The warmup: four instructions, three students, and prefix codes

Transcript: this stretch, timestamped

The previous page set up the claim that compression and prediction are the same problem wearing different clothes. This page is where the series stops gesturing and starts computing. Grant deliberately picks a toy so rigged that the arithmetic comes out in whole numbers: four symbols, probabilities that are all powers of ½, and a fiction of independence. Everything that will later be said about entropy, about fractional bits, and about the compressibility of English is visible in miniature here, minus the mess. By the end of this stretch you have a code that beats the naive one, a structural reason it decodes unambiguously, and an unexplained coincidence — code-word shares that match probabilities exactly — which is the hook for the next page.

Outline, with timestamps

• 03:28 — Setup: a robot on a faraway moon, driven by instructions sent from Earth.
• 03:38 — The distribution: up ½, down ¼, left ⅛, right ⅛, and every instruction independent of the last.
• 04:08 — The puzzle: bits are slow and costly to send. Three students take a crack at it.
• 04:38 — Student one, straightforward: two bits each, decoded by chopping the stream into pairs.
• 05:41 — Student two, clever: 0 / 10 / 110 / 111, and the weighted sum that gives 1.75 bits.
• 06:13 — The saving shown on an actual sampled stream, not just in expectation.
• 07:13 — Decoding from the robot's side: read bits until they form a complete code word.
• 07:47 — The rule that makes it work: no code word may be a prefix of another. A fifth code word 100 would break it.
• 08:17 — The name (prefix-free code / prefix code) and the diagram of all binary strings.
• 09:20 — Every string is a prefix of everything above it, so choosing 0 for "up" consumes half the space.
• 09:50 — ½ + ¼ + ⅛ + ⅛, nothing left over — and the shares equal the probabilities.
• 10:23 — "Better" is not "best": the third student arrives, and the argument moves to the next page.

A rigged little problem, and why the rigging is the point

The scenario is an uplink budget. A robot wanders the surface of a moon; from Earth you send it one of four movement instructions at a time, over a channel where every bit is expensive. The instructions are not equally likely — half of what you send is "up", a quarter is "down", an eighth is "left", an eighth is "right" — and Grant adds a second simplification: each instruction is drawn independently, with no dependence on what came before.

Independence is what makes a per-symbol code the right object at all. If instruction n+1 were predictable from instruction n, encoding each symbol in isolation would leave compression on the table, and you would want a conditional distribution instead of one fixed one. Language, the real target of the series, violates this badly — which is why the general case needs a heavier machine later.

The second rigging is subtler: every probability here is a power of ½. Call such a distribution dyadic (my term for it, not Grant's — it is the standard one). That choice guarantees that the ideal number of bits for each symbol, log₂(1/p), is a whole number: 1, 2, 3, 3. In the toy, "the best possible code" is achievable exactly rather than approached in a limit. The moment probabilities stop being powers of ½ — as they do for English letters — the ideal per-symbol cost becomes fractional, no code word can be 4.19 bits long, and the whole framework has to be lifted from single symbols to long messages. Grant is spending this seven minutes buying an example where that complication is switched off.

Student one: two bits, flat

The straightforward answer is a fixed-length code: 00 = up, 01 = down, 10 = left, 11 = right. Two bits, always. In general a fixed-length binary code for n symbols needs ⌈log₂ n⌉ bits, and with n = 4 that is exactly 2.

This is not a strawman; it is the sane engineering default, and it has one virtue the clever code will have to earn back. Decoding is not just trivial but positional: bits 2k and 2k+1 are always one instruction, so you can seek into the middle of the stream and never need to have read the beginning. Its defect is equally clear — it treats "up" and "right" as equally deserving of bandwidth even though you send "up" four times for every "right".

Student two: spend the short words where the probability mass is

The clever student's code lets the code words differ in length: a single bit 0 for up, two bits 10 for down, three bits 110 for left, three bits 111 for right. The cost of a code that varies in length is no longer a single number, so you ask for the expected cost per instruction — the weighted sum of the lengths, weighted by how often each length is actually paid.

So the average length is L = Σ p(x)·l(x) = 1.75 bits, against the flat code's 2.00 — a saving of a quarter of a bit per instruction, or 12.5% of the uplink. The trade is explicit in the table: the clever student pays an extra bit for left and right relative to the flat code, and those two rows cost 0.75 bits between them instead of 0.5. That penalty is more than repaid by the up row, which drops from 1.0 to 0.5. You lose on the rare symbols and win, bigger, on the common one.

Grant then shows the saving on an actual sampled stream, not only in expectation — worth pausing on, because 1.75 is an average and a short message can come out longer than the flat code would have made it. Four "right"s cost 12 bits here and 8 there. The guarantee is asymptotic, and it is about the source, not any single transmission.

An addition Grant holds back until later: compute Σ p·log₂(1/p) for this distribution and you get ½·1 + ¼·2 + ⅛·3 + ⅛·3 = 1.75 — the same number. That is the Shannon entropy of the source, and the fact that it coincides exactly with the clever student's average length is not luck; it is what "dyadic distribution" buys you. Hold that coincidence; the series spends the next twenty minutes explaining it.

Why the robot never needs a separator

Variable-length code words raise an obvious alarm, and Grant raises it deliberately: if instructions have different lengths, how does the receiver know where one ends and the next begins? There is no comma in the bitstream, no length header, no delimiter — the robot gets an undivided run of ones and zeros.

Take the receiver's point of view and walk a stream one bit at a time. Read 1: not a complete code word, but it rules out "up", so you are somewhere among down / left / right. Read 0: the accumulated 10 is a complete code word and nothing else starts that way, so emit "down" and reset. Read 0: complete on the spot — "up". Read 1, then 1: still ambiguous, still a live prefix of both 110 and 111. Read 0: 110, emit "left".

stream:   1 0   0   1 1 0   ...
          |___| |_| |_____|
          down  up    left

The decoding rule is one sentence: consume bits until what you hold is a code word, emit it, start over. That works if and only if you can never hold a code word while a longer one is still possible — that is, if and only if no code word is a prefix of another. Grant makes the failure concrete: add a fifth instruction with code word 100 and the scheme dies, because after reading 10 the receiver cannot tell whether it is finished (that was "down") or should keep reading (this is the new symbol). The stream stops being self-delimiting.

"It's known in the business as a prefix-free code, or what is confusingly synonymous, it's actually more commonly known as a prefix code."— Grant Sanderson, 08:17

He is right that the naming is unfortunate. "Prefix code" is shorthand for "prefix-free code" — a code in which no code word is a prefix of another. Both names are in wide use for the same object; the older literature also calls it an instantaneous code, which is the most descriptive of the three, because the defining property is precisely that the decoder can commit to a symbol the instant its last bit arrives, without lookahead.

The tree, and the budget it enforces

The diagram Grant draws is the space of all binary strings, layered by length: layer 1 is 0 and 1, layer 2 is 00 01 10 11, and so on, with everything beginning 0 stacked over the left half and everything beginning 1 over the right half, recursively. Structurally it is the infinite binary tree: a string is a path down from the root, left for 0 and right for 1, and every string is a prefix of exactly the strings sitting above it — its descendants.

                    root
                 0 /    \ 1
                  /      \
              [ UP ]      *
              1 bit    0 /   \ 1
              1/2       /     \
                   [ DOWN ]    *
                    2 bits  0 /  \ 1
                    1/4      /    \
                       [ LEFT ]  [ RIGHT ]
                        3 bits    3 bits
                         1/8        1/8

In this picture the prefix-free condition is one line: the code words must be leaves. Claiming a node forbids its entire subtree, since every descendant has that node as a prefix. So a code word of length l does not merely cost l bits to transmit — it claims a 2⁻ˡ fraction of the whole tree and takes it out of circulation. Short code words are expensive in exactly this currency: 0 for "up" eats half of all possible strings.

Add up what the clever student's four claims consume:

Σ 2⁻ˡ  =  2⁻¹ + 2⁻² + 2⁻³ + 2⁻³
       =   ½  +  ¼  +  ⅛  +  ⅛
       =   1        <-- budget exactly spent; nothing left over

The formal statement — my addition; Grant draws the picture but does not name the theorem — is Kraft's inequality. A binary prefix-free code with code-word lengths l₁, …, lₙ exists if and only if Σᵢ 2⁻ˡⁱ ≤ 1. It is due to Leon Kraft's 1949 MIT master's thesis; McMillan proved in 1956 that the same bound binds any uniquely decodable code, which is the deeper result — instantaneous decoding costs you nothing in achievable lengths. A code meeting it with equality, as this one does, is complete: every leaf is used.

The inequality is what turns "spend short words on common symbols" from a slogan into an accounting constraint. Lengths are not independently choosable. Shortening one code word by a bit doubles its claim on the tree, and something else has to give up room: from ⅛ + ⅛ = ¼, if you promote "left" to a 2-bit word it takes ¼ on its own and "right" has to move up a level, and you have paid a bit to save a bit. There is no free shortening anywhere in a complete code. That is the same "push the bump down and it pops up elsewhere" trade the third student will exploit on the next page, stated in advance and in exact form.

Huffman: the algorithm behind the clever student's guess

Grant presents this code as a stroke of cleverness rather than the output of a procedure, and does not name one. There is one, and it is worth knowing: Huffman coding (David A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the IRE, 1952) builds the optimal prefix code for a known symbol distribution, and does it greedily from the leaves up. Repeatedly take the two least probable nodes, merge them under a new parent whose probability is their sum, and repeat until one node remains; the depth a symbol ends up at is its code-word length.

start    1/2 (up)   1/4 (down)   1/8 (left)   1/8 (right)
merge    1/8 + 1/8 = 1/4      ->   1/2 · 1/4 · [1/4]
merge    1/4 + 1/4 = 1/2      ->   1/2 · [1/2]
merge    1/2 + 1/2 = 1        ->   root
depths   up 1 · down 2 · left 3 · right 3   ->  L = 1.75 bits

Run it on this distribution and you get lengths 1, 2, 3, 3 — precisely the clever student's code. So yes: what Grant shows is a Huffman code for this source. The hedge on "a" is real and small: Huffman fixes the multiset of lengths, not the bit patterns, since you may swap the 0 and 1 labels at any branch and, when probabilities tie, merge in either order. 1 / 01 / 001 / 000 is an equally valid Huffman code here. What is uniquely determined, and what optimality is about, is the average length 1.75.

Two caveats that matter later: Huffman is optimal only among codes that give each symbol a whole number of bits, and it meets the entropy exactly only for dyadic sources — in general it can overshoot by up to about a bit per symbol, painfully so when one symbol has probability near 1. It also assumes a fixed, known distribution. Arithmetic coding, which the third video builds toward, escapes both limits.

The coincidence, and the objection that opens the next page

Now put the two tables side by side. The share of the tree each code word claims is ½, ¼, ⅛, ⅛. The probability of each instruction is ½, ¼, ⅛, ⅛. They are the same numbers, and neither the tree nor the arithmetic knew about the other — the tree shares came from a geometric constraint on prefix-free strings, the probabilities came from the physics of the mission.

"And in fact, that tickling sensation of a relationship between data size and probabilities is exactly the founding insight for information theory."— Grant Sanderson, 09:50

Read the coincidence as an equation and you have the whole of the next stretch in embryo. If a symbol of probability p should claim exactly a p share of the tree, then 2⁻ˡ = p, so l = log₂(1/p) = −log₂ p. Under that allocation the average length becomes Σ p·log₂(1/p) — the expression that will be named entropy, arrived at not by definition but by asking how to spend a budget.

Grant refuses to let you cash that in yet. "Better than 2.00" is not "provably best": what rules out an exotic scheme that encodes long runs of instructions jointly and beats 1.75 on average? Nothing here does — this chapter argues about one fixed symbol-by-symbol code, and the question is about all codes. That is the third student's brief: the head-in-the-clouds one who reasons about what a perfect code must look like rather than building one. Their argument — random noise is incompressible, so perfect output must look like random noise — starts at this page's boundary and is the substance of the next.

Where people get stuck

"1.75 bits" sounds like a fractional bit is being sent. It is not. Every transmission here is a whole number of bits; 1.75 is an expected value over the source distribution, the way an average family size of 2.3 does not imply a fractional child. Fractional information per symbol becomes a genuinely meaningful quantity later, once the argument moves from single symbols to long messages — but in this chapter every quantity is an average of integers, and no code word is 1.75 bits long.

Confusing "prefix-free" with "no code word contains another". The condition is only about prefixes — the beginning. 110 contains 10 as a substring and that is completely fine; the decoder is reading left to right and never asks about interior matches. What is fatal is a code word that is an initial segment of another, because that is the case where the decoder has a complete symbol in hand and cannot tell whether to stop.

"Why not shorten several code words at once?" Because of the budget. It is tempting to think the tree has spare room somewhere. It does not, once the code is complete: ½ + ¼ + ⅛ + ⅛ is already 1, and any shortening pushes the sum above 1, which Kraft's inequality says is impossible for a prefix-free code. Shortening one word always forces another to lengthen, and on a source you have already matched, the trade is a net loss.

Assuming variable-length always wins. It wins here because the distribution is skewed. On a uniform source over four symbols, the Huffman code is the flat two-bit code, and any variable-length alternative does strictly worse in expectation. Variable-length coding buys you nothing without non-uniformity to exploit — which is the first quiet appearance of the series' thesis that compression is only possible where prediction is.

Forgetting that independence was assumed, not derived. Grant stipulates that each instruction is drawn independently of the preceding ones. Drop that and the per-symbol code stops being the right object entirely: a source that alternates up, down, up, down is fully predictable and compresses to nearly nothing, yet its symbol frequencies are ½ and ½ and any memoryless code would spend a bit per instruction. The whole difficulty of the language case is exactly this gap.

Going deeper, verified

• A Mathematical Theory of Communication — Claude E. Shannon (1948) · Linked in the video description. Sections 5–9 contain the noiseless coding theorem that the third student is groping toward; the prefix-code construction appears there as the "Shannon–Fano" style argument.
• Visual Information Theory — Christopher Olah (2015) · Grant credits this post in the description as the source of the way he visualises entropy; it develops the same "code words claim fractions of the space" picture at length, with better pictures than any textbook.
• A Method for the Construction of Minimum-Redundancy Codes — David A. Huffman (1952) · Four pages. The algorithm that produces the clever student's code, and the proof that no other prefix code does better on a fixed symbol distribution.
• A device for quantizing, grouping, and coding amplitude-modulated pulses — Leon G. Kraft (1949) · The MIT master's thesis where the inequality Σ 2⁻ˡ ≤ 1 first appears, in a context that has nothing to do with text compression.
• Kraft–McMillan inequality — Wikipedia · The cleanest short statement of both directions, including McMillan's 1956 extension to all uniquely decodable codes, with the counting proof.

Exercises

1. Check the budget, then break it — Verify Σ 2⁻ˡ = 1 for the lengths (1, 2, 3, 3). Then take the length vector (1, 2, 2, 3) and decide, without trying to build a code, whether a prefix-free code with those lengths can exist. A good answer computes ½ + ¼ + ¼ + ⅛ = 1.125 > 1, concludes no by Kraft, and then confirms it concretely: after spending 0 and two 2-bit words you have used the whole tree and there is no leaf left for the 3-bit word.
2. A non-dyadic source — Take p = (0.4, 0.3, 0.2, 0.1) over four symbols. Run Huffman by hand, write down the code words, and compute the average length. Then compute H = Σ p·log₂(1/p). A good answer gets lengths (1, 2, 3, 3) with L = 1.90 bits and H ≈ 1.8464 bits, and notices the 0.054-bit gap — the price of rounding each symbol to a whole number of bits, which is zero in Grant's rigged example and never zero here.
3. Write the decoder — Implement the clever student's code in twenty lines: an encoder mapping the four instructions to bit strings, and a decoder that walks the stream maintaining only a current node in the tree. Sample 10,000 instructions from (½, ¼, ⅛, ⅛), encode, decode, and confirm you recover the original. A good answer reports a measured bits-per-instruction close to 1.75, notes how far a single 10,000-symbol run deviates from it, and shows that inserting the rogue code word 100 as a fifth symbol makes the decoder ambiguous on a concrete stream.