Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

"A sequence of bits is random if there exists no Program shorter than it which can produce the same sequence." ~ Kolmogorov

Q: How do the digits of Pi fall as a random sequence based on the above definition

share|improve this question
5  
Isn't it immediate that the digits of pi are not random? We can write a finite program to compute them. Or am I missing something? –  rghthndsd Jun 8 '13 at 17:26
    
Which digits of pi? Kolmogorov talks about finite sequences –  Goldstern Jun 8 '13 at 17:31
    
Please see Wikipedia on Randomness : "Randomness occurs in numbers such as log (2) and pi". Thats what i want to clear –  ARi Jun 8 '13 at 17:32
3  
There are many different notions of randomness. The digits of pi may satisfy some (such as "Uniform distribution"/"normality"), and fail some others. –  Goldstern Jun 8 '13 at 17:39
    
So my question in generic form is : For any program/ Turing machine which generates a symbol from a finite alphabet of symbols in a finite time , and keeps doing so ad infimitum.. How can one say that sequence of symbols so generated is random Also does it make a difference if i know the Program –  ARi Jun 8 '13 at 17:47
add comment

closed as off topic by Goldstern, Steven Landsburg, Benoît Kloeckner, Bruce Westbury, Douglas Zare Jun 8 '13 at 18:58

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

up vote 4 down vote accepted

If you were buying a random sequence from a specialized firm for you poker website, and if you were handed the first 1,000,000 digits of $\pi$, you would be entitled to go ask for a refund. Indeed, gifted players on your website could figure out the pattern and use it to win games.

This intuition is formalized by the fact that arbitrarily long sequences of digits of $\pi$ can be produced by a small algorithm, so it is the opposite of random. Even if you change a few of them from time to time, it is still not very random, as you can use a program for $\pi$ and just specify a few exceptions in your program.

So in short, $\pi$ is not considered a random number according to Kolmogorov complexity, and that is good.

Now it is true that the digits of $\pi$ and log(2) verify some necessary conditions to be random, regarding the distribution of their digits. But these conditions are not sufficient, and Kolmogorov complexity allows us to distinguish between what seems random (like $\pi$) and what really is.

EDIT: More precisions

Ok I will try to clarify this a bit more, after questions in the comments.

First of all, you can consider finite or infinite sequences.

Randomness is only defined for infinite ones, and we rather talk of complexity for finite sequences, i.e. what is the minimal size of a program generating this sequence. The important difference is that for infinite sequences, either a program exists (and it is not random) or no program exists (and it is random). So randomness is a yes/no question. Notice that almost all infinite sequences are random, as there are countably many programs and uncountably many infinite sequences.

For finite sequences, a program always exists, but it can be as long as the sequence (and then the sequence is complex), or significantly shorter (then the sequence is simpler). So complexity of finite sequences is a quantitative question.

The link between the two is that a sequence is random if and only if the complexities or its successives prefixes are "maximal" in a precise sense (which is up to some additive constant). You can read more precise statements here. The beauty of this notion is that like in Church-Turing thesis, several very different definitions boil down to the same notion of randomness.

So if as you say we are given just the beginning of $\pi$ up to the $k^{th}$ digit, we can just talk how it is more or less complex. In fact for $\pi$ it won't be too complex, because you can fix your program computing $\pi$ once and for all, and just change the digit you want to stop at (which takes only a logarithmic space). And once again, this is because $\pi$ is not random.

Now the last important point that was already emphasized by Andreas Blass in the comments, but it does not hurt to repeat, is the following: all these definitions are mathematical, so they are completely independent of our current knowledge. Either $\pi$ (as an infinite sequence rigorously defined) is random or it is not, no matter whether we already found an algorithm for it or not. Finding an algorithm is a proof for its non-randomness, but it does not change the fact that this algorithm existed, and $\pi$ IS a non-random sequence, it does not BECOME one when we find an algorithm for it.

share|improve this answer
1  
I don't think it's known that the digits of $\pi$ satisfy even very rudimentary necessary conditions for randomness. It seems, though, to be widely believed that $\pi$ is normal, i.e., that every finite sequence of digits occurs in $\pi$ with the same asymptotic frequency that it would have in a genuinely random number. –  Andreas Blass Jun 8 '13 at 19:35
    
Yes most properties on the distributions of digits of $\pi$ are still open, so the picture is even worse. –  Denis Jun 8 '13 at 20:03
    
So, let me understand this, digits in Pi can not be taken as a random sequence ? –  ARi Jun 9 '13 at 6:01
    
Yes that's the main point... –  Denis Jun 9 '13 at 12:08
1  
Thanks a ton, this does clarify the issue –  ARi Jun 11 '13 at 16:45
show 8 more comments

Not the answer you're looking for? Browse other questions tagged or ask your own question.