Algorithmically Random Sequence - Three Equivalent Definitions

Three Equivalent Definitions

Martin-Löf's original definition of a random sequence was in terms of constructive null covers; he defined a sequence to be random if it is not contained in any such cover. Leonid Levin and Claus-Peter Schnorr proved a characterization in terms of Kolmogorov complexity: a sequence is random if there is a uniform bound on the compressibility of its initial segments. Schnorr gave a third equivalent definition in terms of martingales (a type of betting strategy). Li and Vitanyi's book An Introduction to Kolmogorov Complexity and Its Applications is the standard introduction to these ideas.

• Kolmogorov complexity (Schnorr 1973, Levin 1973): Kolmogorov complexity can be thought of as a lower bound on the algorithmic compressibility of a finite sequence (of characters or binary digits). It assigns to each such sequence w a natural number K(w) that, intuitively, measures the minimum length of a computer program (written in some fixed programming language) that takes no input and will output w when run. Given a natural number c and a sequence w, we say that w is c-incompressible if .

An infinite sequence S is Martin-Löf random if and only if there is a constant c such that all of S's finite prefixes are c-incompressible.

• Constructive null covers (Martin-Löf 1966): This is Martin-Löf's original definition. For a finite binary string w we let C_w denote the cylinder generated by w. This is the set of all infinite sequences beginning with w, which is a basic open set in Cantor space. The product measure μ(C_w) of the cylinder generated by w is defined to be 2-|w|. Every open subset of Cantor space is the union of a countable sequence of disjoint basic open sets, and the measure of an open set is the sum of the measures of any such sequence. An effective open set is an open set that is the union of the sequence of basic open sets determined by a recursively enumerable sequence of binary strings. A constructive null cover or effective measure 0 set is a recursively enumerable sequence of effective open sets such that and for each natural number i. Every effective null cover determines a set of measure 0, namely the intersection of the sets .

A sequence is defined to be Martin-Löf random if it is not contained in any set determined by a constructive null cover.

• Constructive martingales (Schnorr 1971): A martingale is a function such that, for all finite strings w, where is the concatenation of the strings a and b. This is called the "fairness condition"; a martingale is viewed as a betting strategy, and the above condition requires that the better plays against fair odds. A martingale d is said to succeed on a sequence S if where is the first n bits of S. A martingale d is constructive (also known as weakly computable, lower semi-computable, subcomputable) if there exists a computable function such that, for all finite binary strings w

1. for all positive integers t,

A sequence is Martin-Löf random if and only if no constructive martingale succeeds on it.

(Note that the definition of martingale used here differs slightly from the one used in probability theory. That definition of martingale has a similar fairness condition, which also states that the expected value after some observation is the same as the value before the observation, given the prior history of observations. The difference is that in probability theory, the prior history of observations just refers to the capital history, whereas here the history refers to the exact sequence of 0s and 1s in the string.)