What perfect compression looks like

Transcript: this stretch, timestamped

P02 handed us the clever student's prefix code for the robot — 0, 10, 110, 111 — averaging 1.75 bits per instruction, and a diagram showing that its four code words carve the space of binary strings into shares of exactly ½, ¼, ⅛, ⅛, matching the four probabilities dead on. That coincidence is suspicious in a promising way, but a coincidence is not a proof: maybe some baroque scheme that swallows a thousand instructions at a time does better. Grant's third student — "head in the clouds", who never writes a code at all — breaks the deadlock by changing what is being argued about. This page is that argument. It ends one sentence short of the definition of information, log₂(1/p), which P04 picks up.

Outline, with timestamps

• 10:46 — The deadlock: the clever code looks perfect, but how would you rule out something cleverer?
• 10:58 — The third student's idea: noise is incompressible, so perfect output must look like noise.
• 11:28 — Sanity check: the robot code really does emit independent fair coin flips, bit by bit.
• 11:59 — Switch to the receiver's seat: an n-bit message is one of 2ⁿ strings that size.
• 12:29 — Uniform over those 2ⁿ, and the argument is meant to hold for any data, not just robots.
• 13:01 — Push the uniformity back through the encoder: each source message had probability 1/2ⁿ.
• 13:33 — Back to the string diagram: moving one message down a layer collides with its neighbours.
• 14:05 — Bump in the rug: one bit saved here costs two bits elsewhere.
• 14:36 — Equal lengths win for equally likely messages — and that sets up p = 2⁻ⁿ for P04.

Arguing about the output instead of the algorithm

The question at 10:46 is a quantifier problem. "Is 1.75 bits per instruction optimal?" ranges over all encoding schemes — including ones nobody has invented, ones that buffer a million symbols before emitting anything. You cannot win that race by being clever about codes; you will always be one clever step behind.

The third student sidesteps it by asking a different question: forget how the code works — what would its output have to look like? That is a property you can state about a bitstream in isolation, without ever seeing the encoder. If you can pin down the fingerprint of optimality, you get a test you can run on any candidate, and a target you can compute against. This is the same manoeuvre as characterising a maximum by its derivative rather than by comparing it to every other point.

The fingerprint: output that looks like fair coin flips

"…random noise should be incompressible, and therefore, a perfect compression algorithm should produce a bitstream that's indistinguishable from random noise."— Grant Sanderson, 10:58

Be precise about what "random noise" means here, because the whole argument leans on it: every bit is 0 or 1 with probability ½, and the bits are mutually independent. Not "looks messy". Not "high variance". A fair, memoryless coin.

The intuition underneath is a contrapositive. Suppose the output is not like that — bit 40 comes up 1 seventy percent of the time, say, or 11 shows up more often than chance. Then the receiver knows something about the stream before receiving it, and knowledge the receiver already has need not be transmitted. The bias is unspent structure, so any code whose output carries a detectable pattern is beatable.

The robot code passes exactly, and the check at 11:28 is worth walking yourself. The first bit is 0 exactly when the instruction is up: probability ½. Given a leading 1, the surviving probabilities ¼, ⅛, ⅛ renormalise to ½, ¼, ¼, so the second bit is 0 — meaning down — with conditional probability ½. Given 11, the last two instructions are equally likely, so the third bit is again a fair flip. Every bit is a fair coin conditioned on everything before it, which is exactly independence plus uniformity.

Code space is a budget, and length is what you spend

The diagram Grant returns to at 13:33 is worth restating as arithmetic, because the arithmetic is the load-bearing part. In a prefix-free code, claiming a code word of length ℓ forbids every longer string that starts with it — you have claimed a fraction 2⁻ˡ of the space of all binary strings, and nobody else may touch it. Each extra bit of length halves your claim. Since the claims are disjoint and live inside a space of total measure 1, they must sum to at most 1.

Σᵢ 2^(−ℓᵢ)  ≤  1

robot:  2^(−1) + 2^(−2) + 2^(−3) + 2^(−3)  =  ½ + ¼ + ⅛ + ⅛  =  1
        (budget spent exactly — nothing left over, nothing overdrawn)

My addition, not Grant's: this is Kraft's inequality (Leon Kraft, 1949, for prefix codes; Brockway McMillan extended it in 1956 to all uniquely decodable codes, so you cannot escape the budget by abandoning the prefix property). The converse also holds — any list of lengths satisfying the inequality can be realised by some prefix code — which turns "design a code" into "choose a list of lengths that fits the budget", a much easier optimisation.

Note the two columns that agree: ℓ and log₂(1/p). That is not luck, and it is exactly what P04 will name. My addition: minimising L = Σ pᵢ·ℓᵢ subject to the Kraft budget, with the integrality constraint relaxed, gives ℓᵢ = log₂(1/pᵢ) and L = Σ pᵢ·log₂(1/pᵢ). The one-line proof that you cannot do better is Gibbs' inequality: set qᵢ = 2^(−ℓᵢ), and Σ pᵢ·log₂(1/qᵢ) ≥ Σ pᵢ·log₂(1/pᵢ) with equality only when q = p.

From "looks like noise" to "every message was equally likely"

At 11:59 the frame shifts from single symbols to whole messages, and from the sender to the receiver. Suppose the receiver gets a compressed string of n bits. There are 2ⁿ strings of that length. If the stream really is fair coin flips, those 2ⁿ strings are equally likely, each with probability 2⁻ⁿ.

Now push that back through the encoder, the step at 13:01. Compression is lossless, so the map from source messages to code words is injective and the decoder inverts it; a probability on the code word is therefore the probability of the unique source message behind it. Conclusion: in a perfect scheme, every message that compresses to n bits had probability exactly 2⁻ⁿ of arising in the first place.

Grant flags at 12:29 that this is deliberately not about robots any more: nothing in it mentions four instructions or a fixed step size. It is a statement about compressors of anything — English, images, DNA, sensor logs — and that generality is what pays for the abstraction.

Why the uniform case is a dead end: pushing a bump around a rug

All that remains is the lemma the argument was set up for: a source of 2ⁿ equally likely messages genuinely cannot be compressed below n bits on average. Grant does it geometrically at 13:33; the Kraft budget makes it arithmetic. Currently every message sits on layer n and claims 2⁻ⁿ of the space; 2ⁿ of them claim all of it. Try to shorten one:

message A:  n → n−1 bits    claim goes 2^(−n) → 2^(−n+1)    overdrawn by 2^(−n)

pay for it: two messages    n → n+1 bits
            each frees      2^(−n) − 2^(−n−1) = 2^(−n−1)
            two of them     2 · 2^(−n−1) = 2^(−n)          budget balances

net over the three:  −1 + 1 + 1  =  +1 bit worse

"You're basically pushing down a bump on the rug, only to see it pop up even worse in another spot."— Grant Sanderson, 14:05

Because all 2ⁿ messages are equally likely, that +1 is not offset by anything: the expected length rises by 1/2ⁿ bits. The trade is always unfavourable, which is the content of the remark at 14:36 that flat, equal-length codes are optimal for a uniform source. My addition: the coarser version of this is the pigeonhole argument — there are only 2ⁿ − 1 binary strings shorter than n bits, so no injective map can shorten all 2ⁿ messages, and every "compresses everything" claim is provably false before you read the source code.

Therefore: compressibility and predictability are one question

Put the fingerprint and the lemma together and you get the sentence the whole trilogy runs on. Structure in a bitstream is predictability, and predictability is unspent compression: a pattern the decoder could have inferred for itself was waste to transmit, and if the decoder truly cannot guess the next bit better than a coin, there is nothing left to remove.

My addition — the exchange rate, so you can see it is not hand-waving. Suppose a predictor says the next bit is 1 with probability ½ + ε. Coding that bit against your prediction costs the binary entropy H₂(½+ε) instead of a full bit:

H₂(½ + ε)  =  1 − (2/ln 2)·ε²  +  O(ε⁴)   bits per bit

ε = 0.05  →  H₂(0.55) = 0.99278  →  0.722 % of every bit was waste
             on a 1 MiB file that is ≈ 60,600 bits ≈ 7.4 KiB you could still remove

The quadratic is the important shape: a tiny edge buys a very small saving, which is why weak biases in a good compressor's output are hard to monetise — but the saving is strictly positive for any ε ≠ 0, so "optimal" really does mean "zero edge", not "small edge".

The fraction you cannot spend

There is an obvious crack in the story, and Grant walks up to it at the end of this stretch. The argument concluded p = 2⁻ⁿ, so the ideal length is log₂(1/p) — an integer only when p is a power of two. The robot was rigged so that it was; real sources are not. If p = 0.3 the ideal length is 1.737 bits, and no prefix code emits 1.737 bits for a symbol.

A symbol-by-symbol prefix code must round each length up to an integer, so it pays a rounding penalty on every symbol. Huffman's algorithm is optimal among such codes, and its expected length satisfies H(p) ≤ L < H(p) + 1 — the overhead is under a bit per symbol, but it does not vanish. Two standard escapes recover the fraction:

• Block coding. Treat N consecutive symbols as one super-symbol and Huffman-code the blocks. The single rounding penalty is now amortised over N symbols, so the per-symbol overhead drops below 1/N. The cost is an alphabet of size |A|ᴺ, which is why nobody pushes N very far.
• Arithmetic coding (Rissanen and Pasco, independently in 1976; popularised by Witten, Neal and Cleary's 1987 tutorial). It never assigns a code word to a symbol at all. The whole message is one nested subdivision of the interval [0, 1) — each symbol narrows the current interval in proportion to its probability — and the output is enough binary digits to name a point inside the final interval. The final interval has width equal to the message probability P, so naming a point in it takes about log₂(1/P) bits; the standard bound is within about two bits for the entire message. Rounding is paid once, not once per symbol, so the per-symbol overhead is O(1/n) and goes to zero. It also accepts a fresh probability distribution at every step, which is exactly what you need when the distribution comes from a language model.

So the fractional-bit awkwardness is real for symbol codes and essentially fictional for stream codes — which is why P04 can define information as log₂(1/p), a continuous quantity, without apology, and why the third video of the trilogy can promise to hit the theoretical bound to within a bit or two on actual English.

Where people get stuck

"Isn't this circular? It assumes optimal output is noise, then proves noise is incompressible." It is two separate halves and it helps to name them. The first half — an output with detectable structure is beatable — is the contrapositive of optimality, and Grant leaves it as intuition rather than proving it here (the proof is the arithmetic-coding construction above: an edge converts into a shorter file). The second half — a uniform source cannot be beaten — is the bump-in-the-rug counting argument, and that one is proved at 13:33. Together they say noise-like output is the fixed point: nothing better exists, and anything else is worse.

"Real gzip output is obviously not random — it has a magic number and a header." True, and it does not dent the claim. The argument is about the ideal payload, not the container: framing, checksums, dictionaries and end-of-stream markers are all overhead that a lossless format needs and a mathematical idealisation ignores. When you run the coin-flip test on a real file, strip the header first and test the compressed body.

"Incompressible" is a statement about the ensemble, not about your file. No compressor shortens every input — pigeonhole forbids it. What the argument establishes is a bound on the expected length, averaged over the source distribution. Any particular file may still be lucky, and a compressor overfitted to one specific file can shrink it dramatically while making everything else longer.

Fractional bits look like nonsense, and at the symbol level they are. There is no way to give the letter i a code word 4.19 bits long. The quantity is only meaningful as a contribution to a whole-message length, where the fractions of many symbols add up and get rounded once at the end. Hold that thought until P04 — it is the reason Grant insists the definition applies to messages and only bounds symbols on average.

Going deeper, verified

• Visual Information Theory — Chris Olah (2015) · The post Grant credits in the description for this way of drawing entropy; its "code space as a budget you spend" pictures are the same intuition as the string diagram, developed further.
• A Mathematical Theory of Communication — Claude Shannon (1948) · The source. Part I sets up discrete sources and codes; the noiseless coding theorem is the rigorous form of everything argued informally on this page.
• Information Theory, Inference, and Learning Algorithms — David MacKay (2003) · Free full text. Chapter 5 does Kraft and Huffman properly, including why the rounding overhead is under a bit; Chapter 6 does arithmetic coding with worked intervals.
• Arithmetic Coding for Data Compression — Witten, Neal and Cleary, CACM 30(6) (1987) · The tutorial that made arithmetic coding practical, with the C implementation. Read it if you want to actually build the thing that turns a predictor into a compressor.

Exercises

1. Audit a code with Kraft. Compute Σ 2^(−ℓᵢ) for the robot code (should be exactly 1), then for the naive two-bits-each code (also 1 — flat codes spend the budget too, just badly), then for the proposed lengths 1, 2, 2, 3. A good answer states the sum, says whether a prefix code with those lengths can exist, and — for any list with slack left over — names which code word could be shortened and by how much.
2. Run the coin-flip test. Take a plain text file and its gzip. Strip gzip's 10-byte header and the 8-byte trailer, then compute, for the remaining payload and for the plain text: the fraction of 1 bits, and the four 2-gram frequencies. A good answer reports both sets of numbers, notes that the text is wildly biased and the payload is close to uniform, and uses H₂(½+ε) ≈ 1 − 2ε²/ln 2 to convert whatever residual bias you measure into an estimate of the bits still recoverable — plus an honest caveat that a bias measured on the same file you are testing is not held-out evidence.
3. Buy back the fraction. For the uniform 3-symbol source, reproduce the table above: run Huffman on the 3 symbols, then on the 9 pairs, then on the 27 triples, and confirm 1.66667, 1.61111, 1.60494 bits per symbol against log₂3 = 1.58496. A good answer reports the length multiset at each block size, verifies Kraft is tight in each case, and states the block size at which the overhead first falls below 0.01 bits per symbol.