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

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.

-
What is the definition of $\infty$-distributed? –  Roland Bacher Jul 8 '11 at 6:33
There is a good discussion of this in the chapter on randomness in Seminumerical Algorithms, Volume 2 of Knuth's The Art Of Computer Programming. –  Gerry Myerson Jul 8 '11 at 6:33
I think the point is this. Von Mises stated that the "policy or rule" must not depend on knowing the value of $x_n$ before you decide whether or not to select $x_n$. However, it was pointed out that of all the possible rules (corresponding to arbitrary increasing sequences $n_1, n_2, ...$) there will be one that happens to pick out the $k$'s in the sequence $x_1, x_2, \ldots$. Of course without foreknowledge of the sequence you don't know which rule this is, but you do know that one of the uncountably many possible rules has this property. So that's why the von Mises definition is flawed. –  Robert Israel Jul 8 '11 at 7:59
There is an excellent and sympathetic discussion of von Mises' definition and the controversy that surrounded it in van Lambalgan's 1987 PhD thesis "Random Sequences" available on-line at: staff.science.uva.nl/~michiell/docs/fFDiss.pdf –  Alex Simpson Jul 8 '11 at 11:37
Two of the previous comments, when combined, seem to capture the intended notion of rule. A rule must not "peek" at the sequence being tested, and it must be recursive. That is, whether $x_n$ is in the extracted sequence should be computable from $(x_1,\dots,x_{n-1})$. Then almost all sequences will be random. (One could weaken "computable" by allowing some other countable class of rules, for example arithmetically definable ones, and still have almost all sequences random.) –  Andreas Blass Jul 8 '11 at 15:39

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.

-

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.

-