Algorithmic Randomness

Kolmogorov's axioms assign probabilities to sets of sequences; they say nothing about whether an individual sequence is random. Indeed the question looks ill-posed: every infinite binary sequence has probability zero under the fair-coin measure, so no assignment of probabilities distinguishes $0101010101\dots$ from a typical coin record. Yet the intuition that the first is not random is not confused, and making it precise requires a genuinely different apparatus — computability theory rather than measure theory.

Three definitions, arrived at independently in the 1960s, turn out to coincide. That convergence is the main evidence that the notion is the right one.

References: Downey–Hirschfeldt, Algorithmic Randomness and Complexity; Li–Vitányi, An Introduction to Kolmogorov Complexity; Nies, Computability and Randomness.

1. Why Measure Theory Cannot Answer

The strong law (laws-of-large-numbers.md) says that almost every sequence has limiting frequency $1/2$. It does not say which. The set of exceptions is null but non-empty, and the theory has no way to pick out a particular sequence and ask whether it belongs.

Von Mises' pre-Kolmogorov programme tried to define probability via randomness: a collective was to be an infinite sequence whose limiting frequencies exist and are invariant under "admissible" subsequence selection. It foundered on the selection rules — with all selection rules allowed, no collective exists (select the positions where the digit is $1$); with too few, the definition is vacuous. Church's proposal to admit exactly the computable selection rules was the right instinct, and Ville's theorem then showed that even this is insufficient: there are Church-random sequences whose partial sums approach the frequency $1/2$ strictly from one side, which no genuinely random sequence should do.

The modern definitions repair this by requiring not invariance under selection but the failure of every effective test.

2. Kolmogorov Complexity

Definition. Fix a universal prefix-free Turing machine $U$. The (prefix) Kolmogorov complexity of a finite binary string $x$ is

$$K(x)=\min \{|p|:U(p)=x\},$$

the length of the shortest program that outputs $x$.

Invariance theorem. For any other universal machine $U^{\prime }$, $|K_U(x)->K_{U^{\prime }}(x)|\le c$ with $c$ independent of $x$. So $K$ is well defined up to an additive constant.

A counting argument shows most strings are incompressible: there are $2^n$ strings of length $n$ but only $2^n-1$ programs shorter than $n$, so at least half of the strings of length $n$ have $K(x)\ge n-1$. Randomness is typical; structure is rare — the algorithmic counterpart of a measure-theoretic "almost every".

$K$ is not computable. If it were, one could compute "the least string with $K(x)>n$" by a program of length $O(\log n)$ — the Berry paradox made into a proof. Relatedly, $K(x)\ge n$ is provable in a fixed formal system only for finitely many $n$ (Chaitin's incompleteness theorem), a variant of Gödel's theorems. Randomness is definable but not decidable.

3. Martin-Löf Randomness

Definition. A Martin-Löf test is a uniformly computably enumerable sequence $(U_n)$ of open subsets of $\{0,1{\}}^{\mathbb{N}}$ with $\mu (U_n)\le >2^{-n}$ (where $\mu$ is the fair-coin measure). A sequence $x$ passes the test if $x\notin {\bigcap }_n{U}_n$, and $x$ is Martin-Löf random if it passes every such test.

The idea: a null set is "effectively null" if it can be covered by an algorithmically generated sequence of shrinking open sets. There are only countably many tests, so the non-random sequences form a null set and almost every sequence is Martin-Löf random — but now "almost every" has been replaced by a property each individual sequence either has or lacks.

Universality. There is a single universal Martin-Löf test that subsumes all others, so "passes every test" is checkable against one object.

4. The Coincidence

Levin–Schnorr theorem. For $x\in \{0,1{\}}^{\mathbb{N}}$ the following are equivalent:

1. $x$ is Martin-Löf random (passes every effective statistical test);
2. $K(x\upharpoonright n)\ge n-c$ for some constant $c$ and all $n$ (incompressibility of every prefix);
3. no computable betting strategy (martingale) succeeds on $x$, i.e. no effective strategy makes unbounded capital betting on its bits (unpredictability).

Three intuitions about randomness — passing all statistical tests, being incompressible, being unpredictable — turn out to define the same class. This is the strongest available evidence that the notion is natural rather than stipulative, and it is a striking instance of a definition being confirmed by convergence of independent characterizations.

Formulation (3) is literally the martingale of martingales.md restricted to computable strategies — the "you cannot beat a fair game" theorem turned into a definition of what it means for a particular sequence to be fair.

5. Consequences and Calibration

• Randoms satisfy the laws. Every Martin-Löf random sequence obeys the strong law of large numbers and the law of the iterated logarithm — the failure sets are effectively null, so they are covered by tests. Ville's counterexample to Church randomness is excluded, because his one-sided sequence is defeated by a computable martingale.
• Chaitin's $\Omega$. The halting probability $\Omega ={\sum }_{U(p)\downarrow }{2}^{-|p|}$ is Martin-Löf random and, being definable, is a specific real number that is provably random. It is also uncomputable, and its first $n$ bits decide the halting problem for all programs of length $\le n$.
• No random sequence is computable. A computable $x$ has $K(x\upharpoonright n)=O(\log n)$, failing (2). So the randoms form a class of objects that exist, provably, but cannot be produced.
• A hierarchy, not a dichotomy. Weaker (Schnorr, computable randomness) and stronger ($n$-randomness, relative to higher jumps) notions form a strict hierarchy. "Random" is a scale indexed by computational power, not a single property — which is itself a foundationally significant finding.

6. Relation to the Measure-Theoretic Theory

The two frameworks answer different questions and neither replaces the other.

The bridge is that effectively null refines null: algorithmic randomness picks out, inside the measure-one set where the classical theorems hold, a subset whose membership is a property of the individual object. It thereby delivers what von Mises wanted, and does so on top of the measure-theoretic theory rather than as a replacement for it — the frequencies whose existence it guarantees are the ones the strong law predicts.

7. Where This Is Used

• Computational complexity theory — the resource-bounded analogues (pseudorandomness, derandomization) replace "computable" with "polynomial-time".
• Laws of large numbers §5 — the classical statement this page individualizes.
• Martingales — characterization (3).
• Gödel's incompleteness theorems — Chaitin's variant in §2.