Random Sequence - Modern Approaches

Modern Approaches

In the mid 1960s, A. N. Kolmogorov and D. W. Loveland independently proposed a more permissive selection rule. In their view Church's recursive function definition was too restrictive in that it read the elements in order. Instead they proposed a rule based on a partially computable process which having read any N elements of the sequence, decides if it wants to select another element which has not been read yet. This definition is often called Kolmogorov-Loveland stochasticity. But this method was considered too weak by Alexander Shen who showed that there is a Kolmogorov-Loveland stochastic sequence which does not conform to the general notion of randomness.

In 1966 Per Martin-Löf introduced a new notion which is now generally considered the most satisfactory notion of algorithmic randomness. His original definition involved measure theory, but it was later shown that it can be expressed in terms of Kolmogorov complexity. Kolmogrov's definition of a random string was that it is random if has no description shorter than itself via a universal Turing machine.

Three basic paradigms for dealing with random sequences have now emerged:

• The frequency / measure-theoretic approach. This approach started with the work of Robert von Mises and Alonzo Church. In the 1960s Per Martin-Löf noticed that the sets coding such frequency-based stochastic properties are a special kind of measure zero sets, and that a more general and smooth definition can be obtained by considering all effectively measure zero sets.

• The complexity / compressibility approach. This paradigm was championed by A. N. Kolmogorov along with contributions Levin and Gregory Chaitin. For finite random sequences, Kolmogorov defined the "randomness" as the entropy, i.e. Kolmogorov complexity, of a string of length K of zeros and ones as the closeness of its entropy to K, i.e. if the complexity of the string is close to K it is very random and if the complexity is far below K, it is not so random.

• The predictability approach. This paradigm was due to Claus P. Schnorr and uses a slightly different definition of constructive martingales than martingales used in traditional probability theory. Schnorr showed how the existence of a selective betting strategy implied the existence of a selection rule for a biased sub-sequence.

In most cases, theorems relating the three paradigms (often equivalence) have been proven.

It is important to realize that for each of the definitions given above for infinite sequences, if one adds a billion zeros to the front of the random sequence the new sequence will still be considered random. Hence any application of these concepts to practical problems needs to be performed with care.