Recap: what makes a code optimal

Transcript: this stretch, timestamped

Part 2 of the series opens on a magic trick — gzip reconstructing the family tree of European languages — and then stops to reload. This stretch is that reload: Part 1's entire argument compressed into two minutes, so a viewer arriving cold has the one formula they need. A recap states the true thing quickly and leaves the reader no scars from having earned it, so this page restates the result and then does the part a recap cannot — shows why it is forced rather than chosen, and names the two soft spots Grant papers over. Both are load-bearing. The next page, defining cross-entropy, pushes on the second until it breaks.

Outline, with timestamps

• 03:02 — Reload: cross-entropy is easiest to motivate through bit encodings, so back to bits we go.
• 03:08 — The frame from Part 1: a message is a sequence of symbols drawn from a distribution, and those probabilities set a hard limit on compression.
• 03:38 — The toy world returns: four robot instructions with probabilities ½, ¼, ⅛, ⅛, and the code that costs 1, 2, 3, 3 bits.
• 04:09 — Generalization: an optimal code spends −log₂ p bits on a symbol of probability p, which is really "how many halvings to get down to p".
• 04:39 — Shannon's name for that quantity is information content — and the admission that it is usually not a whole number.
• 05:11 — The rescue: information adds over a message, and an optimal encoding of the whole message is about that total, so fractional bits are real.

03:02 · Why the video restarts here

Cross-entropy shows up in two places that look nothing alike: the theory of compression, and the loss function that trains language models. Grant builds it from the compression side first, because that is where it has a meaning you can count — bits down an actual wire — and only then reveals that the training objective is the same object in different clothes. But that requires Part 1 to be in the reader's hands, and Part 1 is a half-hour video. Hence this recap. Read it as the minimum viable prerequisite; everything below is unpacked properly across P2, P3, P4 and P6.

03:38 · The toy world, with every number on the table

The running example is a stream of instructions to a distant robot, one of four: up, down, left, right, and they are not equally likely. Up is sent half the time, down a quarter, left and right an eighth each — a biased random walk, and that bias is exactly what a compressor eats. The code lengths come out as clean integers only because every probability is a power of two, which is why this example was chosen. The whole thing, arithmetic included:

Two numbers in that table deserve staring at. The fifth column sums to 1.75: that is the average cost per instruction, against the 2 bits a fixed-width code would spend, a 12.5% saving bought entirely from knowing the bias. The last column also sums to exactly 1, and that is not a coincidence — it is the budget being spent to the last cent, which is the next section.

04:09 · The one line worth memorizing

Strip away the robot and the rule is: an optimal code spends log₂(1/p) bits on a symbol of probability p. Written as −log₂ p it looks like an arbitrary bit of algebra with a minus sign bolted on; written as log₂(1/p) it is a count of halvings — how many times do you have to halve 1 before you get down to p? For p = ⅛ the answer is three, and the code word is three bits long. Grant makes the same point by wishing the field had picked a different base:

"I kind of wish that history had unfolded in such a way that we call it the log base 1 half of the probability, since it's really just asking how many times do you chop things in half to get down to a certain amount."— Grant Sanderson, 04:09

He is right on the mathematics as well as the pedagogy: log base ½ of p equals log₂(p) / log₂(½) = −log₂(p). Same number, no minus sign to lose. Shannon's name for it, coined in the 1948 paper, is the information content (or surprisal) of the event (04:39). Average it over the distribution and you get entropy, H(p) = Σ p(x)·log₂(1/p(x)) — the 1.75 in the table. Why it has to be a logarithm and not some other decreasing function is P4's subject; the one-line version is that independent surprises must add, and the logarithm is the only thing that turns multiplied probabilities into added bits.

04:09 · Why the floor cannot be cheated

Grant asserts optimality here rather than proving it, which is correct for a recap and unsatisfying for a reference card, so here is the argument in full. (This section is my addition — the theorem names are standard, Grant does not use them in this stretch.) The constraint that does the work is Kraft's inequality (Kraft, 1949; extended by McMillan in 1956 to every uniquely decodable code, not just prefix-free ones, which is why insisting on prefix-freeness costs you nothing). Think of a code word of length ℓ as claiming every infinite bit string that starts with it — a slice of size 2^(−ℓ). Prefix-freeness says the slices do not overlap. So they must fit inside 1.

Kraft's inequality — for a prefix-free binary code with word lengths ℓ₁…ℓₙ:

    Σᵢ 2^(−ℓᵢ)  ≤  1        (and any lengths obeying it can be realized)

Minimize the expected length  L = Σᵢ pᵢ·ℓᵢ  against that budget:

    ℓᵢ = log₂(1/pᵢ)    ⇒    L = Σᵢ pᵢ·log₂(1/pᵢ)  =  H(p)

Nothing else does better. For ANY qᵢ ≥ 0 with Σᵢ qᵢ ≤ 1, concavity of log gives

    Σᵢ pᵢ·log₂(qᵢ/pᵢ)  ≤  log₂( Σᵢ pᵢ·(qᵢ/pᵢ) )  =  log₂( Σᵢ qᵢ )  ≤  0

    ⇒   Σᵢ pᵢ·log₂(1/qᵢ)   ≥   Σᵢ pᵢ·log₂(1/pᵢ)   =   H(p)

That last line is Gibbs' inequality, proved in one step from Jensen's. Read it slowly, because it is the whole rest of the video in embryo: the left-hand side is what you pay when your code was built for q and reality is p; the right-hand side is entropy; and the inequality says the mismatch is never free and is zero only when q = p. That left-hand side already is cross-entropy. P9 gives it the name.

04:39 · Caveat one: log₂(1/p) is almost never a whole number

The toy example works because ½, ¼, ⅛, ⅛ are powers of two. Change one probability to ⅓ and the ideal length becomes log₂ 3 ≈ 1.585 bits, and you cannot emit 1.585 bits. Any code that maps one symbol to one string of bits must round up, and rounding up is a real cost. The standard guarantee — the Shannon source coding theorem, sharpened by Huffman's construction — is that the best per-symbol code lands somewhere in H(p) ≤ L < H(p) + 1: at worst one wasted bit per symbol, which for a low-entropy source can be a disaster.

The fix is to stop coding symbols one at a time. Code blocks of n symbols as single super-symbols and the wasted bit is amortized over n, so the overhead falls like 1/n. Three fair-die symbols, each of probability ⅓, make the point concretely:

Arithmetic coding takes this to its limit by never building a code book at all: it encodes the entire message as a single number in [0, 1), narrowing the interval by a factor of p at each symbol, and finishes within about two bits of the message's total information content regardless of length. That is what Grant is gesturing at when he says information adds over a message and the encoding is approximately that total:

"So fractional information really does have a very real meaning here."— Grant Sanderson, 05:11

Be blunt about the logical status of this, because it is where the subject stops being about code books. Entropy is not the length of any code you can write down; it is the limit that block and arithmetic coding approach, and it is the right thing to measure precisely because it ignores the integer bookkeeping of any particular encoder.

05:11 · Caveat two: the distribution has to come from somewhere

Every sentence above starts with "given the probabilities". Grant grants himself the distribution — the space agency told us the robot's bias — and in the toy world that is fair. Out in the world nobody hands you p. You estimate it from a sample, or you assert it from a model, and either way the thing you actually build your code from is some q that is not p. Worse, the decoder needs the same q, so a fully honest accounting also charges you for transmitting the model itself — the idea that becomes two-part codes and minimum description length. (That last connection is my addition; Grant does not raise it here.)

05:11 · The question Part 2 turns on

Combine the two caveats and the rest of the video takes shape. Coding is optimal relative to a distribution; the distribution is a guess; so the interesting quantity is not "how many bits does an optimal code use" but "how many bits does a code built for q use when the data actually follows p?" That number has a name and a formula, and Gibbs' inequality above already told us it can only be larger than H(p). Grant answers it in the very next breath by re-aiming the robot: the space agency rotates the mission so that right becomes the common instruction, the old code stays bolted into the hardware, and the average cost climbs from 1.75 to 2.625 bits per instruction. That excess — where it comes from, why it is asymmetric in p and q, and why it is the loss function used to train every large language model — is P9 onward.

Where people get stuck

"Why does the most likely symbol get the shortest code?" Because you pay for a code word every time you send it. Length is a cost and probability is how often you pay it, so the product p·ℓ is what matters and you want the big p multiplied by the small ℓ. In the table above, "up" and "down" each contribute the same 0.5 bits to the average for exactly opposite reasons.

The minus sign. −log₂ p and log₂(1/p) are the same number, and the second form is the one to hold in your head because it is visibly non-negative for p ≤ 1. If you ever compute a negative number of bits, you have dropped a sign or fed in a probability greater than one. The sign of the sum is the one thing to check before anything else: H(p) ≥ 0 always.

"1.75 bits per symbol" does not mean any message costs a fraction of a bit. It is an average over a long stream. A single "up" costs one whole bit; a thousand-instruction message costs about 1750 bits. Averages over symbols are allowed to be fractional in the same way that a household can have 2.3 children.

Entropy is a property of the distribution, not of the data. A specific file does not "have" an entropy; a source does. And the entropy you compute depends entirely on the model you compute it under. English text scored as independent letters comes out around 4.1 bits per character; scored with real context — which is what Shannon's 1951 experiments measured, and what a language model does — it drops to roughly 1 bit per character. Same text, different p, wildly different floor. That is not a paradox; it is the whole game.

Going deeper, verified

• Reinventing Entropy — Compression is Intelligence, Part 1 — 3Blue1Brown · The full version of everything this page compresses; Grant links it from the description of Part 2.
• A Mathematical Theory of Communication — Claude Shannon (1948) · The source. Section 6 defines entropy; Theorem 9 is the source coding theorem that makes H a floor rather than a heuristic.
• Kraft–McMillan inequality — reference article · The budget constraint behind the whole page, including McMillan's 1956 result that unique decodability buys you nothing over prefix-freeness.
• Information Theory, Inference, and Learning Algorithms — David MacKay (2003) · Free full text. Chapter 5 does symbol codes and Kraft properly; Chapter 6 does arithmetic coding, with the model-is-a-compressor framing made explicit.
• An Introduction to Arithmetic Coding — Glen Langdon (1984) · How you actually cash in fractional bits: one interval, one number, no code book.

Exercises

1. Check the floor by hand. Take the four-symbol distribution ½, ¼, ⅛, ⅛ and try to beat 1.75 bits per symbol. Enumerate every assignment of prefix-free lengths whose Kraft sum is ≤ 1 — there are not many — and compute Σ p·ℓ for each. A good answer shows a specific alternative (say lengths 2, 2, 2, 2, or 1, 3, 3, 3) and its average, and states which constraint stopped you from doing better.
2. Reproduce the block-coding table. For a uniform source over three symbols, build the Huffman code for blocks of n = 1, 2, 3 and confirm the bits per symbol are 1.6667, 1.6111 and 1.6049 against H = log₂ 3 = 1.5850. A good answer also reports the Kraft sum at each n (it should be exactly 1) and extrapolates where n = 6 would land.
3. Measure a real floor, twice. Take a few hundred kilobytes of English prose. Compute the order-0 entropy from the character histogram, then the order-2 conditional entropy H(x | previous two characters). Compare both to what gzip actually achieves on the same file, in bits per character. A good answer explains why gzip beats the order-0 number and why it does not reach the context-conditioned one — and says which of the three is "the entropy of English".