Randomness is a property of the string, not of how it was made.
Toss a fair coin 20 times and you might get 00000000000000000000
or 01101001011001011010. Both have exactly the same probability,
2⁻²⁰. Yet the first one looks obviously fake and the second
looks random. Classical probability has nothing to say about a single
fixed string — so where does that intuition come from?
The answer this book builds from scratch: measure a string by the length of the shortest program that prints it. The all-zeros string has a tiny program (“print 0 twenty times”), so it is highly compressible. A genuinely random string has no program shorter than just quoting it verbatim. A string is random exactly when it cannot be compressed — when its information content equals its length.
One number — the length of the shortest description — at once grounds information, randomness, and the limits of proof.
The puzzle
Two equally probable strings — why is only one of them “random”?
Step 1 · The unsettling premise
Two strings, the same odds — yet your gut insists one isn't random.
Here is the whole subject in one picture. Take two bit strings of length 20. The book's own running contrast: a string with obvious structure against a string that looks like coin flips.
The usual escape hatch — “the probability of all-zeros is negligible” —
does not work. A fair coin produces every specific 20-bit string
with the same probability 2⁻²⁰, including the random-looking
one. So you cannot reject the all-zeros run on probability grounds without
also rejecting the string you would happily accept.
The intuition is real, though: one string follows a short rule (“all zeros”), the other follows no rule shorter than itself. The book's whole program is to turn that informal sense of “follows a rule” into one exact, machine-checkable quantity.
Randomness will not be a property of the coin or the process. It will be a property of the individual string — measured by how short a program can reproduce it.
Kolmogorov, 1965, asked whether one can “free information theory from probabilities” and develop “the intuitive idea of randomness as incompressibility — the law describing the object cannot be shortened.” This page follows the authors' free draft of the AMS book.
Step 2 · Compression, by decompressor
“Compressed size” means: the shortest input that makes a fixed program print your string.
We want to measure “follows a short rule.” The book starts from something everyone already trusts: file compression. zip, gzip, rar all shrink a regular file and barely dent a random one.
Strip it to the bone. Forget the compressor; keep only the
decompressor — a program D that reads a short
description p and outputs a string. We say p is
a description of x with respect to D when
D(p) = x. The complexity of x relative to D is the
length of its shortest description:
ℓ(p) = length of p in bits · the minimum over the empty set is +∞ (no description ⇒ infinite complexity)
But complexity depends on which decompressor you pick — and silly choices give silly numbers. Here are three, applied to our 20-zero string:
D₁ · copy machine
ℓ(x)
Copy in to out. Every string is its own description, so C(x) = ℓ(x) — no compression at all. A safe baseline.
D₂ · zeros specialist
≈ log n
Reads a count, prints zeros. Twenty zeros need only bin(20) ≈ log₂ n bits. Great for zeros — but any string with a 1 has infinite complexity.
D₃ · cheater
0
Hardwired to one string. Define D₃(Λ) = x and that one string has complexity 0 — by cheating. Any single string can be made “simple” this way.
Complexity is only meaningful once we stop letting the decompressor be tailored to the string. Step 3 finds a single universal decompressor that no other can beat by more than a constant.
A description mode is any partial computable function from binary strings to binary strings; it may run forever on some inputs and be undefined there. We care only about the shortest description that exists.
The measure
One universal yardstick · why it is well-defined · and how to count incompressible strings
Step 3 · One decompressor to rule them all
There is a single universal decompressor no other can beat by more than a constant.
We saw the danger: tailor the decompressor to a string and you can fake any complexity you like. The fix is to merge decompressors, then take the idea to its limit.
Start with just two decompressors, D₁ and D₂.
Build a combined one D that reads the first bit as an
index — 0 means “use D₁ on the rest”, 1 means “use D₂ on the rest”:
Pick which sub-decompressor the prefix bit selects — the merged D pays just one extra bit
CD(x) ≤ CD₁(x) + 1 and CD(x) ≤ CD₂(x) + 1. One merged machine is essentially as good as the better of the two — for the price of a single bit.
This is the whole trick, scaled up. A zip archive already works this way: a small preamble names the compression mode, the rest is the payload.
Now take the limit. Instead of two machines, index all of them:
prefix each description with the program P that interprets it
(written self-delimiting, so D knows where P ends). This universal
D(Py) = P(y) is just an interpreter — and it gives the
theorem the whole subject rests on:
Theorem 1 (Solomonoff–Kolmogorov) · cP = ℓ(P), the length of P's program · such a D is called optimal
Fix any optimal D and drop the subscript: C(x) is Kolmogorov complexity. Switch to a different optimal D′ and every value changes by at most a constant: |CD(x) − CD′(x)| ≤ c. That additive slack is the price of having a definition that does not depend on a programming language.
The constant c is the length of an interpreter translating one language into the other — for natural languages, a few hundred or thousand bits. So all statements about C are inherently asymptotic, true “up to O(1)”.
Step 4 · Complexity = information content
No string needs more than its own length — and processing never adds information.
Now that C(x) is well-defined, it should behave the way “amount of information” ought to behave. Three sanity checks, each a one-line proof from the optimal D — and each holding up to O(1):
upper bound
C(x) ≤ ℓ(x) + c
Theorem 2
Just quote the string: the copy machine D₁ gives ℓ(x), and optimality adds only a constant.
processing
C(A(x)) ≤ C(x) + c
Theorem 3
Reverse the bits, double them, encrypt — an algorithm and its inverse change C by at most a constant.
conditional
C(xy) = C(y) + C(x|y)
+ O(log n)
C(x|y) is the new information in x once y is known — the basis of mutual information later in the book.
For the 20-zero string, a short program (“print 0 twenty times”) gives C ≈ log₂ 20 ≈ 5 bits — far below its length 20. For the coin-flip string, no program beats quoting it: C ≈ 20. That gap between C and ℓ is exactly what your gut was reacting to in Step 1.
“Amount of information” here ignores meaning: a chaotic string has more information than a meaningful one, simply because it has no short description. Shannon entropy needs a probability distribution; C needs only the string.
Step 5 · Counting the compressible
There simply aren't enough short programs to go around — most strings can't be compressed.
We have a number, C(x), and the gap to ℓ(x) felt like “randomness”. Now we prove the gut feeling: compressible strings are rare, by a counting argument so simple you can do it on your fingers.
A description shorter than n bits is itself a binary string
of length 0, 1, …, n−1. Add those up:
1 + 2 + 4 + … + 2n−1 = 2n − 1
descriptions. Each names at most one string. So:
Theorem 5 · there are simply not enough short descriptions for everyone to have one
Fix the length at 100 bits (so 2100 strings in all) and slide the compression threshold. The fraction that can be squeezed below it is at most 2n−100 — and it collapses fast:
Drag the “save at least k bits” threshold — watch how few length-100 strings qualify
At k = 10, fewer than 2⁻¹⁰ — about 1 in 1024 — of all length-100 strings have complexity below 90. Every extra bit you demand halves the survivors. The overwhelming majority are incompressible.
The sliver vanishes. Pushing the threshold right makes the compressible fraction shrink geometrically — this is a real, exact bound, not an illustration.
The real experiment: toss a coin 80,000 times, save the 10,000-byte file. Bet that no compressor (chosen before the toss) shrinks it by more than 10 bytes — the chance of losing is below 2⁻⁸⁰ per compressor.
Step 6 · Randomness = incompressibility
A string's “randomness deficiency” is the bits it wastes — ℓ(x) minus C(x).
Most strings are incompressible (Step 5), and incompressible is exactly what “random” felt like in Step 1. So define randomness as incompressibility, and measure the shortfall directly.
The randomness deficiency of a string is d(x) = ℓ(x) − C(x): how many bits it could be squeezed by. A small deficiency means random; a large one means there's a rule hiding inside. Run our two strings through it:
A low-deficiency string can't have a lopsided bit frequency: if its share
of 1s drifted from ½, that pattern would be a rule, giving a
shorter program — contradiction. So “most strings have frequency near ½”
falls straight out of “most strings are incompressible”.
There is no sharp line between random and non-random finite strings — flipping one bit can't suddenly make 000…0 random. For a crisp yes/no answer you must pass to infinite sequences, which is Step 8 and Martin-Löf's work.
Randomness & reach
A built-in catch · complexity as a proof tool · and the line to infinity
Step 7 · The catch — C is uncomputable
No algorithm can ever tell you a string's exact complexity. Berry's paradox forbids it.
We have a perfect ruler for randomness. The sting in the tail: you can never read it off mechanically. C(x) is not computable — and not even any nontrivial lower bound for it is.
The proof is the old Berry paradox made rigorous: “the smallest number not definable in under fourteen words” — a thirteen-word phrase that just defined it. Replay it with complexity:
C(x) can be approximated from above — run all short programs and watch which halt — but never pinned down exactly, and never bounded usefully from below. Every application of complexity lives with this one-sided fog.
A consequence: the optimal decompressor must be non-total — some inputs make it loop forever. If it always halted, you could compute C(x) by trying all shorter descriptions, which Theorem 6 forbids.
Step 8 · Complexity as a proof tool · the line to infinity
“A random object exists” becomes “pick an incompressible one” — and finite randomness sharpens into Martin-Löf's.
C is a perfect-but-unreadable ruler. Yet you don't need to compute it to use it — and that turns the whole theory into a method for proving things, the payoff most readers came for.
The incompressibility method: to show an object with some property exists, take an incompressible string (Step 5 guarantees most strings are) and argue that any object lacking the property would compress it. Existence proofs shrink to a few lines.
For a clean yes/no notion of randomness, pass from finite strings to infinite sequences. Martin-Löf called a sequence random if it passes every effective statistical test — it avoids all algorithmically describable “null sets” of measure zero. Levin and Schnorr then tied it back to complexity:
Levin–Schnorr criterion (using monotone complexity) · every prefix stays nearly incompressible forever
The Strong Law of Large Numbers drops out: every Martin-Löf random sequence has limiting frequency ½, and the non-random sequences form a set of measure zero — so “almost every sequence has frequency ½” is just “almost every sequence is random”.
Four equivalent faces of randomness recur through the book: frequency stability (von Mises), chaoticness (incompressibility), typicalness (Martin-Löf), and unpredictability (martingales) — different doors into the same room.
Step 9 · The whole picture & recap
One ruler — and can you now explain it?
You've met the puzzle, the universal yardstick, the counting bound, the incompressibility-as-randomness idea, the uncomputability catch, and the reach to infinity. Final question: how does it all fit, and have you got it?
Report card · what the shortest program measures
Information content · bits in x
Randomness · incompressibility
How rare structure is · counting
prior hope · “read off the complexity”
Now you can explain it. Five questions — answer each out loud before opening it. If all five come easily, you've genuinely got this book's core.
Why doesn't probability explain “000…0 isn't random”?
A fair coin produces every specific 20-bit string with the same probability 2⁻²⁰, including the random-looking one. So you can't reject all-zeros on probability alone. The difference is in the strings themselves: one follows a short rule, the other doesn't.
What is Kolmogorov complexity C(x)?
The length of the shortest input that makes a fixed optimal decompressor print x — i.e. the shortest program that outputs x. The all-zeros string has a tiny program; a random string needs one as long as the string itself.
Why is C(x) the same no matter the programming language?
The invariance theorem: a universal decompressor beats any other by at most a constant (the length of an interpreter), so switching languages changes C by only an additive O(1). That's why we drop the subscript.
Why are most strings incompressible?
There are fewer than 2ⁿ descriptions shorter than n bits, so fewer than 2ⁿ strings can have complexity below n. Demanding k bits of compression leaves at most a 2⁻ᵏ fraction — the overwhelming majority can't be squeezed.
If C is uncomputable, what good is it?
You rarely need its exact value. The incompressibility method just uses “an incompressible string exists” to prove lower bounds and existence results; and the Levin–Schnorr criterion ties incompressibility to Martin-Löf randomness for infinite sequences.
What it founded — measuring information by the shortest program gave a single home to randomness, information, and provability. Define randomness as incompressibility; count to show it's the norm; use that scarcity as a proof engine. The book builds all of it from these first principles.
“The meaning of the new definition is very simple. Entropy H(x|y) is the minimal length of a program P that permits construction of the value of x, the value of y being known.” — A. N. Kolmogorov, 1965 (quoted in the book's preface)
It gave “information” a meaning without probability.
Kolmogorov's shortest-program idea turned vague intuitions — “this looks random”, “this theory is simpler” — into one exact, machine-checkable quantity, and that quantity now threads through computer science, logic, and statistics.
Algorithmic information theory
A whole branch of theory — incompressibility proofs, mutual information, algorithmic statistics — grew from the single definition built in this book.
Occam's razor, made exact
“The best theory is the shortest description of the data” became formal: Solomonoff induction and the Minimum Description Length principle for learning.
Martin-Löf randomness
The crisp definition of a random infinite sequence — and its complexity criterion — underpins modern computability theory and the foundations of probability.
From compression to Occam's razor to the limits of proof — all read off one number: the length of the shortest program.