-2
$\begingroup$

"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

$\endgroup$
5
  • 5
    $\begingroup$ 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? $\endgroup$
    – rghthndsd
    Jun 8, 2013 at 17:26
  • $\begingroup$ Which digits of pi? Kolmogorov talks about finite sequences $\endgroup$
    – Goldstern
    Jun 8, 2013 at 17:31
  • $\begingroup$ Please see Wikipedia on Randomness : "Randomness occurs in numbers such as log (2) and pi". Thats what i want to clear $\endgroup$
    – ARi
    Jun 8, 2013 at 17:32
  • 4
    $\begingroup$ There are many different notions of randomness. The digits of pi may satisfy some (such as "Uniform distribution"/"normality"), and fail some others. $\endgroup$
    – Goldstern
    Jun 8, 2013 at 17:39
  • $\begingroup$ 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 $\endgroup$
    – ARi
    Jun 8, 2013 at 17:47

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 8, 2013 at 19:35
  • $\begingroup$ Yes most properties on the distributions of digits of $\pi$ are still open, so the picture is even worse. $\endgroup$
    – Denis
    Jun 8, 2013 at 20:03
  • $\begingroup$ So, let me understand this, digits in Pi can not be taken as a random sequence ? $\endgroup$
    – ARi
    Jun 9, 2013 at 6:01
  • $\begingroup$ Yes that's the main point... $\endgroup$
    – Denis
    Jun 9, 2013 at 12:08
  • $\begingroup$ But that is conditional, suppose the number Pi is not known ( let alone its formula) would I still treat the sequence as not random $\endgroup$
    – ARi
    Jun 9, 2013 at 15:04

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