Did Joseph Doob prove that random sequences don't exist? - MathOverflow

Did Joseph Doob prove that random sequences don't exist?

2011-07-08T05:49:25Z

In the book "The Mathematical Experience" it says:

"An infinite [binary] sequence $x_1, x_2, \ldots$ is called random in the sense of von Mises if every infinite sequence $x_{n_1}, x_{n_2}, \ldots$ extracted from it and determined by a policy or rule R is $\infty$-distributed. Now comes the shocker. It has been established by Joseph Doob that there are no sequences that are random in the sense of von Mises."

A sequence on $\{H,T\}$ is $\infty$-distributed if for each positive integer $k$ and sequence $\vec y \in \{H,T\}^k$ the set $\{n\in {\mathbb N} \colon \langle x_{n},\dots,x_{n+k-1}\rangle=\vec y\}$ has density $2^{-k}$.

But the definition of von Mises seems so natural to me that if a sequence does not satisfy it then the sequence is not random.

Answer by Gerry Myerson for Did Joseph Doob prove that random sequences don't exist?

2011-07-09T04:49:43Z

At Gerald Edgar's suggestion, I promote my comment to an answer.

There is a good discussion of the questions raised here in the chapter on randomness in Seminumerical Algorithms, Volume 2 of Knuth's The Art Of Computer Programming.

Answer by Louigi Addario-Berry for Did Joseph Doob prove that random sequences don't exist?

2011-07-09T13:39:20Z

There is an excellent article by Sérgio B. Volchan in the American Mathematical Monthly, titled What Is a Random Sequence, which discusses how the von Mises-Wald-Church model of randomness is unsatisfactory. He goes on to explain the proposed candidate for a definition of a random sequence due to Martin-Löf, that of typicality, or "randomness with respect to effective statistical tests". Here randomness is defined with respect to a given measure $\mu$ on infinite binary strings; it turns out to coincide with a natural notion of incompressibility of the sequence.

Anyway, in short: there are other natural candidates for what it should mean for a sequence to be random, that turn out to work pretty well (and are beautiful), and Volchan's paper is a good place to learn about them.