Algorithmically random sequence


Intuitively, an algorithmically random sequence is a sequence of binary digits that appears random to any algorithm running on a universal Turing machine. The notion can be applied analogously to sequences on any finite alphabet. Random sequences are key objects of study in algorithmic information theory.
In measure-theoretic probability theory, introduced by Andrey Kolmogorov in 1933, there is no such thing as a random sequence. For example, consider flipping a fair coin infinitely many times. Any particular sequence, be it or, has equal probability of exactly zero. There is no way to state that one sequence is "more random" than another sequence, using the language of measure-theoretic probability. However, it is intuitively obvious that looks more random than. Algorithmic randomness theory formalizes this intuition.
As different types of algorithms are sometimes considered, ranging from algorithms with specific bounds on their running time to algorithms which may ask questions of an oracle machine, there are different notions of randomness. The most common of these is known as Martin-Löf randomness, but stronger and weaker forms of randomness also exist. When the term "algorithmically random" is used to refer to a particular single sequence without clarification, it is usually taken to mean "incompressible" or, in the case the sequence is infinite and prefix algorithmically random, "Martin-Löf–Chaitin random".
Since its inception, Martin-Löf randomness has been shown to admit many equivalent characterizations—in terms of compression, randomness tests, and gambling—that bear little outward resemblance to the original definition, but each of which satisfies our intuitive notion of properties that random sequences ought to have: random sequences should be incompressible, they should pass statistical tests for randomness, and it should be difficult to make money betting on them. The existence of these multiple definitions of Martin-Löf randomness, and the stability of these definitions under different models of computation, give evidence that Martin-Löf randomness is natural and not an accident of Martin-Löf's particular model.
It is important to disambiguate between algorithmic randomness and stochastic randomness. Unlike algorithmic randomness, which is defined for computable processes, stochastic randomness is usually said to be a property of a sequence that is a priori known to be generated by an independent identically distributed equiprobable stochastic process.
Because infinite sequences of binary digits can be identified with real numbers in the unit interval, random binary sequences are often called random real numbers. Additionally, infinite binary sequences correspond to characteristic functions of sets of natural numbers; therefore those sequences might be seen as sets of natural numbers.
The class of all Martin-Löf random sequences is denoted by RAND or MLR.

History

Richard von Mises

formalized the notion of a test for randomness in order to define a random sequence as one that passed all tests for randomness. He defined a "collective" to be an infinite binary string defined such that
  • There exists a limit.
  • For any "admissible" rule, such that it picks out an infinite subsequence from the string, we still have. He called this principle "impossibility of a gambling system".
To pick out a subsequence, first pick a binary function, such that given any binary string, it outputs either 0 or 1. If it outputs 1, then we add to the subsequence, else we continue. In this definition, some admissible rules might abstain forever on some sequences, and thus fail to pick out an infinite subsequence. We only consider those that do pick an infinite subsequence.
Stated in another way, each infinite binary string is a coin-flip game, and an admissible rule is a way for a gambler to decide when to place bets. A collective is a coin-flip game where there is no way for one gambler to do better than another over the long run. That is, there is no gambling system that works for the game.
The definition generalizes from binary alphabet to countable alphabet:
  • The frequency of each letter converges to a limit greater than zero.
  • For any "admissible" rule, such that it picks out an infinite subsequence from the string, the frequency of each letter in the subsequence still converges to the same limit.
Usually the admissible rules are defined to be rules computable by a Turing machine, and we require. With this, we have the Mises–Wald–Church random sequences. This is not a restriction, since given a sequence with, we can construct random sequences with any other computable.
However, this definition was found not to be strong enough.
Intuitively, the long-time average of a random sequence should oscillate on both sides of, like how a random walk should cross the origin infinitely many times. However, Jean Ville showed that, even with countably many rules, there exists a binary sequence that tends towards fraction of ones, but, for every finite prefix, the fraction of ones is less than.

Per Martin-Löf

The Ville construction suggests that the Mises–Wald–Church sense of randomness is not good enough, because some random sequences do not satisfy some laws of randomness. For example, the Ville construction does not satisfy one of the laws of the iterated logarithm: Naively, one can fix this by requiring a sequence to satisfy all possible laws of randomness, where a "law of randomness" is a property that is satisfied by all sequences with probability 1. However, for each infinite sequence, we have a law of randomness that, leading to the conclusion that there are no random sequences.
defined "Martin-Löf randomness" by only allowing laws of randomness that are Turing-computable. In other words, a sequence is random iff it passes all Turing-computable tests of randomness.
The thesis that the definition of Martin-Löf randomness "correctly" captures the intuitive notion of randomness has been called the Martin-Löf–Chaitin Thesis; it is somewhat similar to the Church–Turing thesis.

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. Gregory Chaitin, Leonid Levin and Claus Peter Schnorr proved a characterization in terms of algorithmic 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. Li and Vitanyi's book is the standard introduction to these ideas.
  • Algorithmic complexity : Algorithmic complexity can be thought of as a lower bound on the algorithmic compressibility of a finite sequence. It assigns to each such sequence w a natural number K that, intuitively, measures the minimum length of a computer program 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.
  • Constructive null covers : This is Martin-Löf's original definition. For a finite binary string w we let Cw 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 μ 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.
  • Constructive martingales : 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": if a martingale is viewed as a betting strategy, then the above condition requires that the bettor 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 if there exists a computable function such that, for all finite binary strings w
  1. for all positive integers t,

  2. Interpretations of the definitions

The Kolmogorov complexity characterization conveys the intuition that a random sequence is incompressible: no prefix can be produced by a program much shorter than the prefix.
The null cover characterization conveys the intuition that a random real number should not have any property that is "uncommon". Each measure 0 set can be thought of as an uncommon property. It is not possible for a sequence to lie in no measure 0 sets, because each one-point set has measure 0. Martin-Löf's idea was to limit the definition to measure 0 sets that are effectively describable; the definition of an effective null cover determines a countable collection of effectively describable measure 0 sets and defines a sequence to be random if it does not lie in any of these particular measure 0 sets. Since the union of a countable collection of measure 0 sets has measure 0, this definition immediately leads to the theorem that there is a measure 1 set of random sequences. Note that if we identify the Cantor space of binary sequences with the interval of real numbers, the measure on Cantor space agrees with Lebesgue measure.
An effective measure 0'' set can be interpreted as a Turing machine that is able to tell, given an infinite binary string, whether the string looks random at levels of statistical significance. The set is the intersection of shrinking sets, and since each set is specified by an enumerable sequence of prefixes, given any infinite binary string, if it is in, then the Turing machine can decide in finite time that the string does fall inside. Therefore, it can "reject the hypothesis that the string is random at significance level ". If the Turing machine can reject the hypothesis at all significance levels, then the string is not random. A random string is one that, for each Turing-computable test of randomness, manages to remain forever un-rejected at some significance level.
The martingale characterization conveys the intuition that no effective procedure should be able to make money betting against a random sequence. A martingale d'' is a betting strategy. d reads a finite string w and bets money on the next bit. It bets some fraction of its money that the next bit will be 0, and then remainder of its money that the next bit will be 1. d doubles the money it placed on the bit that actually occurred, and it loses the rest. d is the amount of money it has after seeing the string w. Since the bet placed after seeing the string w can be calculated from the values d, d, and d, calculating the amount of money it has is equivalent to calculating the bet. The martingale characterization says that no betting strategy implementable by any computer can make money betting on a random sequence.