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.

`$x_n$`

is in the extracted sequence should becomputablefrom`$(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 Jul 8 '11 at 15:39