Random Sequence : Definition of [closed]

Question

"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

Answer 1

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.