Algorithmically random sequence

The notion can be applied analogously to sequences on any finite alphabet (e.g. decimal digits).

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.

Unlike algorithmic randomness, which is defined for computable (and thus deterministic) processes, stochastic randomness is usually said to be a property of a sequence that is a priori known to be generated by (or is the outcome of) 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 (algorithmically) 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 or MLR.

In this definition, some admissible rules might abstain forever on some sequences, and thus fail to pick out 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.

[2]) Theorem (Abraham Wald, 1936, 1937)[3] If there are only countably many admissible rules, then almost any sequence is a collective.

Intuitively, the long-time average of a random sequence should oscillate on both sides of

However, Jean Ville showed that, even with countably many rules, there exists a binary sequence that tends towards

For example, the Ville construction does not satisfy one of the laws of the iterated logarithm:

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.

The null cover characterization conveys the intuition that a random real number should not have any property that is "uncommon".

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.

Note that if we identify the Cantor space of binary sequences with the interval [0,1] of real numbers, the measure on Cantor space agrees with Lebesgue measure.

, then the Turing machine can decide in finite time that the string does fall inside

If the Turing machine can reject the hypothesis at all significance levels, then the string is not random.

[8] The martingale characterization conveys the intuition that no effective procedure should be able to make money betting against a random sequence.

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.

(Martin-Löf 1966) Intuitively, this universal test for randomness says "If the sequence has increasingly long prefixes that can be increasingly well-compressed on this universal Turing machine", then it is not random."

[9] Conversely, if the sequence is compressible, then by the pigeonhole principle, only a vanishingly small fraction of sequences are like that, so we can define a new test for randomness by "has a compression by this universal Turing machine".

For example, consider a binary sequence sampled IID from the Bernoulli distribution.

(Example 14.2.8 [10]) Consider a casino offering fair odds at a roulette table.

The roulette table generates a sequence of random numbers.

Conversely, if this sequence is not algorithmically random, then there is a lower semi-computable strategy to win.

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.

At the opposite end of the randomness spectrum there is the notion of a K-trivial set.