Did Joseph Doob prove that random sequences don't exist? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T12:23:10Z http://mathoverflow.net/feeds/question/69773 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/69773/did-joseph-doob-prove-that-random-sequences-dont-exist Did Joseph Doob prove that random sequences don't exist? teil 2011-07-08T05:49:25Z 2011-07-09T13:39:20Z <p>In the book "<a href="http://books.google.com/books?id=lMdz84dWNnAC&amp;q=Doob#v=snippet&amp;q=Doob&amp;f=falseBlockquoteblah" rel="nofollow">The Mathematical Experience</a>" it says: </p> <blockquote> <p>"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." </p> </blockquote> <p>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}$.</p> <p>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. </p> http://mathoverflow.net/questions/69773/did-joseph-doob-prove-that-random-sequences-dont-exist/69851#69851 Answer by Gerry Myerson for Did Joseph Doob prove that random sequences don't exist? Gerry Myerson 2011-07-09T04:49:43Z 2011-07-09T04:49:43Z <p>At Gerald Edgar's suggestion, I promote my comment to an answer. </p> <p>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.</p> http://mathoverflow.net/questions/69773/did-joseph-doob-prove-that-random-sequences-dont-exist/69874#69874 Answer by Louigi Addario-Berry for Did Joseph Doob prove that random sequences don't exist? Louigi Addario-Berry 2011-07-09T13:39:20Z 2011-07-09T13:39:20Z <p>There is an excellent article by Sérgio B. Volchan in the American Mathematical Monthly, titled <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.671&amp;rep=rep1&amp;type=pdf" rel="nofollow">What Is a Random Sequence</a>, 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 <em>typicality</em>, 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 <em>incompressibility</em> of the sequence. </p> <p>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. </p>