Why nobody can agree what a random number is

Flip a coin thirty-two times and write down the bits. Every particular sequence has probability one in four billion — the all-zeros string exactly as much as any ragged, patternless one. Probability theory, on its own, cannot say what a random outcome is. It took the twentieth century three attempts to say it properly.

The discomfort is real. If a casino dealt you thirty-two zeros you would walk out, yet the calculation offers no grounds: that string is precisely as likely as the one you would have accepted. Whatever we mean by random, it is a property of the string itself, not of the chance that produced it. The first serious attempt, von Mises around 1919, said: a sequence is random if heads comes up half the time — in the whole sequence and in every subsequence you could reasonably select. The definition spent two decades under repair — Church eventually pinned "reasonably select" to computable selection rules — and still turned out too weak: sequences satisfying it can violate basic laws of chance that any honest coin obeys.¹ Frequency is a symptom of randomness, not the thing itself.

The decisive idea came from @Kolmogorov in 1965, and it is the one the figure below makes visible: measure a string by the length of the shortest program that prints it. A patterned string has a short description — "16 copies of 01" — so its #kolmogorov-complexity is far below its length. A random string is one that admits no shortcut: the cheapest way to specify it is to quote it in full. Randomness, on this account, is #incompressibility.

Three intuitions, one class

The third attempt attacked from statistics. In 1966 @Martin-Löf made "passes every statistical test" precise: a test is any effectively describable set of outcomes with vanishing measure, and a sequence is random if no such test catches it. Because the tests can be enumerated, there is a single universal test that subsumes them all — randomness stops being a checklist and becomes one definition. Then the surprise: for infinite sequences, passing every Martin-Löf test is equivalent to having incompressible prefixes, and both are equivalent to no effective gambling strategy winning unbounded money against the bits.² Frequency, unpredictability, incompressibility — three different intuitions converge on one class of sequences. That convergence is the best evidence we have that the concept is real.

Now the punchline. Kolmogorov complexity is not computable. If a program could calculate K, you could ask it for the first string with complexity above a million — thereby describing that string in a few hundred bits, a contradiction straight out of the Berry paradox. Worse, provability collapses too: any formal system can certify the randomness of at most finitely many individual strings, no matter how many actually are random.³

So the situation is genuinely odd. Almost every string is random: there are simply not enough short programs to go around, and a count of them shows that at least half of all n-bit strings cannot be compressed by even a single bit. Yet you can never point to a particular one and prove it earned the label. Randomness of an individual object is perfectly well-defined and permanently undecidable, both at once.

This is why the arguments never quite end. A statistician audits frequencies, a cryptographer demands unpredictability against every feasible adversary, an information theorist measures compression, and each of them is holding one face of the same underlying object — an object whose definition is exact and whose instances can only ever be rejected, never confirmed. Your random number generator can fail an audit. It can never, even in principle, pass one completely.