Algorithmically random sequence

Intuitively, an algorithmically random sequence is an infinite sequence of characters that appears random to any algorithm. The first suitable definition of random sequences was given by Per Martin-Löf in 1966. Earlier researchers such as Richard von Mises had attempted to formalize the notion of a test for randomness in order to define a random sequence as one that passed all tests for randomness; however, the precise notion of a randomness test was left vague. Martin-Löf's key insight was to use the theory of computation to formally define the notion of test for randomness.

Martin-Löf's definition has the advantage that it is robust to changes in the model of computation being used: they all define exactly the same set of random sequences. Martin-Löf randomness has since been shown to admit many equivalent characterizations -- in terms of compression, prediction, and gambling -- that bear little outward resemblance to his original definition, but each of which satisfy our intuitive notion of properties that random sequences ought to have (they should be incompressible, unpredictable, and difficult to make money betting on). This gives additional evidence that Martin-Löf randomness is in some sense, a universal definition of randomness that is a fundamental property of mathematics and not an accident of Martin-Löf's particular model.

Definition

Martin-Löf's original definition of a random sequence was in terms of constructive null covers and is a bit involved. Claus-Peter Schnorr proved the simplest characterization in terms of Kolmogorov complexity: a infinite sequence S is random if and only if there exists a constant c such that, for all but finitely many prefixes w of S, ${\rm {K}}(w)\geq |w|-c$, where K(w) is the Kolmogorov complexity of w. In other words, S is random if its initial segments are incompressible, in the sense that no significantly shorter program can produce them.

Equivalent Definitions

There are several equivalent characterizations of Martin-Löf randomness of infinite sequences. The definitions below are in terms of the binary alphabet {0,1}, but the extension to arbitrary finite alphabets is routine. Besides the Kolmogorov complexity characterization, the definitions below are quite technical, and Li and Vitanyi's book gives a good introduction to these ideas.

• Kolmogorov complexity (Schnorr 1971) - A sequence S is random if there exists a constant c such that, for all but finitely many prefixes w of S, ${\rm {K}}(w)\geq |w|-c$.
• Constructive null covers (Martin-Löf 1966) - This is Martin-Löf's original definition. A sequence is random if it is not contained in any constructive null cover. A constructive null cover of a set of sequences X is a total computable function $g:\mathbb {N} \times \mathbb {N} \to \{0,1\}^{*}$ satisfying, for all positive integers k,
  • $X\subseteq \bigcup _{l=0}^{\infty }C_{g(k,l)},$
  • $\sum _{l=0}^{\infty }{\rm {Pr}}(C_{g(k,l)})\leq 2^{-k}.$

  Here, C_n is the n^th cylinder: the set of infinite sequences beginning with the n^th string in the lexicographical ordering of all finite strings. ${\rm {Pr}}(C_{n})$ is the probability of the n^th cylinder; the value 2^-|w|, if w is the string associated with the cylinder C_n.

• Constructive martingales (Schnorr 1971) - A sequence is random if no constructive martingale succeeds on it. A martingale is a function $d:\{0,1\}^{*}\to [0,\infty )$ such that, for all finite strings w,

  $d(w)={\frac {d(w0)+d(w1)}{2}}$.

  (This is Ville's original definition of a martingale, later extended by Joseph Leo Doob.) A constructive martingale d is a martingale that is lower semi-computable: there exists a computable function ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ such that, for all finite strings w and positive integers t,
  • ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$
  • $\lim _{t\to \infty }{\widehat {d}}(w,t)=d(w).$

  A martingale d is said to succeed on a sequence S if $\limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,$ where $S\upharpoonright n$ is the first n bits of S'.

References

• Li M. and Vitanyi P. M. B. An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, Berlin, 1997. Second Edition.
• Martin-Löf, P. "The definition of random sequences." Information and Control 9, 602-619 (1966).
• Schnorr, C. P., "A unified approach to the definition of a random sequence." Mathematical Systems Theory, 5 (1971), 246-258.
• Ville, J. "Etude critique de la notion de collectif." Gauthier-Villars, Paris, 1939.