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.
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. The term "algorithmically random" used to refer to a particular single sequence without clarification is usually taken to mean "incompressible" or, in the case the sequence is infinite and prefix algorithmically random, "Martin-Löf-Chaitin random".
It is important to disambiguate algorithmic randomness with 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
The first suitable definition of a random sequence 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 a test for randomness. This contrasts with the idea of randomness in probability; in that theory, no particular element of a sample space can be said to be 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 satisfy 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 a fundamental property of mathematics and not an accident of Martin-Löf's particular model. 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. The complexity is required to be prefix-free: The program is followed by an infinite string of 0s, and the length of the program includes the number of zeroes to the right of the program that the universal Turing machine reads. The additional requirement is needed because we can choose a length such that the length codes information about the substring. 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 G-delta set| 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
- for all positive integers t,
Interpretations of the definitions
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.
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.
Properties and examples of Martin-Löf random sequences
- Chaitin's halting probability Ω is an example of a random sequence.
- RANDc is a measure 0 subset of the set of all infinite sequences. This is implied by the fact that each constructive null cover covers a measure 0 set, there are only countably many constructive null covers, and a countable union of measure 0 sets has measure 0. This implies that RAND is a measure 1 subset of the set of all infinite sequences.
- Every random sequence is normal.
- There is a constructive null cover of RANDc. This means that all effective tests for randomness are, in a sense, subsumed by this universal test for randomness, since any sequence that passes this single test for randomness will pass all tests for randomness.
- There is a universal constructive martingale d. This martingale is universal in the sense that, given any constructive martingale d, if d succeeds on a sequence, then d succeeds on that sequence as well. Thus, d succeeds on every sequence in RANDc.
- The class RAND is a subset of Cantor space, where refers to the second level of the arithmetical hierarchy. This is because a sequence S is in RAND if and only if there is some open set in the universal effective null cover that does not contain S; this property can be seen to be definable by a formula.
- There is a random sequence which is, that is, computable relative to an oracle for the Halting problem. Chaitin's Ω is an example of such a sequence.
- No random sequence is decidable, computably enumerable, or co-computably-enumerable. Since these correspond to the,, and levels of the arithmetical hierarchy, this means that is the lowest level in the arithmetical hierarchy where random sequences can be found.
- Every sequence is Turing reducible to some random sequence.. Thus there are random sequences of arbitrarily high Turing degree.
Relative randomness
An important result relating to relative randomness is van Lambalgen's theorem, which states that if C is the sequence composed from A and B by interleaving the first bit of A, the first bit of B, the second bit of A, the second bit of B, and so on, then C is algorithmically random if and only if A is algorithmically random, and B is algorithmically random relative to A. A closely related consequence is that if A and B are both random themselves, then A is random relative to B if and only if B is random relative to A.
Stronger than Martin-Löf randomness
Relative randomness gives us the first notion which is stronger than Martin-Löf randomness, which is randomness relative to some fixed oracle A. For any oracle, this is at least as strong, and for most oracles, it is strictly stronger, since there will be Martin-Löf random sequences which are not random relative to the oracle A. Important oracles often considered are the halting problem,, and the nth jump oracle,, as these oracles are able to answer specific questions which naturally arise. A sequence which is random relative to the oracle is called n-random; a sequence is 1-random, therefore, if and only if it is Martin-Löf random. A sequence which is n-random for every n is called arithmetically random. The n-random sequences sometimes arise when considering more complicated properties. For example, there are only countably many sets, so one might think that these should be non-random. However, the halting probability Ω is and 1-random; it is only after 2-randomness is reached that it is impossible for a random set to be.Weaker than Martin-Löf randomness
Additionally, there are several notions of randomness which are weaker than Martin-Löf randomness. Some of these are weak 1-randomness, Schnorr randomness, computable randomness, partial computable randomness. Yongge Wang showedthat Schnorr randomness is different from computable randomness. Additionally, Kolmogorov-Loveland randomness is known to be no stronger than Martin-Löf randomness, but it is not known whether it is actually weaker.
At the opposite end of the randomness spectrum there is the notion of a K-trivial set. These sets are anti-random in that all initial segment is logarithmically compressible, but they are not computable.