9
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 5
    $\begingroup$ What is the definition of $\infty$-distributed? $\endgroup$
    – Roland Bacher
    Commented Jul 8, 2011 at 6:33
  • 7
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Commented Jul 8, 2011 at 6:33
  • 4
    $\begingroup$ 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. $\endgroup$
    – Robert Israel
    Commented Jul 8, 2011 at 7:59
  • 3
    $\begingroup$ 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 $\endgroup$
    – Alex Simpson
    Commented Jul 8, 2011 at 11:37
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Andreas Blass
    Commented Jul 8, 2011 at 15:39

2 Answers 2

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .