Randomness: Processes and Individual Outcomes

"Random" is used for two different things, and conflating them causes persistent confusion.

A process is random when it is governed by a probability distribution — when its outcomes are not determined by prior conditions, or at least not predictable from them. This is a property of the generating mechanism.

An outcome is random when it exhibits no pattern — when the particular sequence produced has no structure that would allow it to be compressed or predicted. This is a property of the object, not of its source.

The two come apart in both directions, which is why they need separate treatment. A genuinely random process can produce the sequence of a million zeros; that sequence is not random by any reasonable standard, though its source was. A deterministic algorithm can produce the digits of $\pi$, which pass every practical statistical test for randomness while being generated by a short program.

Process randomness

The classical notion, and the one von Mises tried to axiomatise. His collectives required that limiting frequencies be invariant under admissible place selections — no gambling system should improve one's expected return by selecting a subsequence.

Formalising "admissible" proved difficult: allowing arbitrary subsequence selection makes collectives impossible, since one can always select the subsequence of all heads. The successful restriction, due to Church and Wald, is to effectively computable place selections, which is the point at which the theory of randomness becomes a branch of computability theory.

Process randomness in physics means indeterminism: the prior state does not fix the outcome. As the determinism and chance page sets out, this is distinct from unpredictability, and chaotic deterministic systems are unpredictable without being indeterministic.

Individual randomness

The modern theory, developed by Kolmogorov, Chaitin, Solomonoff, Martin-Löf, Levin, and Schnorr, applies to individual objects. The mathematical treatment has the details; the philosophically important content is that three quite different-looking definitions turn out to coincide.

Incompressibility. The Kolmogorov complexity $K(x)$ of a string is the length of the shortest program producing it. A string is random if it is incompressible — if $K(x)\approx |x|$, so that no description is shorter than the string itself. Most strings are incompressible by a simple counting argument: there are $2^n$ strings of length $n$ and fewer than $2^n$ shorter programs.

Unpredictability. A sequence is random if no effective betting strategy — a computable martingale — can make unbounded gains betting on its successive digits.

Typicality. A sequence is Martin-Löf random if it passes every effectively presented statistical test, that is, if it lies outside every effectively null set.

The Levin–Schnorr theorem establishes that these three notions coincide for infinite binary sequences. That is a striking convergence: incompressibility, unpredictability, and typicality are conceptually distinct desiderata, formalised with different machinery, and they pick out the same class. The convergence is the main reason to regard algorithmic randomness as capturing a natural notion rather than an arbitrary stipulation.

What the theory delivers

Randomness becomes a property of the object. This is what the classical framework could not provide. A probability measure assigns the same value to every specific sequence of a million coin flips — $2^{-10^6}$ each — so the measure cannot distinguish the all-heads sequence from a patternless one. The intuition that one is anomalous and the other unremarkable is real, and algorithmic randomness is what vindicates it.

It clarifies what frequency accounts were reaching for. Von Mises's randomness axiom was an attempt to say that a collective has no exploitable structure. The martingale characterisation is exactly that claim, made precise.

Almost all sequences are random, and none can be proved to be. With respect to the uniform measure, the Martin-Löf random sequences have measure one. But by a Gödel-style argument, for any consistent formal system there is a bound $c$ such that the system cannot prove $K(x)>c$ for any specific string. Randomness is generic and individually uncertifiable — a combination with no analogue in the classical theory.

Limitations

Machine-dependence. Kolmogorov complexity depends on the choice of universal machine, though only up to an additive constant. For infinite sequences this washes out and the class of random sequences is machine-independent; for finite strings the constant can exceed the differences one cares about, so "this string is random" is not a sharp claim about short strings.

Uncomputability. $K(x)$ is not computable. One cannot in general determine whether a given string is random, which limits the notion's practical application.

It is not physical randomness. A Martin-Löf random sequence can be produced by a deterministic process — indeed, being incompressible has nothing to do with how a sequence was generated. So algorithmic randomness characterises the product, not the source, and cannot settle whether the world is indeterministic.

Pseudorandomness

The practical counterpart, and the place where the process/product distinction matters most.

A pseudorandom generator is a deterministic algorithm producing sequences that pass statistical tests. The output is compressible — the generator and seed constitute a short description — so it is not algorithmically random. But it may be computationally indistinguishable from random: no efficient algorithm can tell it apart from a truly random sequence.

This weaker notion is what applications actually need. Randomised algorithms in complexity theory work with pseudorandom bits, and cryptographic security rests on computational indistinguishability rather than on genuine randomness. The relationship between $\mathsf{BPP}$ and $\mathsf{P}$ — whether randomness genuinely helps computation — is a central open problem, and the prevailing conjecture is that it does not: that under plausible hardness assumptions $\mathsf{BPP}=\mathsf{P}$, so randomness is a convenience rather than a resource.

That is a philosophically notable prospect. If it holds, then for computational purposes randomness adds nothing that sufficient complexity does not already provide, and the practical significance of the process/product distinction largely collapses.

Randomness and probability

How does the theory bear on the interpretations?

• Frequentism is the natural beneficiary: von Mises's programme is completed by the algorithmic theory, and his randomness axiom is given a precise and defensible form.
• Propensity concerns process randomness and is untouched by the algorithmic theory, which says nothing about generating mechanisms.
• Subjectivism can use algorithmic randomness for priors: the Solomonoff prior weights hypotheses by $2^{-K}$, providing a universal prior with good convergence properties, at the cost of uncomputability and machine-dependence. This is the formal core of the simplicity discussion.
• Best-system chance has a natural affinity: a system's fit to the mosaic and the mosaic's compressibility are closely related notions, and a world whose history is algorithmically random is one no simple system summarises well.

Where this sits

The theory of randomness is a rare case where a philosophical notion received a fully satisfactory mathematical treatment, with three independent formalisations proved equivalent. What it settles is what it is for an outcome to be patternless. What it leaves open is whether any physical process is genuinely indeterministic — which is the question quantum chance addresses and which no amount of examining the output can decide, since deterministic sources can produce incompressible sequences.

The last page of this folder turns to the application of chance where the stakes are personal rather than physical: whether indeterminism can underwrite free will.