Part 1: Shannon (1948) — Entropy, N-grams, and Guessing the Next Letter

Hey, welcome to the very first part of From Shannon to Transformers. I will not waste your sec. Trust me.

Every time an LLM writes a sentence, it is doing one thing over and over: looking at what came before and guessing what comes next. We dress it up with attention heads, billions of parameters and fancy GPUs, but the core question is old. Really old. In 1948 a Bell Labs engineer named Claude Shannon asked it with nothing more than a book, a table of letter frequencies and a book of random numbers. And he got machines (well, a very patient human acting like one) to produce text that slowly started to look like English.

That paper is A Mathematical Theory of Communication, published in two parts in the Bell System Technical Journal (Vol. 27, pp. 379–423 and 623–656, July and October 1948). Most people know it as "the paper that invented the bit". Fewer people actually open it. Today we open it, rebuild its most famous experiment in about 60 lines of Python, and understand the one number that still sits at the heart of how we train language models: entropy.

In this post:

• What problem Shannon was actually solving (spoiler: not "meaning")
• His series of approximations to English: zero-order, first-order, digram, trigram
• Rebuilding that experiment in Python on Moby Dick
• Entropy explained with coins and yes/no questions, then with the real formula
• Why English is roughly 50% redundant, and what that has to do with crosswords
• The trap that catches everyone when they measure entropy on real data
• How all of this connects to the loss function of the model you used this morning

Tighten your seatbelt. We start with a telephone line, not a neural network.

1. The problem Shannon was solving

Shannon worked at Bell Labs, a telephone company's research lab. The engineering problem was very concrete: you have a message on one end of a wire, and you want to reproduce it on the other end, exactly or approximately, as cheaply as possible.

Here is the move that makes the whole paper work. Shannon says the meaning of the message does not matter for this problem. In his words: "These semantic aspects of communication are irrelevant to the engineering problem." What matters is that the message is one selected from a set of possible messages. The system has to be ready for any of them.

Did you get the shift? A message stops being "words with meaning" and becomes "a choice among possibilities". And once it is a choice, you can ask a measurable question: how much choice is there? If a source always sends the same letter, there is no choice and nothing to transmit. If every letter is equally likely, there is maximum choice. Real English sits somewhere in between, and Shannon wanted to know exactly where.

To do that, he needed a model of English as a statistical process: a machine that spits out letters one at a time, according to some probabilities. That is the first language model idea in this series, and it is the one everything else builds on.

2. The series of approximations to English

Section 3 of the paper is the part everyone should read. Shannon builds a ladder of fake-English generators, each one using a bit more of the real statistics of English. He uses a 27-symbol "alphabet": the 26 letters and a space. No punctuation, no case.

The rungs of the ladder are:

1. Zero-order approximation: symbols independent and equiprobable. Every one of the 27 symbols has probability 1/27.
2. First-order approximation: symbols independent, but with the frequencies of English. E is common, Z is rare, but each letter ignores the one before it.
3. Second-order approximation: digram structure as in English. The next letter depends on the previous one (after Q, you almost surely get U).
4. Third-order approximation: trigram structure. The next letter depends on the previous two.
5. Then he jumps to words: a first-order word approximation (words drawn by frequency) and a second-order word approximation (each word depends on the previous word).

How did he generate these without a computer? For the first two, he used a book of random numbers together with a table of letter frequencies. For the higher orders, he used a trick that I love: open a book at random and pick a letter at random on the page. Say it is "T". Now flip to another page and read until you find a "T", and write down the letter that follows it. Then search for that letter, and so on. The book itself becomes the probability table. No counting required.

His comment on the results is short: the resemblance to ordinary English text "increases quite noticeably at each of the above steps." Let's see it for ourselves.

3. Rebuilding the experiment in Python

Instead of a book and a lot of patience, we'll use a public domain text: Moby Dick from the Project Gutenberg selection that ships with NLTK's corpus data. Same rules as Shannon: uppercase letters plus space, everything else collapses into a single space.

The model is just a dictionary. For an order-n model, the key is the previous n − 1 letters (the context), and the value is a count of which letter came next. Generating text means looking up the last n − 1 letters and sampling from those counts. That's it. That's the whole language model.

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

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "   # Shannon's 27 symbols

def clean(text):
    text = text.upper()
    text = re.sub(r"[^A-Z]+", " ", text)      # everything else becomes a space
    return re.sub(r" +", " ", text).strip()

def ngram_model(text, n):
    """Map each (n-1)-letter context to a Counter of next letters."""
    model = defaultdict(Counter)
    for i in range(len(text) - n + 1):
        context, nxt = text[i:i + n - 1], text[i + n - 1]
        model[context][nxt] += 1
    return model

def generate(model, n, length=80, seed=None):
    rng = random.Random(seed)
    if n == 0:                                 # zero-order: all 27 equally likely
        return "".join(rng.choice(ALPHABET) for _ in range(length))
    out = rng.choice([c for c in model if c.startswith(" ")] or list(model)) if n > 1 else ""
    while len(out) < length:
        context = out[len(out) - (n - 1):] if n > 1 else ""
        counts = model.get(context)
        if not counts:                         # dead end: restart from a space
            out += " "
            continue
        letters, weights = zip(*counts.items())
        out += rng.choices(letters, weights=weights)[0]
    return out

def entropy(counter):
    total = sum(counter.values())
    return -sum((c / total) * math.log2(c / total) for c in counter.values())

def conditional_entropy(model):
    """H(next letter | previous n-1 letters), averaged over contexts."""
    total = sum(sum(c.values()) for c in model.values())
    return sum(sum(c.values()) / total * entropy(c) for c in model.values())

if __name__ == "__main__":
    text = clean(open(sys.argv[1], encoding="utf-8").read())
    print(f"{len(text):,} symbols\n")
    print(f"order 0  H = {math.log2(27):.2f} bits/letter")
    print("   ", generate(None, 0, seed=1))
    for n in (1, 2, 3, 4):
        m = ngram_model(text, n)
        print(f"order {n}  H = {conditional_entropy(m):.2f} bits/letter")
        print("   ", generate(m, n, seed=1))

Here is the actual output from running python shannon.py melville-moby_dick.txt:

1,170,352 symbols

order 0  H = 4.75 bits/letter
    ESZYCIDPYOPUMZGDPA MNTYYAWOIXZHSDKAAAURAMVGNXAQHYOPRHLHVHYOJAN RUDFUXJDXKXWQNQ V
order 1  H = 4.09 bits/letter
    TL EHATYOTHLMHN PSOOEUI HO HE   H OTEA FG INNUHTADRSTERO TH ENNIHETECEOONFRC EF
order 2  H = 3.32 bits/letter
    T BAS A TTHIT SOR ANGRITSTHAPOORDOS FUST ASSLIKEN SLID OFOWHENEVITININCAT THIN
order 3  H = 2.72 bits/letter
    EXED AND YE TH THER THENTH HABOARPLUTTAKED AGGIF DISPED CAUGHTEVE ME NO BROSEAD
order 4  H = 2.18 bits/letter
    ARED WHALE AND WILL AND ALIVENEAR WONDROP THANINEROUGH FOUNTED MY LIFE SAY COMP

Read that slowly, top to bottom. Order 0 is keyboard noise. Order 1 has the right texture (lots of E, T, spaces) but no structure at all; notice it even produces runs of spaces, because each symbol ignores the previous one. Order 2 starts producing pronounceable chunks: "SLID", "THIN", "FUST". Order 3 gives you real words ("AND", "CAUGHT", "ME NO"). Order 4 suddenly knows it is reading Moby Dick: "WHALE", "MY LIFE".

Nobody told the model what a word is. Nobody told it about whales. Words fall out of the statistics. That is the observation Shannon made with a book and random numbers, and it is the same observation that, scaled up enormously, gives you GPT-style models.

For fun, I also ran order 6 with a longer output: PAIR WHAT WHAT DISTRESS INDEX MIDDLE SLEWED UPON THEM TILL WELL TOUCHES FIFTY TIME…. Every chunk is a real word. The sentence is still nonsense. Keep that in mind; we'll come back to it.

4. Entropy: how much choice is there, really?

Look again at the output above. Next to each order there's a number like H = 3.32 bits/letter. That's entropy, and it's the hero of the paper. Let's build it from the ground up.

4.1 Start with yes/no questions

I pick one of 8 equally likely cards. You can ask yes/no questions. The smart strategy is to cut the options in half each time: 8 → 4 → 2 → 1. Three questions. With 16 cards, four questions. With N equally likely options, you need log₂ N questions. Each yes/no answer is one bit (short for binary digit, a word Shannon credits to J. W. Tukey).

So for Shannon's zero-order English, with 27 equally likely symbols, each letter carries log₂ 27 ≈ 4.75 bits. That's exactly the first number in our output.

4.2 Now make it unfair

But real letters aren't equally likely. Take a coin. A fair coin is 1 bit per flip: you genuinely have no idea what's coming. Now take a coin that lands heads 90% of the time. You're rarely surprised. It feels like less than 1 bit of "news" per flip. How much less?

Shannon's answer: an outcome with probability p carries −log₂ p bits of surprise (rare things are more surprising), and entropy is the average surprise:

H = −Σ pᵢ log₂ pᵢ

For the 90/10 coin: H = −(0.9 × log₂ 0.9 + 0.1 × log₂ 0.1) ≈ 0.137 + 0.332 ≈ 0.47 bits. Less than half of a fair coin. The math matches the gut feeling.

4.3 Why this formula and not some other one?

This is the part I like most, because Shannon doesn't just pull the formula from a hat. In Section 6 he lists three properties any reasonable measure of "choice" should have:

1. It should be continuous in the probabilities. Nudge a probability a little, the measure changes a little.
2. If all n options are equally likely, it should increase with n. More equally likely options means more uncertainty.
3. If you break one choice into two successive choices, the total should be the weighted sum of the parts. Picking a letter directly, or first picking "vowel or consonant" and then the letter, should give the same total uncertainty.

Then he proves (his Theorem 2) that the only function satisfying all three is H = −K Σ pᵢ log pᵢ, where K is just a positive constant that picks the unit. Choose log base 2 and you're measuring in bits. That's the beauty: the formula isn't a convention, it's forced by three common-sense requirements.

4.4 Entropy of a source with memory

Our order-2 and order-3 models have context. After "Q", the next-letter distribution is almost all U, so its entropy is near zero. After a space, almost anything can follow, so its entropy is high. Shannon handles this in Section 7: compute the entropy Hᵢ for each state (context) and average them, weighted by how often each state occurs: H = Σ Pᵢ Hᵢ.

That's literally what conditional_entropy() in our code does. Each context's Counter gets an entropy, and we weight it by how often that context appears. Concrete first, abstract second: the code is the formula.

5. English is about half redundant

Now look at the trend in our numbers: 4.75 → 4.09 → 3.32 → 2.72 bits per letter. The more context you use, the less surprising the next letter is. English is far from 4.75 bits of free choice per letter.

Shannon defines redundancy as one minus the ratio of the actual entropy to the maximum possible entropy with the same alphabet. His estimate, considering statistical structure over distances up to about eight letters: the redundancy of ordinary English is roughly 50%, a figure he says several independent methods agreed on. He also explains what that means in plain terms: half of what we write is determined by the structure of the language, and half is chosen freely.

Then he drops a delightful observation: redundancy decides whether crossword puzzles are possible. With zero redundancy, any sequence of letters would be valid text and any grid would be a crossword. With very high redundancy, there's too little freedom to fit words crossing in two directions. At about 50%, he notes, large crossword puzzles are just possible.

The engineering payoff is the real point: if half of English is predictable, a clever code can transmit it using fewer bits than the naive 4.75 per letter. Shannon proves that the entropy is the floor: you can't encode a source with fewer than H bits per symbol on average, and you can get as close to H as you like. Every lossless compressor you have used (zip, gzip, PNG) has to respect that floor.

⚠️ The trap that catches everyone

Look at our numbers again and keep going to higher orders. I ran orders 1 to 8 on two books:

• Moby Dick (1.17M symbols): 4.09, 3.32, 2.72, 2.18, 1.82, 1.53, 1.25, 0.98
• Alice in Wonderland (135k symbols): 4.05, 3.21, 2.44, 1.82, 1.42, 1.09, 0.84, 0.61

Did you get the pain? The smaller book "looks" more predictable. Alice isn't a simpler language. We just have less data. At order 8 on Moby Dick, the model has 350,829 distinct 7-letter contexts, and 207,975 of them appear exactly once. A context seen once has exactly one "next letter", so its measured entropy is zero. The model hasn't learned English; it has memorized the book.

Counting frequencies on finite text and plugging them into the formula underestimates the true entropy, and the error grows as the order grows. Shannon himself, in his 1951 follow-up, reports 3.32 bits for the digram estimate on a 27-symbol alphabet (matching our order-2 number) but 3.1 for trigrams, noticeably above our 2.72. Low entropy on a training set means nothing until you measure it on text the model has never seen. Sound familiar? It's overfitting, 1948 edition, and it's the exact reason we evaluate language models on held-out data.

6. From Shannon's letters to your LLM's loss

Let me connect the dots, because this isn't just history.

• The model: our order-n dictionary is a model of P(next symbol | previous symbols). An LLM models exactly the same thing, with tokens instead of letters and a context of thousands of tokens instead of three letters.
• The problem with counting: the trap above is why we stopped using raw counts. The number of possible contexts explodes (27⁷ ≈ 10 billion possible 7-letter contexts), and most of them are never seen. Neural networks are, in one sense, a way to share statistical strength between similar contexts instead of treating each one as a separate row in a table.
• The score: when you train a language model you minimize cross-entropy: the average of −log p(actual next token) under the model. That's Shannon's "average surprise", measured with the model's probabilities against real text. Perplexity, the other number you see in papers, is just 2 raised to that cross-entropy (when measured in bits).

So when someone says a model reached a certain loss, they're telling you how many bits of surprise per token it still has left. Shannon gave us the ruler in 1948. We've spent the 75+ years since then building better things to measure with it.

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

We didn't build anything intelligent today. Our order-4 model can write "WHALE AND WILL AND ALIVENEAR", and our order-6 model writes real words in nonsense order. No grammar, no meaning, no idea what a whale is.

And that's exactly the honest lesson of this paper. Shannon was explicit that meaning wasn't his problem. What he gave us was more fundamental: a way to treat language as a probability distribution, a way to generate from it, and a single number, entropy, to measure how predictable it is. The approximations show that structure (letters, then syllables, then words) emerges from statistics alone. The trap shows that statistics from finite data lie to you if you're not careful.

Two ideas from 1948 that you will see again in every part of this series: predict the next symbol, and measure your surprise in bits. Everything up to transformers is a better answer to the same question.

If you want to really own this, run the script on a text you love, push the order up until it starts copying whole sentences, and watch the entropy collapse. Feel the trap with your own hands. That's worth more than any summary.

What's next

In Part 2 we stay with Shannon for one more round: his 1951 paper Prediction and Entropy of Printed English. Instead of counting letters, he turned humans into the language model, making people guess a hidden text one letter at a time. With up to 100 letters of context, he estimated that English drops to something on the order of one bit per letter, around 75% redundancy. We'll rebuild the guessing game, see how he squeezed upper and lower bounds out of it, and put a counting model in the subject's chair to see how far it gets against Shannon's human.

Sources: C. E. Shannon, "A Mathematical Theory of Communication," Bell System Technical Journal, 27, pp. 379–423, 623–656, 1948. C. E. Shannon, "Prediction and Entropy of Printed English," Bell System Technical Journal, 30(1), pp. 50–64, 1951. Text: Moby Dick and Alice's Adventures in Wonderland via the NLTK Gutenberg corpus (public domain).

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