Algorithmic Randomness

Origin. Martin-Löf (1966), building on Kolmogorov; extensive Soviet/Russian development by Levin, Zvonkin, and others.

Mechanism. A sequence is algorithmically random if it has no structure that allows compression — its Kolmogorov complexity equals its length. Equivalently, no effective statistical test rejects it as non-random. This formalizes randomness without reference to probability: a sequence is random if there's no shorter description of it.

Procedure. To test whether data is random: attempt to compress it. If compression succeeds, the data has structure (patterns, regularities). If compression fails (compressed length ≈ original length), the data is algorithmically random with respect to the compressor. For stronger tests, apply multiple compression algorithms and statistical tests. Persistent incompressibility suggests genuine randomness; compressibility reveals structure to exploit.

Applies to. Random number generation testing, cryptography, anomaly detection, distinguishing signal from noise.

Limitations. Practical compression algorithms are weaker than Kolmogorov complexity; failure to compress proves nothing about true randomness, only that the algorithm didn't find structure. Also: short sequences cannot be meaningfully tested — randomness is a property of infinite sequences, and any finite sequence has some short program producing it.