Von Mises, Ville, and martingales: alternative roads to randomness through selection rules and betting strategies.
Before Martin-Löf, before Kolmogorov complexity, the first serious attempt to define random sequences was by Richard von Mises (1919). His idea was intuitive and beautiful, though ultimately flawed.
A selection rule is a procedure that looks at a sequence and decides which positions to select. For example: "take every third bit," or "take bits after a run of two zeros." Von Mises called a sequence satisfying both conditions a Kollektiv.
The idea is: a random sequence should remain random even after you cherry-pick a subsequence. You shouldn't be able to find a pattern that, when exploited, reveals a bias.
A selection rule is a function σ: {0,1}* → {0, 1} that, given the bits seen so far, decides whether to "select" the next bit (1 = select, 0 = skip). The selected subsequence consists of the bits at positions where σ returns 1.
Crucially, the decision to select position n depends only on the bits before position n, not on the bit at position n itself. The gambler decides to bet before seeing the card.
Von Mises never precisely specified which selection rules are "admissible." This vagueness was the source of much debate. Different choices lead to different notions of randomness.
Alonzo Church (1940) proposed a natural fix for Von Mises' vagueness: take the admissible selection rules to be the computable ones.
This is a clean, precise definition. It says: no algorithm can select a biased subsequence from ω. The sequence defeats all computable "frequency-finding" strategies.
However, Mises-Church randomness turns out to be too weak. It is strictly weaker than Martin-Löf randomness. Ville showed why.
In 1939, Jean Ville proved a devastating result:
This sequence passes all frequency tests but fails a different kind of test: the running average never dips below 1/2. A truly random sequence should cross 1/2 infinitely often (by the Law of the Iterated Logarithm).
A martingale is a betting strategy. Formally, a martingale is a function d: {0,1}* → [0, ∞) satisfying the fairness condition:
Think of d(x) as the gambler's capital after seeing the sequence x. The fairness condition says: no matter what the next bit is, the expected capital doesn't change. The gambler starts with d(λ) dollars and bets on each bit.
A martingale succeeds on a sequence ω if d(ω[0..n)) → ∞ as n → ∞. The gambler makes unbounded profit — the sequence has a pattern the gambler can exploit.
A sequence is random (in the martingale sense) if no martingale from a given class succeeds on it. Different classes give different randomness notions.
The key result connecting martingales to Martin-Löf randomness:
A martingale d is lower semicomputable if d(x) can be approximated from below by a computable sequence. Equivalently, the gambler can compute increasingly accurate lower bounds on the optimal bet at each step.
This gives a beautiful game-theoretic characterization of ML-randomness: a sequence is random iff no effective gambler can make unlimited money betting on it.
Schnorr (1971) proposed a weaker randomness notion using computable martingales (rather than lower semicomputable ones).
Schnorr randomness is strictly weaker than ML-randomness. There exist sequences that are Schnorr random but not ML-random. The difference: Schnorr randomness only defends against "constructive" gambling strategies, while ML-randomness also defends against semi-constructive ones.
| Notion | Martingale class | Strength |
|---|---|---|
| Mises-Church | Computable selection rules | Weakest |
| Schnorr | Computable martingales | Middle |
| Martin-Löf | Lower semicomputable martingales | Strongest |
Martingales also characterize effective Hausdorff dimension. Instead of asking "does the martingale grow to infinity?", we ask "how fast does it grow?"
An s-supermartingale is like a martingale but with a different fairness condition: d(x) ≥ 2s−1 (d(x0) + d(x1)). The parameter s controls how "aggressively" the gambler bets. When s = 1, this is a standard martingale. When s < 1, the gambler has an advantage — the game is biased.
Sequences with dimension s < 1 are "partially random" — a gambler with an s-advantage can make money, but a fair gambler cannot. The dimension measures the boundary between exploit and no-exploit.
The simulation below shows a gambler using a martingale strategy against a sequence. Against a random sequence, the capital fluctuates but doesn't grow. Against a patterned sequence, the gambler can exploit the pattern.
The gambler bets on each bit. Against random sequences, capital stays bounded. Against biased or patterned sequences, the gambler's capital grows.
| Approach | Key idea | Randomness notion |
|---|---|---|
| Von Mises | Subsequence frequencies | Kollektiv (informal) |
| Church | Computable selection rules | Mises-Church (weakest) |
| Ville | Showed selection rules insufficient | Motivated martingales |
| Martingales | Betting strategies / capital growth | Depends on class |
| Schnorr | Computable martingales | Schnorr randomness |
| Schnorr's thm | L.s.c. martingales | ML-randomness |