Algorithmically random sequence
From CryptoDox, The Online Encyclopedia on Cryptography and Information Security
Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm. The definition applies equally well to sequences on any finite set of characters. Random sequences are key objects of study in algorithmic information theory.
As different types of algorithm are sometimes considered, ranging from algorithms with specific bounds on their running time to algorithms which may ask questions of an oracle, there are different notions of randomness. The most common of these is known as Martin-Löf randomness (or sometimes as 1-randomness), but stronger and weaker forms of randomness also exist. The term "random" used to refer to a sequence without clarification is usually taken to mean "Martin-Löf random".
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 (binary) sequences is denoted by RAND.
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.
Martin-Löf randomness has since 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.
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 an excellent introduction these ideas.
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.
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(w) 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(w), d(w0), and d(w1), 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 (even in the weak sense of constructive strategies, which are not necessarily computable) can make money betting on a random sequence.
Properties of Martin-Löf random sequences
As each of the equivalent definitions of a Martin-Löf random sequence is based on what is computable by some Turing machine, one can naturally ask what is computable by a Turing oracle machine. For a fixed oracle A, a sequence B which is not only random but in fact satisfies the equivalent definitions for computability relative to A (e.g., no martingale which is constructive relative to the oracle A succeeds on B) is said to be random relative to B. Two sequences, while themselves random, may contain very similar information, and therefore neither will be random relative to the other. Any time there is a Turing reduction from one sequence to another, the second sequence cannot be random relative to the first, just as computable sequences are themselves nonrandom; in particular, this means that Chaitin's Ω is not random relative to the halting problem.
An important result relating to relative randomness is van Lambolgen'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 very closely related consequence is that if both 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 particularly complicated properties. One expects that a random sequence should not have properties which are very rare - specifically, if the properties are only possessed by a measure 0 collection of sequences - but this may not be true for Martin-Löf random sequences if the property is sufficiently complicated, as any statistic test which checks for the property may be too complicated to be a Martin-Löf test. However, for any such property that one is likely to consider, any sequence which is n-random for sufficiently large n will not have the unusual property.
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. 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.