This is a technicality, but isn't it the case that if the deterministic algorithm required takes up as much space at the mathematical object itself, the object can be considered random?(according to Gregory Chaitin etc.)
What is? My question was about whether random numbers can have patterns.
I thought a sort of general definition of patterns was the existence of correlation from one state to another, while the definition of randomness was the lack of the same correlation. So I'm wondering how random numbers can have patterns? It's possible my view of "random numbers" and "patterns" is not sufficiently nuanced.
I have no idea what your comment means in this context.
Sorry I thought the context of your question was "Prime numbers may be generated in deterministic fashion"
Of course you know that random numbers will have a distribution. I think this is an example of that. Most people would have expected a uniform distribution here but it isn't the case.
Right, but then they aren't random, right? I feel like this is a problem of semantics.. what do we mean by "random number"? I thought the definition was basically, "lack of pattern." What is a better definition?
Well it's degrees of random. You just shift the probabilities. Rolling a die is still random even though you'll never roll a 7, or a 3.5, or a "b". Picking a number from a normal distribution is still random even though it's more likely to get you a sample from the center than from the edges.
In mathematical terms, random refers to a quantity which is "randomly" picked from a distribution. In a sense, things are only random in reference to a distribution.
A "random number" in the lay sense is a "random number from a uniform probability distribution"; a uniform distribution being one where each element is equally likely.
You might note there are still patterns in uniform distributions. e.g. Uniformly random integers are never not integers, and they also fit within a particular range: we have no way to pick random numbers uniformly between -infinity and infinity.
It's actually a very good question. Even up to the Renaissance, we had no real conception of "probability" -- even though there were games of chance that depended on it. The Greeks had notions of impossible/possible/likely, but no way to link the notions to the world.
It was finally in the correspondence of Pascal and Fermat in 1654 that a mathematics for probability started to emerge. With the emergence of the laws of large numbers, this mathematics could be linked to observable real-world occurrence rates. (Ian Hacking's book "The Emergence of Probability" is a standard reference, http://www.jstor.org/stable/2184357?seq=1#page_scan_tab_cont...)
Suppose you were confronted with a stream of random numbers, and no intellectual or mathematical framework for quantifying them. Just coming up with a notion of a frequency curve (i.e., a density), and statistical independence of "unlinked" events would be a huge leap.
I used to TA an undergrad probability class, and in the first weeks, I'd ask the students to quantify some random variable, and they'd sometimes blankly look back and say, "it's just random" -- what we taught them is how you break that down in terms of the familiar quantities (densities, independence, correlations) and operations (multiplying for independence, integrating for expectation, integrating and renormalizing for conditioning).
So to get back to your original question, even a deterministic sequence, like
0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, ...
could be regarded as random, and given a density and all the other folderol. And a "completely random" sequence of 0/1 equiprobable bits also has a density, etc. And so does everything in between.
Thank you, that is a very good answer. So "random" is how you look at a sequence. It's more a model (context in which to interpret a sequence) than an observable fact. Is that a fair interpretation?
By saying "this is a random sequence," you enable a statistical view of the problem. Even for purely deterministic sequences, this can be useful.
Last question, something I've never been perfectly clear on, what is the difference between "random" and "stochastic"? My understanding is that a stochastic model is a model featuring stochastic variables, which are variables that draw from some random distribution. Is the terminology I am using correct?
For almost all purposes, "stochastic" is literally a synonym for "random". But sometimes the usage favors one and not the other.
You would talk of a "random variable" (loosely, a quantity that exhibits random behavior, although there is a technical definition that is more precise and has a different flavor), not a "stochastic variable".
Sometimes, you would talk about a "stochastic matrix" (which is actually deterministic, an example of a namespace clash), because a "random matrix" would indeed be random be filled with "random variables".
But, you would often talk about a "stochastic process" like Brownian motion. Although you can also say "random process", and that's the same thing.
You would not talk about a "random distribution", that sounds like you mean "arbitrary distribution" (as in, "I picked out some random socks today"). But you don't mean arbitrary, you mean a "statistical distribution" or "probability distribution".
To get all this right, you have to live in that world, you can't just visit. If an outsider could just speak the language using clear rules, there would be no point in all those advanced classes, right? ;-)
The idea of what "random" means turns out to not be very simple after all.
I think in a typical definition (at least as used for CS?), a "random" sequence of numbers _by definition_ has no predictable pattern to it -- that's what makes it random. Of course, a given sequence of random numbers could _happen_ to have all sorts of patterns in it (and indeed, you could find patterns to post-fit to any sequence), but if you can predict it in advance... it's not "random"? I think?
The possibility, however remote, exists that you will randomly select a sequence with patterns and order. In cryptography, we define the term 'pseudorandom' in order to discuss a class of functions that look random.
Pseudorandom sequences are sequences where, given the first n bytes of the sequence, an adversary cannot guess the n+1th byte with probability significantly higher than 1/2.
Basically, it's important to distinguish between blindly selecting a sequence out of all possible sequences, and finding a particular sequence with no discernible internal order.
I used to have a version of that Dilbert comic as a forum signature for a while, except I hacked a little PHP script so it would insert a random number instead of "nine" into that panel (still repeated), different on every reload. Just to confuse people :)
I think it's in quotes because prime numbers have a probability distribution, but it's (obviously) not a uniform distribution. I think that the article is trying to say that there are more subtle rules around the distribution than just probability density.
By "probability density", I mean that the probability of a number around n being prime are about 1/ln(n) -- see the Prime Number Theorem[1] for more -- but of course any given integer is either prime or not.
He got the joke, but was also taking it seriously as a phenomenon that could have interesting implications. This finding obviously doesn't hold base 2 (more accurately, isn't an applicable concept), and apparently becomes more pronounced in base 3.
It's a joke. The last digit of a binary number is parity (odd or even). Since all primes (except for the number 2 [or 10 in binary]) are odd, the last digit will of always be 1.
just tested it against the 10000 first prime numbers in Sublime Text : 2462 prime numbers have a direct neighbour with the same last digit. That's nearly a quarter of them...
Edit: by taking into account sequences with 3 identical digits (110 occurrences), it's even more.
> “Every single person we’ve told this ends up writing their own computer program to check it for themselves,” says Kannan Soundararajan, a mathematician at Stanford University in California, who reported the discovery with his colleague Robert Lemke Oliver
In the 60's Scientific American had an interesting article about a curious pattern in primes. If you start on a grid and fill in the integers in a spiral there are obvious patterns of connected primes. I had to try it of course, on grid paper by hand up to a couple of hundred.
This is true, they're called Ulam spirals. But the reasons for these patterns appearing are afaik pretty well understood (I forget exactly how but it wasn't hard to get a grasp of why they are there).
40 comments
[ 2.5 ms ] story [ 107 ms ] threadMore discussion at https://news.ycombinator.com/item?id=11282480
https://en.m.wikipedia.org/wiki/Algorithmically_random_seque...
I thought a sort of general definition of patterns was the existence of correlation from one state to another, while the definition of randomness was the lack of the same correlation. So I'm wondering how random numbers can have patterns? It's possible my view of "random numbers" and "patterns" is not sufficiently nuanced.
I have no idea what your comment means in this context.
Of course you know that random numbers will have a distribution. I think this is an example of that. Most people would have expected a uniform distribution here but it isn't the case.
A "random number" in the lay sense is a "random number from a uniform probability distribution"; a uniform distribution being one where each element is equally likely.
You might note there are still patterns in uniform distributions. e.g. Uniformly random integers are never not integers, and they also fit within a particular range: we have no way to pick random numbers uniformly between -infinity and infinity.
It was finally in the correspondence of Pascal and Fermat in 1654 that a mathematics for probability started to emerge. With the emergence of the laws of large numbers, this mathematics could be linked to observable real-world occurrence rates. (Ian Hacking's book "The Emergence of Probability" is a standard reference, http://www.jstor.org/stable/2184357?seq=1#page_scan_tab_cont...)
Suppose you were confronted with a stream of random numbers, and no intellectual or mathematical framework for quantifying them. Just coming up with a notion of a frequency curve (i.e., a density), and statistical independence of "unlinked" events would be a huge leap.
I used to TA an undergrad probability class, and in the first weeks, I'd ask the students to quantify some random variable, and they'd sometimes blankly look back and say, "it's just random" -- what we taught them is how you break that down in terms of the familiar quantities (densities, independence, correlations) and operations (multiplying for independence, integrating for expectation, integrating and renormalizing for conditioning).
So to get back to your original question, even a deterministic sequence, like
could be regarded as random, and given a density and all the other folderol. And a "completely random" sequence of 0/1 equiprobable bits also has a density, etc. And so does everything in between.By saying "this is a random sequence," you enable a statistical view of the problem. Even for purely deterministic sequences, this can be useful.
Last question, something I've never been perfectly clear on, what is the difference between "random" and "stochastic"? My understanding is that a stochastic model is a model featuring stochastic variables, which are variables that draw from some random distribution. Is the terminology I am using correct?
You would talk of a "random variable" (loosely, a quantity that exhibits random behavior, although there is a technical definition that is more precise and has a different flavor), not a "stochastic variable".
Sometimes, you would talk about a "stochastic matrix" (which is actually deterministic, an example of a namespace clash), because a "random matrix" would indeed be random be filled with "random variables".
But, you would often talk about a "stochastic process" like Brownian motion. Although you can also say "random process", and that's the same thing.
You would not talk about a "random distribution", that sounds like you mean "arbitrary distribution" (as in, "I picked out some random socks today"). But you don't mean arbitrary, you mean a "statistical distribution" or "probability distribution".
To get all this right, you have to live in that world, you can't just visit. If an outsider could just speak the language using clear rules, there would be no point in all those advanced classes, right? ;-)
The possibility, however remote, exists that you will randomly select a sequence with patterns and order. In cryptography, we define the term 'pseudorandom' in order to discuss a class of functions that look random. Pseudorandom sequences are sequences where, given the first n bytes of the sequence, an adversary cannot guess the n+1th byte with probability significantly higher than 1/2. Basically, it's important to distinguish between blindly selecting a sequence out of all possible sequences, and finding a particular sequence with no discernible internal order.
By "probability density", I mean that the probability of a number around n being prime are about 1/ln(n) -- see the Prime Number Theorem[1] for more -- but of course any given integer is either prime or not.
[1] https://en.wikipedia.org/wiki/Prime_number_theorem
The normal distribution is
The distribution following a prime ending in 1: Source: https://gist.github.com/kbadk/71bbb57c9be0d66de156> “Every single person we’ve told this ends up writing their own computer program to check it for themselves,” says Kannan Soundararajan, a mathematician at Stanford University in California, who reported the discovery with his colleague Robert Lemke Oliver
In the 60's Scientific American had an interesting article about a curious pattern in primes. If you start on a grid and fill in the integers in a spiral there are obvious patterns of connected primes. I had to try it of course, on grid paper by hand up to a couple of hundred.
Though these patterns are pretty noisy still.
https://en.wikipedia.org/wiki/Ulam_spiral