Part 2: Shannon (1951) — The Guessing Game That Put English Near One Bit per Letter

Hey, welcome back to From Shannon to Transformers. This is Part 2. I will not waste your sec. Trust me.

At the end of Part 1 we hit a wall. Our counting model of English got better as we gave it more letters of context, and then it started lying to us. Push the order high enough and every context is one you have seen exactly once, the measured entropy collapses toward zero, and the model hasn't learned English. It has memorized Moby Dick.

Shannon hit the same wall. In 1948 he could only push his statistics out to about eight letters, which gave him roughly 2.3 bits per letter and about 50% redundancy. To go further you'd need tables of every 20-letter sequence in English, and no library on Earth has enough text to fill them.

So in 1951 he did something brilliant and a little bit lazy. He stopped counting. He took a machine that already knows the statistics of English extremely well, one that has been trained on decades of reading, talking and listening, and he made it play a game.

The machine was a person.

The paper is Prediction and Entropy of Printed English, Bell System Technical Journal, Vol. 30, No. 1, pp. 50–64, January 1951. It's 15 pages long, and it's the first time someone measured a language model by making it guess the next character. Sound familiar?

In this post:

• Why counting can't go past ~8 letters, and what Shannon got from words instead
• The guessing game: how it works and what the "reduced text" is
• The identical-twin argument: why your guesses are a compressed copy of the text
• The upper and lower bounds, built from guess counts (with code)
• Shannon's results: English at roughly one bit per letter, about 75% redundant
• Rebuilding the game in Python and letting an n-gram model play against Shannon's human
• The trap that catches everyone when they score a guesser
• How the guessing game became next-token prediction, and why prediction is compression

Tighten your seatbelt. This one has a twist in the middle.

---

1. Where counting runs out

Shannon opens the paper by redoing the counting approach properly, so let's look at his numbers first. He calls them F_N: the entropy of the next letter when you know the previous N − 1 letters. Bits per letter, two alphabets:

F0 is just log2 26 or log2 27: every letter equally likely. F1 uses letter frequencies, F2 digrams, F3 trigrams. If you ran the Part 1 script, these should look very familiar: our Moby Dick order-2 number was also 3.32.

Then he stops, because F4 and beyond needed more text than anyone could count by hand in 1950. You can't fill a table with 27^4 ≈ 530,000 rows from a few books, let alone 27^10.

The last row, F_word, is a cute workaround. Shannon uses the observation (Zipf's law) that the probability of the n-th most common English word is roughly 0.1/n. Add up the entropy of that distribution out to the point where the probabilities sum to 1 (around rank 8,727) and you get 11.82 bits per word. English words average 4.5 letters, so 11.82 / 4.5 ≈ 2.62 bits per letter. That's better than trigrams, but it still treats every word as independent of the one before it.

So the counting approach plateaus around 2–3 bits. The real question is what happens when you use all the context: a whole sentence, a whole paragraph. Counting can't answer that. Something else has to.

2. The guessing game

Here's the setup, and it's beautifully simple.

You give a person a passage they've never seen. They have to guess it one letter at a time (26 letters plus space). If they guess right, they move on. If they guess wrong, they're told the correct letter and they move on. Shannon writes down which letters they got right.

His example is the start of a passage from a book. The first line is the real text, the second is what Shannon called the reduced text: a dash for every letter guessed right, and the actual letter wherever the guess was wrong:

THE ROOM WAS NOT VERY LIGHT A SMALL OBLONG
----ROO------NOT-V-----I------SM----OBL----

Over the full passage of 129 letters, 89 (69%) were guessed right on the first try.

Look at where the misses are. The start of words: "ROO", "NOT", "V", "SM", "OBL". Once you have "ROO" after "THE", the M is almost free. Once you have "OBL", the "ONG" comes with it. The surprise in English isn't spread evenly. It sits at the start of words and at the start of new ideas, and the rest is filler you could predict with your eyes half closed. That's redundancy, and you can see it with your own eyes.

Then Shannon made the game more informative. Instead of one guess, the subject keeps guessing until they get the letter right, and you record how many guesses it took. A 1 means "right first time", a 5 means four wrong tries first. In one 102-symbol run, the subject got 79 right on the first guess, 8 on the second, 3 on the third, 2 on the fourth, 2 on the fifth, and 8 needed more than five.

Now the text has been turned into a sequence of numbers, mostly 1s. Keep that in mind, because the whole paper hangs on it.

3. The twist: your guesses are a compressed copy of the text

Here's the move that turns a parlor game into a measurement.

Imagine the subject has an identical twin: same brain, same reading history, same guessing behavior, letter for letter. You hand the twin only the sequence of guess numbers: 1 1 1 5 1 1 2 ....

The twin can rebuild the original text. They start guessing the first letter exactly as their sibling did. The sequence says "1", so their first guess is right, and they write it down. Next letter, also "1". Then "5": the twin makes their first four guesses, knows they're wrong, and writes down their fifth. Because the twins guess identically, the twin's fifth guess is exactly the letter the original subject landed on.

Did you get it? The sequence of guess numbers contains all the information in the text. It's an encoding. You can go text → numbers and numbers → text without losing anything, as long as you have the same predictor on both ends. Shannon points out you don't even need a twin: a complete table of the predictor's choices for every possible context would do the same job.

And here's why that matters. The guess-number sequence is mostly 1s. A sequence that's mostly 1s has low entropy, which means it can be compressed into very few bits. And since the text can be rebuilt from it, the text can't contain more information than it does.

That's the whole trick. You can't measure the entropy of English directly, but you can measure the entropy of the guess numbers, and that tells you about English.

4. Upper and lower bounds from guess counts

Let's make that precise. Shannon imagines an ideal predictor with N − 1 letters of context: it always guesses letters in order of their true conditional probability, most likely first. Call q_i the fraction of the time its i-th guess is the right one. So q_1 is the first-guess hit rate, q_2 the second-guess rate, and so on.

From those numbers he proves two bounds on F_N:

Upper bound:   F_N ≤ − Σ q_i · log2(q_i)
Lower bound:   F_N ≥ Σ i · (q_i − q_(i+1)) · log2(i)

The upper bound is the identical-twin argument turned into a formula. It's just the entropy of the guess-number distribution. If you can encode the text as guess numbers, the text can't carry more bits than the guess numbers do.

The lower bound is subtler. The guess numbers throw away information: they tell you the right letter was the predictor's 3rd choice, but not whether that choice was a coin flip or a near-certainty. Shannon shows that, for a fixed set of q_i, the predictor that's most uncertain still can't get the entropy below that expression. You don't need to memorize the proof. Read it as: "with this hit-rate profile, English has at least this much surprise left in it."

Concrete first, abstract second. Here are both bounds in code. Give it a list of guess numbers and it gives you the two bounds:

import math
from collections import Counter

def bounds(guess_numbers):
    """Shannon (1951), eq. 17: bounds on F_N from guess-number frequencies."""
    total = len(guess_numbers)
    freq = Counter(guess_numbers)
    q = [freq.get(i, 0) / total for i in range(1, 29)]       # q[27] = 0
    upper = -sum(p * math.log2(p) for p in q if p > 0)
    lower = sum((i + 1) * (q[i] - q[i + 1]) * math.log2(i + 1) for i in range(27))
    return upper, lower, q[0]

One sanity check that helps it click: with N = 1 (no context at all) the ideal predictor always guesses E, then T, then A, and so on in frequency order. The guess number is just the letter's frequency rank, so the upper bound becomes exactly the entropy of English letter frequencies, F1. Shannon's human got 4.03 at N = 1, the same as his counted F1.

5. What Shannon found

Shannon took 100 random passages of 15 letters from Jefferson the Virginian by Dumas Malone. For each one the subject guessed letter by letter, so the first letter was guessed with no context, the second with one letter of context, and so on up to 14. He also ran a test where the subject could see 100 letters of context first. Here are his bounds, in bits per letter:

(The table in the paper has every N from 1 to 15. The numbers bounce around a bit in the middle because each column is based on only 100 guesses.)

With 100 letters of context, English sits somewhere between 0.6 and 1.3 bits per letter. Shannon's summary: long-range effects "reduce the entropy to something of the order of one bit per letter," with a redundancy of roughly 75%.

Let that sink in. In 1948 he could only say "about half of English is predictable". Now, with context, about three quarters is. Out of 4.76 bits of possible choice per letter, you're only really making about one.

Two smaller results from the paper I love:

• Reverse prediction. He also had subjects guess text backwards, predicting the letter before the ones they could see. It felt much harder, but the scores were only slightly worse: on two 101-letter samples, 70 first-guess hits forwards versus 66 backwards. He notes that, in theory, F_N is the same whether you read the language forwards or backwards.
• Humans aren't ideal, and that's fine. The bounds are proven for an ideal predictor, and a human is a noisy one. Shannon argues the gap mostly works in the bounds' favor and says he's "reasonably confident" in both, apart from sampling error. Later work agrees with him: Cover and King (1978) replaced guessing with betting on the next letter, ran it on the same Dumas Malone book, and got about 1.3 bits per symbol, with 1.25 as their preferred estimate.

6. Rebuilding the game: an n-gram model vs. Shannon's human

Let's do what Shannon couldn't: put a machine in the subject's chair.

Our player is the counting model from Part 1, slightly upgraded. For each position, it ranks all 27 symbols from most to least likely using the longest context it has seen. Shorter contexts break ties and fill in letters it has never seen after that context. The rank of the correct letter is the guess number. Then we feed the guess numbers into bounds().

One important rule (you'll see why in the next section): we train on the first 90% of Moby Dick and play the game on the last 10%, text the model has never seen.

import math, re, sys
from collections import Counter, defaultdict

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "          # Shannon's 27 symbols

def clean(text):
    text = re.sub(r"[^A-Z]+", " ", text.upper())
    return re.sub(r" +", " ", text).strip()

def train(text, max_order):
    """counts[k][context] -> Counter of next letters, for contexts of length k."""
    counts = [defaultdict(Counter) for _ in range(max_order)]
    for i in range(len(text)):
        for k in range(max_order):
            if i - k < 0:
                break
            counts[k][text[i - k:i]][text[i]] += 1
    return counts

def ranking(counts, context):
    """The predictor's guesses, best first. Longest known context wins;
    shorter contexts break ties and fill in letters never seen after it."""
    guesses = []
    for k in range(min(len(context), len(counts) - 1), -1, -1):
        ctx = context[len(context) - k:] if k else ""
        for letter, _ in counts[k].get(ctx, Counter()).most_common():
            if letter not in guesses:
                guesses.append(letter)
    guesses += [c for c in ALPHABET if c not in guesses]
    return guesses

def play(counts, text, n):
    """Guess every letter of `text` knowing the previous n-1 letters.
    Returns the guess number (1 = right first time) for each letter."""
    return [ranking(counts, text[max(0, i - (n - 1)):i]).index(text[i]) + 1
            for i in range(n - 1, len(text))]

def reduced(text, guess_numbers):
    """Shannon's reduced text: '-' for a first-guess hit, else the letter."""
    return "".join("-" if g == 1 else c
                   for c, g in zip(text, guess_numbers)).replace(" ", "_")

# bounds() from section 4 goes here

if __name__ == "__main__":
    text = clean(open(sys.argv[1], encoding="utf-8").read())
    cut = int(len(text) * 0.9)
    seen, unseen = text[:cut], text[cut:]
    counts = train(seen, max_order=8)
    print(f"train {len(seen):,} symbols | test {len(unseen):,} symbols\n")
    print(" N   first-guess   upper   lower   (unseen text)")
    for n in (1, 2, 3, 4, 5, 6, 8):
        up, lo, hit = bounds(play(counts, unseen, n))
        print(f"{n:2}   {hit:10.0%}   {up:5.2f}   {lo:5.2f}")
    sample = unseen[1000:1060]
    g = play(counts, unseen[1000 - 7:1060], 8)
    print("\n" + sample.replace(" ", "_") + "\n" + reduced(sample, g))

Here's the actual output of python guess.py melville-moby_dick.txt (the same NLTK Gutenberg file as Part 1). It takes about 20 seconds:

train 1,053,316 symbols | test 117,036 symbols

 N   first-guess   upper   lower   (unseen text)
 1          19%    4.07    3.28
 2          29%    3.44    2.49
 3          40%    2.98    1.97
 4          50%    2.60    1.59
 5          55%    2.42    1.42
 6          58%    2.37    1.36
 8          58%    2.38    1.37

G_THE_SUN_TO_YE_YOKE_ON_THE_FURTHER_BILLOWS_HALLO_A_TANDEM_I
--T----U--TO_YE-YOK-_-N_T---FUR-----BI------HALL-_A_TAN----I

Put that next to Shannon's human:

For short contexts, a dictionary of letter counts plays exactly like a person. Up to four letters, the numbers are almost identical, which tells you that for local spelling patterns humans are basically n-gram machines too.

Then the model stalls. From N = 5 to N = 8 it flatlines at about 2.4 bits upper, 1.4 lower. Its first-guess rate is stuck at 58%. Giving it more context doesn't help, because most 7-letter contexts in the test text never appeared in training, so it falls back to shorter ones. (Note that 2.4 is right next to the "about 2.3 bits" Shannon got from his eight-letter statistics in 1948. Same wall, almost 80 years later.)

The human keeps going. With 100 letters of context, they're down near one bit. The human isn't using a bigger table. They're using things a table can't hold: grammar, meaning, what a sentence about whales is likely to say next. That gap, between 2.4 and ~1, is basically the story of the rest of this series.

Look at the reduced text too. Same pattern as Shannon's: the misses are at the start of words ("TO YE", "YOK", "FUR", "BI", "HALL", "TAN"), and the ends of words come almost for free.

⚠️ The trap that catches everyone

Run the exact same game, but let the model guess text it was trained on (the last 117,036 symbols of the training portion instead of the held-out 10%):

N	first-guess	upper	lower
1	19%	4.09	3.29
4	49%	2.60	1.60
8	71%	1.65	0.83

At N = 8 our little counting model suddenly scores 1.65 / 0.83, close to Shannon's human with 100 letters of context (1.3 / 0.6). Did we just build a human-level predictor in 60 lines of Python?

No. It's the Part 1 trap again in a different outfit. At N = 8, most 7-letter contexts in the training text appear only a handful of times, so the model "predicts" by remembering what came next in the book. On unseen text the same model is stuck at 2.38 / 1.37.

Shannon's design quietly avoids this. He picked passages the subject hadn't read. The moment your guesser has seen the test text (a famous quote, a song lyric, a benchmark that leaked into the training data), the guess numbers stop measuring the language and start measuring memory. Same thing applies to every LLM benchmark you read about today: if the test set leaked into the training data, the score is a memory test.

7. From the guessing game to next-token prediction

Let me connect this to the model you used this morning, because the line is surprisingly direct.

• The game is the training objective. An LLM is trained to do exactly what Shannon's subject did: see the context, predict the next symbol. The only differences are that the symbols are tokens instead of letters, and that the model outputs a full probability for every possible token instead of a ranked list of guesses.
• Probabilities beat rankings. That second difference is why we have two bounds instead of one number. A guess number tells you which choice was right but not how confident the predictor was. If the predictor gives you real probabilities, you don't need bounds: you just average −log2 p(actual next symbol) over the text. That's the cross-entropy loss from Part 1, and it's Shannon's upper-bound idea with all the information kept.
• The identical twin is a decompressor. The twin argument says "same predictor on both ends means the text can be rebuilt from a cheap encoding". Swap the twin for a copy of the same model, and swap guess numbers for arithmetic coding, and you have a real compressor. This is not a metaphor. A 2023 paper from DeepMind, Language Modeling Is Compression (Delétang et al.), opens with the line that predictive models "can be transformed into lossless compressors and vice versa," and shows a large language model (Chinchilla 70B) compressing ImageNet image patches to 43.4% of their raw size, beating PNG's 58.5%, even though it was trained mostly on text.

So when someone tells you an LLM "just predicts the next token", they're right, and they're describing Shannon's game. What they usually skip is that playing that game well enough is compression, and compression at that level requires a lot of knowledge about the world.

8. Let's be honest about what just happened…

We didn't measure the entropy of English today. Nobody has, not exactly. What Shannon gave us is a pair of bounds, from human guessing on one book, with most columns based on just 100 samples. "English is about one bit per letter" is a good summary, but it's a range (0.6 to 1.3 at N = 100), not a constant of nature. Be suspicious of anyone who quotes it with two decimal places.

What we did get is more useful than a number:

1. A way to measure a model you can't open. Shannon couldn't look inside a human brain, so he measured it by how well it predicts. That's still how we evaluate language models.
2. The link between prediction and compression. Good guesses make a short code. Same predictor on both ends means you can decompress. Hold onto that.
3. A clear picture of where counting runs out. Our n-gram model matched a human for four letters and then hit a wall at about 2.4 bits. The human, using meaning and long-range context, went down to about 1.

If you want to really feel this, add a tiny loop that asks you for each letter and records your guess numbers, then pass them to bounds(). Try 100 letters of a book you haven't read. It's slow, a bit humbling, and you'll understand the paper better than any summary can give you.

What's next

Our model in section 6 had a quiet problem: every time it met a 7-letter context it had never seen, it gave up and fell back to a shorter one. And when a letter had never followed a context in training, the counts said its probability was exactly zero. That's not just inelegant. In a real compressor or language model, a zero probability on something that actually happens is a disaster.

In Part 3 we fix that. We'll look at how to give probability to things you've never seen, starting with an idea from Alan Turing's wartime codebreaking work that I. J. Good published in 1953, now known as Good–Turing estimation, and then the smoothing and backoff tricks that kept n-gram models on top of language modeling for decades. Spoiler: the question "how likely is something I've never seen?" is the exact problem neural networks were brought in to solve.

Sources: C. E. Shannon, "Prediction and Entropy of Printed English," Bell System Technical Journal, 30(1), pp. 50–64, January 1951. C. E. Shannon, "A Mathematical Theory of Communication," Bell System Technical Journal, 27, pp. 379–423, 623–656, 1948. T. M. Cover and R. C. King, "A Convergent Gambling Estimate of the Entropy of English," IEEE Transactions on Information Theory, IT-24(4), pp. 413–421, July 1978. G. Delétang et al., "Language Modeling Is Compression," arXiv:2309.10668, 2023. I. J. Good, "The Population Frequencies of Species and the Estimation of Population Parameters," Biometrika, 40(3–4), pp. 237–264, 1953. Text: Moby Dick via the NLTK Gutenberg corpus (public domain).

---

📬 If you like this kind of "raw stuff nobody explains properly", subscribe to the newsletter. Part 3 lands in your inbox first, along with the code.