The information in language: Shannon's guessing game

Transcript: this stretch, timestamped

P04 landed the definition: the information of an outcome with probability p is log₂(1/p) bits, and in a perfect code that is exactly how many bits its code word gets. That was proved on a toy — a robot taking four moves with probabilities ½, ¼, ⅛, ⅛, all of them perfect powers of two, all of them independent. Real signals are not like that. This stretch of the video is the bridge from the toy to the thing Shannon actually cared about, natural language, and it is where the series earns its title: you cannot put a number on the compressibility of English without committing to a model of English, which is to say without committing to something that looks a great deal like understanding. P06 takes the same machinery and averages it, which is where entropy gets its formula.

Outline, with timestamps

• 17:40 — The toy was too clean: dyadic probabilities and independence both fail for language.
• 18:45 — Fractional bits demand a real interpretation. No letter gets a code word 4.19 bits long.
• 19:18 — The chain rule: a message's probability is a product of conditionals.
• 19:50 — Logs turn that product into a sum, so information adds along the message.
• 20:51 — The load-bearing question: where do those conditional probabilities come from?
• 21:23 — Shannon's first answer, n-gram tables scraped from books — and why they break.
• 22:24 — The guessing game with Betty Shannon; the reduced text; the identical-twin decoder.
• 23:29 — The 1951 redesign: record how many guesses, convert guess counts into bits.
• 24:00 — What he was really doing: probing a black-box model of language. We now build those.

Two things the robot example got for free

Go back to the moon robot and notice which conveniences were doing the work. One: every probability was a power of two. ½, ¼, ⅛, ⅛ give informations of 1, 2, 3, 3 bits — whole numbers, so a prefix code hit the bound exactly. Two: successive instructions were independent, so the distribution never changed and one fixed code book served the whole stream.

Language breaks both, and it breaks the second one much more violently than the first (18:13). The probability that the next character is u is small in general and close to 1 immediately after q. The probability that the next character is a space depends on how many letters you are into the current word. Every distribution in the stream is a different distribution, conditioned on everything already written. That is not a wrinkle to be smoothed away — it is the entire source of compression. A code that ignores context is leaving almost all of the redundancy on the table.

The first failure, non-dyadic probabilities, is the one Grant foregrounds visually: run a small character-level language model over a phrase, take −log₂ p of each letter's predicted probability, and you get numbers like 4.19 and 0.13 (18:45). The vague reading is easy — surprising letters cost more. The exact reading is the thing to nail down, because there is obviously no code word that is 4.19 bits long, and there is certainly no code word that is a thin sliver of a bit.

The chain rule, and why the logarithm is the right lens

The resolution is that fractional information is a statement about whole messages, not about individual code words. Write a message as a sequence of symbols x₁ x₂ … xₙ. Its probability factors — this is just the definition of conditional probability applied repeatedly, the chain rule (19:18):

P(x₁ x₂ … xₙ) = P(x₁) · P(x₂ | x₁) · P(x₃ | x₁x₂) · … · P(xₙ | x₁ … xₙ₋₁)

Now take the information of the whole message and watch the logarithm do its one trick (19:50):

I(x₁ … xₙ) = log₂( 1 / P(x₁ … xₙ) )
           = Σ  log₂( 1 / P(xₜ | x₁ … xₜ₋₁) )
            t=1..n

Products become sums. The per-letter numbers on screen are not code word lengths; they are addends. The message as a whole has an information content that is a perfectly ordinary real number, and Part 3 of the trilogy exhibits an algorithm — arithmetic coding — that encodes the passage in within a bit or two of that total, once, at the end. The rounding happens a single time for the whole message rather than 300 times for 300 letters, which is precisely why the fractional bookkeeping is worth doing.

This is the payoff Grant flags at 20:21: work one level of abstraction above bits, where information is continuous and additive, and cash out into integers only at the boundary with real hardware.

Whose probabilities? Entropy is defined relative to a model

Everything above assumed the conditional probabilities were handed to you. For the robot they were, by construction. For English, nobody hands them to you — and it is not even clear what it would mean for them to exist (20:51).

"All of this hinges on the question of how you know the probabilities for each successive letter."— Grant Sanderson, 20:51

Shannon's first attack was pure statistics (21:23): scan books, count what follows every occurrence of th, and use those frequencies as the conditional distribution. That gives the N-gram entropies F₀, F₁, F₂, F₃, …, where F_N is the conditional entropy of the next letter given the previous N−1. The true entropy of the language is the limit H = limₙ F_N, and the sequence is non-increasing: more context can only help.

The numbers below are from Shannon's 1951 paper, computed on a 26-letter alphabet and again on 27 symbols with the space included. I checked each one against the paper.

Read that column top to bottom and the point of the whole series is sitting right there: the number goes down as the model gets better, and nothing in the procedure ever tells you that you have reached the bottom. Every model you can build gives you an upper bound on the entropy of the source and never a lower one. (That asymmetry has a name Grant has not introduced yet — it is Gibbs' inequality, the fact that cross-entropy is at least entropy, and it is exactly what P08 onward is about. Flagging it as my addition.)

And the n-gram route hits a wall (21:53). To estimate P(next | previous 20 letters) by counting, you need to have seen that 20-letter string, and essentially every 20-letter string in this sentence has never appeared in any corpus. The counts are all zero. Worse, this is not a failure at the margins — long contexts are precisely where prediction is easiest and where the compression is, so the method fails hardest exactly where the payoff is largest.

The guessing game: encode the rank, not the letter

So Shannon stopped trying to build the model and went looking for one that already existed. The story Grant tells at 22:24: he opened a book and asked his wife Betty to guess the text one letter at a time, writing a dash when she was right and the true letter when she was wrong. The result is a reduced text — visibly shorter, and yet, he argued, carrying the same information.

The argument for "same information" is a decoding argument, and it is worth spelling out as an induction because it is the skeleton of every predictive compressor ever built. Fix a deterministic predictor R that maps a context to a ranked list of the 27 candidate next symbols, best guess first.

ENCODE:  for t = 1 … n
           order ← R(x₁ … xₜ₋₁)        # rank the candidates
           emit rₜ = position of xₜ in order

DECODE:  for t = 1 … n
           order ← R(x₁ … xₜ₋₁)        # SAME context, already decoded
           read rₜ ;  xₜ ← order[rₜ]

Two properties make this a legitimate code, and neither of them is "the predictor is good".

• Causality. The predictor at step t is fed only x₁ … xₜ₋₁, which the decoder has already reconstructed. The induction closes: if the decoder is correct through step t−1, it builds the identical ranked list and recovers xₜ.
• Bijectivity. For a fixed context, letter ↔ rank is a bijection on 27 items. Nothing is discarded; this is a re-encoding, not a lossy summary.

Grant's "identical replica of his wife" (22:57) is standing in for that shared deterministic predictor — and it is also the weak point of the first experiment, since a person does not guess the same way twice. Shannon's patch: ask the subject, for every possible N-gram, to write down their full ranked list once. That frozen table is deterministic, and the human is out of the loop.

Here is the crucial reframing. The reduced text is a stream over a new alphabet — the numbers 1 through 27 — with wildly skewed statistics: rank 1 is overwhelmingly common, high ranks are rare. All of the messy context-dependent structure of English has been pushed into the predictor and converted into a simple, context-free imbalance in the rank stream. A bad predictor still gives you a valid code, just one whose rank stream is nearly uniform and therefore incompressible. Prediction quality shows up entirely as skew in the rank distribution. That single sentence is the "prediction and compression are two sides of the same coin" claim, made concrete.

From guess counts to bits: what the 1951 paper actually measured

Dashes tell you a guess was right but not how nearly right the wrong ones were. The redesign (23:29) records the full rank: the subject keeps guessing until correct, and Shannon writes down the guess number. In one published sample of 102 symbols, the subject was right on the first guess 79 times, on the second 8 times, on the third 3 times, twice each on the fourth and fifth, and needed more than five guesses only 8 times. Roughly four characters in five were free.

Let qᵢ be the frequency of rank i in the reduced text. Shannon's bounds are:

  27                                          27
  Σ  i · (qᵢ − qᵢ₊₁) · log₂ i   ≤   F_N   ≤  − Σ  qᵢ · log₂ qᵢ
 i=1                                         i=1

The upper bound is a two-line argument. The rank stream is a symbol-by-symbol bijective recoding of the text, so it has the same entropy rate; and the entropy rate of any process is at most the plain entropy of its marginal distribution, because conditioning cannot increase entropy. So the zeroth-order entropy of the rank frequencies already bounds English from above — no modeling of the rank stream required. The lower bound is the harder half: the rank frequencies alone do not pin down the underlying conditional distributions, so Shannon asks which system of conditionals consistent with those frequencies has the least entropy. The answer is a mixture of uniform distributions — put weight i·(qᵢ − qᵢ₊₁) on "uniform over the top i candidates" — whose entropy is the left-hand sum. He notes honestly that this half is proved for an ideal predictor, while human guessers are not ideal, and argues the two errors roughly cancel.

Run those formulas on the 102-symbol sample above and you get roughly 0.7 and 1.2 bits per character (my calculation, treating the eight beyond-rank-five guesses as a lump at rank 6 — spreading them out raises the upper bound and barely moves the lower one). Shannon's own smoothed table, from 100 samples with 100 letters of context, gives lower 0.6, upper 1.3 bits per character, against 4.76 for the same 27 symbols chosen at random. His summary in the abstract is "of the order of one bit per letter", a redundancy of roughly 75%; Grant quotes about one bit per character at 30:21, which matches.

One citation note. Grant calls this "his 1950 paper" (22:57). The manuscript was received in September 1950, but it was published in the Bell System Technical Journal vol. 30 in January 1951 and is universally cited as Shannon 1951 — worth knowing if you go looking for it.

The same construction, with a machine in the chair

The last beat of this chapter is the one the whole trilogy hangs on (24:00).

"He wasn't just doing pure data analysis looking through books. He was trying to probe at an underlying model of language, namely the interviewee's brain."— Grant Sanderson, 24:00

Swap the human for a neural network and nothing about the construction changes. The network is a deterministic, causal, context-conditioned distribution over next symbols; encoder and decoder both run it; you code the outcome against its predictions. Modern systems code against the probabilities directly with arithmetic coding rather than against ranks, which is strictly better — ranks throw away the difference between a 0.99 first guess and a 0.35 first guess — but the correctness argument is the identical induction.

Two verified data points for scale, and one caveat about comparing them. Working with a 27-symbol normalization of Pride and Prejudice (692,508 characters, letters and spaces only), I measured the following on this machine:

Reproducing Shannon's 1951 letter-frequency numbers to within 0.02 bits off a single novel is a nice sanity check on the whole apparatus. And note where the general-purpose compressors sit: comfortably below the digram model, comfortably above a human reader.

For the machine side, Delétang et al. (2023) evaluate large models as literal lossless compressors on enwik9. In their Table 1, gzip reaches 32.3% of raw size (2.58 bits per byte) and Chinchilla 70B reaches 8.3% (0.66 bits per byte) — below Shannon's human estimate, on the same order. The caveat is real: enwik9 is raw Wikipedia markup measured per byte, not clean printed English measured per letter, so the two numbers are cousins, not twins. And the same table's "adjusted" column, which charges the compressor for shipping the model itself, sends Chinchilla's 8.3% past 14000% — a useful antidote to any claim that a language model has "beaten" the entropy of English.

Where people get stuck

"The entropy of English is 1 bit per character." It is not a constant of nature; it is a measurement of one model class on one kind of text with one alphabet. Shannon's number is 27 symbols, literary English, ~100 letters of context, one era, a handful of subjects, 100 samples per column. Bits per letter, bits per byte, and bits per token are three different units, and papers quietly switch between them.

"A letter can't cost 4.19 bits." Correct, and nobody claims a code word of that length exists. Information is additive over a message; the sum is a real number; the rounding to whole bits happens once, for the message, not once per symbol. Arithmetic coding is the constructive proof, and its overhead is a couple of bits for the entire passage.

"Encoding the rank feels like cheating — where did the dictionary go?" Nowhere: both sides must hold the predictor, and it is not free. For a fixed predictor amortized over a long stream, the cost per symbol vanishes; for a 70-billion-parameter model and a one-gigabyte file, it does not, which is what the "adjusted compression rate" accounting above measures. The principled version of this bookkeeping is minimum description length: total cost = model size + data cost under the model.

"Better models keep giving lower numbers — when do we stop?" You do not get to stop, and that is the philosophical content of the chapter. Any model gives an upper bound on the source entropy; nothing certifies you have reached the floor. Measuring the entropy of a language is therefore an open-ended search for a better model of it, which is why the compression question and the intelligence question refuse to come apart.

Going deeper, verified

• Prediction and Entropy of Printed English — C. E. Shannon, Bell System Technical Journal 30 (1951), pp. 50–64 · The primary source for everything on this page: the guessing protocol, Table I of guess frequencies, and the bounds derivation. Short and readable.
• Visual Information Theory — Christopher Olah (2015) · Linked in the video description as the origin of Grant's way of drawing entropy; the best visual companion to the next few pages.
• A Mathematical Theory of Communication — C. E. Shannon (1948) · Where F_N, redundancy, and the ≈2.3 bits-per-letter estimate come from, and where the noiseless coding theorem of P06 lives.
• Language Modeling Is Compression — Delétang et al. (2023) · Runs Shannon's construction with modern models: arithmetic coding driven by Chinchilla, with the raw-versus-adjusted compression accounting quoted above.
• Large Text Compression Benchmark — Matt Mahoney · The long-running leaderboard for compressing enwik9, where predictive-model compressors have been quietly grinding toward Shannon's estimate for two decades.

Exercises

1. Rebuild Shannon's table. Take any public-domain novel, lowercase it, keep only a–z and space, and collapse runs of whitespace. Compute F₁ = −Σ p(c)·log₂ p(c) and F₂ = H(digrams) − F₁. A good answer reports both numbers to two decimals, states the character count, and compares against Shannon's 27-symbol 4.03 and 3.32. You should land within about 0.1 bits; if you are near 4.7 you forgot to include the space, and if you are near 4.2 you excluded it.
2. Compute the bounds by hand. Shannon's 102-symbol sample gave guess-rank counts 79, 8, 3, 2, 2, with 8 symbols needing more than five guesses. Normalize to frequencies qᵢ and evaluate both sides of Σ i(qᵢ − qᵢ₊₁)log₂ i ≤ F_N ≤ −Σ qᵢ log₂ qᵢ. A good answer gets roughly 0.7 and 1.2 bits per character, and says explicitly what assumption it made about the eight tail symbols and which direction that assumption biases each bound.
3. Build the rank codec. Train a trigram table on one book, then encode a second book as a stream of guess-ranks under that predictor. Gzip the rank stream and gzip the original text, and compare bits per character. A good answer reports both numbers, confirms that decoding reproduces the input exactly, and states the causality invariant that makes the decoder work — that the predictor at step t sees only symbols already emitted.