Appendix 3

Random Sequences

In 1919, the Austrian-born mathematician Richard von Mises proposed the following definition: an infinite sequence s, say, of 0s and 1s is random if

(a) s satisfies the law of large numbers, that is, ‘there are as many 0s as there are 1s,’ or, more precisely, the limiting value of x/n, where x is the number of 0s among the first n terms of the sequence, is 0.5, and

(b) Every subsequence that can be extracted from s by reasonable means also satisfies the law of large numbers.

Applying von Mises definition to the sequence 0 1 0 1 0 1 0 1 . . . of alternating 0s and 1s would confirm that it is not random, for the subsequence of even bits (the 2nd, 4th, etc.), that is, 1 1 1 1 1 1 . . . , clearly does not satisfy condition (a). Likewise, many other sequences which appear intuitively to be nonrandom fail to satisfy von Mises’ conditions, and hence they are not random also in the technical sense.

Unfortunately, the definition proposed by the Austrian mathematician suffered from a fundamental defect: it did not specify which means for extracting a subsequence are “reasonable” means. To remedy this situation Alonzo Church, an American mathematician, suggested in 1940 that condition (b) of von Mises’ definition should only apply to computable subsequences, that is, to those subsequences whose terms could be defined by a computer program. Although Church’s idea had the merit of making the definition precise, examples were subsequently found of sequences that are intuitively nonrandom but nevertheless satisfy the von Mises-Church notion of “randomness.” The modified definition was therefore too large and the concept of a binary random sequence still could not be pinned down.