Markov chains and information

In the last chapter all the observations were independent: the respondents didn’t confer, the cups of tea knew nothing of one another. But the letters of a text, the weather from day to day, clicks on links all depend on what came before. How do you describe such dependence? And can you measure how much information a message carries, not by eye but in units, like length or mass?

Both questions would be best answered by a cryptographer and a linguist sitting at one table. The cryptographer knows that a text gives itself away through its letter frequencies: back in the ninth century the Arab philosopher al-Kindi described how to break a cipher by comparing the frequencies of the symbols in the ciphertext with the frequencies of the letters of the language. The linguist knows that letters aren’t independent: some readily follow others. This chapter is the working log of such a table. We’ll count letters with Andrey Markov, teach a machine to write, find out how many questions it takes to guess what someone has in mind, and find the number that Claude Shannon called the amount of information.

Twenty thousand letters

In January 1913 Andrey Andreyevich Markov presented an unusual paper to the Academy of Sciences. The mathematician, known for his theorems on sums of random variables, had taken up Pushkin’s verse novel Eugene Onegin. He wrote out the first $20{,}000$ letters of the novel (without spaces, punctuation, or the Russian hard and soft signs) and counted the vowels and consonants. There were $8638$ vowels and $11{,}362$ consonants, so the share of vowels was $0.432$.

That was only the beginning. Markov also counted pairs of neighbouring letters. A vowel right after a vowel occurred $1104$ times, a consonant after a consonant $3827$ times. If the letters came independently, like tosses of a coin, a vowel would follow a vowel with the same probability $0.432$ as in general. In fact

$$P(\text{vowel} \mid \text{vowel}) = \frac{1104}{8638} \approx 0.128, \qquad P(\text{vowel} \mid \text{consonant}) = 1 - \frac{3827}{11{,}362} \approx 0.663.$$

After a vowel a vowel comes more than three times less often than on average, and after a consonant one and a half times more often. Letters remember their neighbour: vowels and consonants like to alternate.

Why would an academician count letters? Markov was having an argument. The mathematician Pavel Nekrasov claimed that the law of large numbers requires the observations to be independent, and drew far-reaching philosophical conclusions from this. Back in 1906 Markov had proved that the law of large numbers also holds for variables each of which depends on the previous one, and in 1913 he tested his model on the liveliest material he could find: Pushkin’s verse.

Markov’s model is simple. A text is a sequence of two states, “vowel” and “consonant”. The next letter is chosen at random, but the probabilities depend only on the current one. This is a Markov chain with two states, the same construction as the scooters in chapter 38. Its transition probabilities are collected into a matrix:

$$P = \begin{pmatrix} 0.128 & 0.872 \\ 0.663 & 0.337 \end{pmatrix}.$$

There’s a subtlety of notation here. In chapter 38 column $j$ of the transition matrix said where state $j$ goes, and the columns added up to one. Probability theory traditionally writes the transposed matrix: the row is where from, the column is where to, $p_{ij}$ is the probability of moving from state $i$ to state $j$, and the rows add up to one. The first row of our matrix is what happens after a vowel, the second after a consonant. A distribution over the states is then written as a row $\boldsymbol\pi = (\pi_1, \dots, \pi_n)$ and multiplied by the matrix on the right. From here on in this chapter, that’s the only way we’ll do it.

A row of probabilities of the states: $\pi_i \ge 0$ and $\pi_1 + \dots + \pi_n = 1$. The transition matrix: $p_{ij}$ is the probability of moving from state $i$ to $j$, and the rows add up to one. The product $\boldsymbol\pi P$ is the distribution one step later: $(\boldsymbol\pi P)_j = \sum_i \pi_i p_{ij}$ by the law of total probability. The equation says that the distribution doesn’t change in a step. It’s the same eigenvector with eigenvalue $1$ as in chapter 38, only written as a row: $\boldsymbol\pi P = \boldsymbol\pi$ is the same as $P^{\mathsf T}\boldsymbol\pi^{\mathsf T} = \boldsymbol\pi^{\mathsf T}$. Example: for Markov’s chain $\boldsymbol\pi \approx (0.432,\ 0.568)$, and indeed $0.432 \cdot 0.128 + 0.568 \cdot 0.663 \approx 0.432$.

Notice that the stationary share of vowels, $0.432$, matches their share in the text to three decimal places. That’s no accident. In any text there are as many “vowel → consonant” transitions as “consonant → vowel” ones, give or take one: each group of vowels starts somewhere and ends somewhere. And the equality of these flows, as we’ll now see, is exactly what determines the chain’s equilibrium. For two states everything can be computed to the end.

The trick is to follow not the letters but the flows of probability between the states.

Suppose the chain is now in state $1$ with probability $x$ and in state $2$ with probability $1 - x$. In a step a share $a$ of $x$, that is, $ax$, flows from $1$ to $2$, and $b(1 - x)$ flows back. The distribution doesn’t change when the flows balance: $ax = b(1 - x)$. This is a linear equation with the unique solution $x = \frac{b}{a + b}$ (here we need $a + b > 0$). That’s $\pi_1$, and $\pi_2 = 1 - \pi_1 = \frac{a}{a + b}$. Now take any initial $x$. After a step $x' = x - ax + b(1 - x) = b + (1 - a - b)\,x$. For $\pi_1$ a step changes nothing: $\pi_1 = b + (1 - a - b)\,\pi_1$, the same balance of flows. Subtract one equation from the other: $x' - \pi_1 = (1 - a - b)(x - \pi_1)$. At each step the deviation from equilibrium is multiplied by the same number $1 - a - b$, so after $k$ steps it’s $(1 - a - b)^k\,\delta$. If $0 < a + b < 2$, the factor is less than one in absolute value, and the deviation melts away. For Markov $1 - a - b \approx -0.535$: a negative factor means that the deviation changes sign each time; the chain approaches equilibrium by swinging, just as vowels and consonants alternate.

The condition $a + b < 2$ cuts off the one bad case $a = b = 1$: the chain alternates the states without any randomness, and the deviation only changes sign without shrinking. And the factor $1 - a - b$ is the second eigenvalue of the matrix $P$, like the factor $0.4$ for the scooters in chapter 38.

In a certain text a vowel follows a vowel with probability $0.2$, and follows a consonant with probability $0.6$. What share of the letters of a long text are vowels? Give the answer as a fraction.

From a vowel the chain goes to a consonant with probability $a = 1 - 0.2 = 0.8$, from a consonant to a vowel with probability $b = 0.6$. The stationary share of vowels is $\frac{b}{a + b} = \frac{0.6}{1.4} = \frac37 \approx 0.43$. A check by the balance of flows: $\frac37 \cdot 0.8 = \frac47 \cdot 0.6 = \frac{2.4}{7}$.

Weather and walks

It’s a similar story with the weather: tomorrow is most often like today. Take a chain with three states (sunny, cloudy, rain) and conditional transition probabilities. After a sunny day, tomorrow is sunny with probability $0.6$, cloudy $0.3$, rain $0.1$; after a cloudy day $0.3$, $0.4$ and $0.3$; after a rainy one $0.2$, $0.4$ and $0.4$.

Let Monday be sunny: the distribution $(1,\ 0,\ 0)$. On Tuesday it’s the first row of the matrix, $(0.6,\ 0.3,\ 0.1)$. On Wednesday $(0.47,\ 0.34,\ 0.19)$, on Thursday $(0.422,\ 0.353,\ 0.225)$, and by the next Monday $(0.394,\ 0.361,\ 0.245)$. Whatever weather you start with, a week later the picture is almost the same: the chain forgets where it started. The limit is the stationary distribution $\boldsymbol\pi = \left(\frac{24}{61},\ \frac{22}{61},\ \frac{15}{61}\right)$; check that $\boldsymbol\pi P = \boldsymbol\pi$. This will happen with any matrix in which all the transition probabilities are positive: it’s the theorem on positive chains from chapter 38, and its proof doesn’t depend on transposing.

The most vivid Markov chain is a random walk on a graph (chapter 46). A walker stands at a vertex and leaves along a randomly chosen edge: from a vertex of degree $d$, to each neighbour with probability $1/d$. Where do they end up most often? Intuition suggests: where more roads lead. Intuition is right, and the answer fits into one fraction.

The trick is to check the balance not vertex by vertex but for each edge separately.

The numbers $\frac{\deg v}{2E}$ really do form a distribution: they’re non-negative, and their sum is $\frac{1}{2E}\sum_v \deg v = 1$, because the sum of the degrees is twice the number of edges; each edge is counted at both ends. Compute the flow of probability along an edge $uv$ in one step. From $u$ to $v$ goes $\pi_u \cdot \frac{1}{\deg u} = \frac{\deg u}{2E} \cdot \frac{1}{\deg u} = \frac{1}{2E}$. Exactly the same amount goes back along this edge, from $v$ to $u$. Each edge carries equal amounts both ways, $\frac{1}{2E}$. So in a step as much flows into each vertex as flows out: along each of its edges the inflow equals the outflow. The distribution doesn’t change; it’s stationary. This equality of flows along each edge is called detailed balance. Now uniqueness. Let $\boldsymbol\pi'$ be any stationary distribution, and put $h(v) = \pi'_v/\deg v$. The stationarity condition $\pi'_v = \sum_{u \sim v} \pi'_u/\deg u$ (a sum over the neighbours of $v$) turns into $h(v) = \frac{1}{\deg v}\sum_{u \sim v} h(u)$: at each vertex $h$ equals the average of its values at the neighbours. Take a vertex where $h$ is largest. The average of numbers not exceeding the maximum equals the maximum only if all of them equal the maximum. So at all the neighbours of this vertex $h$ is largest too. Repeat the argument for the neighbours, then for their neighbours. The graph is connected, so this reaches every vertex: $h$ is the same number $c$ everywhere, that is, $\pi'_v = c\deg v$. The probabilities add up to $1$, so $c = \frac{1}{2E}$ and $\boldsymbol\pi' = \boldsymbol\pi$.

The stationary distribution exists and is unique, but the walk doesn’t always converge to it. If the graph is bipartite (the vertices can be coloured in two colours so that edges join only different colours), the walker alternates between the two sides, and the distribution over even and odd steps never evens out. The theorem in chapter 38 required all transition probabilities to be positive precisely to rule out such traps. And if the walker is sometimes allowed to teleport to a random page, and the edges are made one-way, you get PageRank (chapter 38).

A machine that writes

Back to text. Markov distinguished only vowels and consonants. What if the states are the letters themselves? The next letter is chosen with probabilities that depend on the previous one, and the chain starts to write. Better still if the state is the last two, three, four letters: then the chain remembers more.

That’s what Claude Shannon did in his paper “A Mathematical Theory of Communication” (1948). He had no computer to hand, and he built the chain with a book. He opened a book at random, found the current word on the page, looked at which word followed it and wrote it down; opened the book at another place, found that word, and so on. The result was a “second-order word approximation”, which begins like this: THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER… There’s no sense in it, but each pair of neighbouring words sounds perfectly English.

As its memory grows, the model writes ever more plausibly, but it runs into two walls. The first is the number of states: with an alphabet of $27$ symbols (the letters and the space), a model with a memory of $k$ symbols has up to $27^k$ states, and at $k = 5$ that’s already more than $14$ million. The second wall follows from the first: almost none of these states occurs in the sample, and those that do occur once or twice. A model with a long memory doesn’t compose, it quotes: after a rare context it has exactly one continuation, the one that stood in the sample.

Modern language models get round both walls differently. They don’t store a table of continuations; they learn to generalise: to estimate the probability of the next symbol even after a context that never occurred in the training texts, by its similarity to what did. How to build such a model from scratch and train it right in your browser is the subject of the Sprout course on this site (/utilities/micro-llm). But it too, like a Markov chain, outputs at each step a probability distribution for the next symbol and chooses from it.

Twenty questions

Now the second question: how much information is there in a message? Shannon started from the idea that information is uncertainty removed. The simplest way to measure it is a game: one person thinks of something, the other guesses by asking questions answered “yes” or “no”.

In chapter 1 six cards guessed a number from $1$ to $63$: six answers, “yes” or “no”. Each answer halves the pool of candidates, so $k$ questions can distinguish $2^k$ options, and choosing one of $N$ equally likely options takes $\lceil \log_2 N\rceil$ questions. A million is twenty questions: $2^{20} = 1{,}048{,}576$. Hence a natural measure: a message that selects one of $N$ equally likely options carries $\log_2 N$ bits. A measure based on the logarithm of the number of options was proposed by the engineer Ralph Hartley as early as 1928.

But options are rarely equally likely. Suppose a random letter of an English text has been chosen. The letter e occurs well over a hundred times more often than z, and a good guesser won’t ask “is the letter in the first half of the alphabet?”. They’ll ask “is it e, t or a?”: that trio alone covers more than a quarter of the letters of a text. A good question halves not the number of options but their probability. Then a rare letter takes many questions and a common one few, and on average fewer than $\log_2 N$ are needed.

How many questions is an outcome of probability $p$ “worth”? If each question halves the probability, then after $k$ answers the remaining options have total probability $2^{-k}$. An outcome of probability $p$ is identified when $2^{-k} = p$, that is, $k = \log_2\frac1p$. Shannon took this number as the measure.

The logarithm here isn’t a whim. For independent events probabilities multiply, while information should add: learning the outcome of two coins is the same as learning the outcome of each, $\log_2 4 = \log_2 2 + \log_2 2$. The logarithm is exactly what turns a product into a sum: $-\log_2(pq) = -\log_2 p - \log_2 q$. Shannon called the average amount of information per message entropy.

The probability of the $i$th outcome: its weight in the average. With a minus sign, the self-information of the outcome: the rarer, the larger. Outcomes with $p_i = 0$ don’t enter the sum: $p\log_2 p \to 0$ as $p \to 0$. Example: a fair coin has $H = 1$ bit, a fair die $\log_2 6 \approx 2.58$ bits. A coin that comes up heads in $90$ % of tosses gives only $0.47$ bits: the outcome is almost always predictable. The distribution $\left(\frac12,\ \frac14,\ \frac18,\ \frac18\right)$ gives $\frac12 \cdot 1 + \frac14 \cdot 2 + \frac18 \cdot 3 + \frac18 \cdot 3 = 1.75$ bits.

The letter z is very rare in English texts. How much information does each letter of the long message “zzzzzzzzzz…” carry if the sender only ever sends z’s?

Zero bits A lot: z is a rare letter $\log_2 26 \approx 4.7$ bits

Information depends not on the symbol but on the distribution it was chosen from. A source that always sends the same thing tells you nothing: its outcome is known in advance, $-\log_2 1 = 0$.

Why a die has more entropy than a coin is clear: there are more options. But which distribution on $n$ outcomes is the most unpredictable? The answer comes from an inequality on which the whole of information theory rests.

The trick is that the graph of the logarithm lies below its tangent, and the centre of mass of points lying below a line is below it too.

The natural logarithm lies below its tangent at the point $1$: $\ln x \le x - 1$ for all $x > 0$, with equality only at $x = 1$. Indeed, the function $f(x) = x - 1 - \ln x$ has derivative $1 - \frac1x$, negative for $x < 1$ and positive for $x > 1$, so the function’s smallest value is $f(1) = 0$ (chapter 27). The difference between the right and left sides of the inequality is $-\sum p_i\log_2\frac{q_i}{p_i}$ (summing over the $i$ with $p_i > 0$), and $\log_2 y = \frac{\ln y}{\ln 2}$. We need to prove that $\sum p_i \ln x_i \le 0$, where $x_i = \frac{q_i}{p_i}$. Place weights $p_i$ at the points $(x_i,\ \ln x_i)$ of the graph. The centre of mass of these weights has abscissa $\sum p_i x_i = \sum q_i \le 1$ (summing over $p_i > 0$) and ordinate $\sum p_i \ln x_i$, exactly what we need to estimate. All the weights lie on the graph, and so not above the line $y = x - 1$; their centre of mass isn’t above it either: $\sum p_i\ln x_i \le \sum p_i (x_i - 1) = \sum q_i - 1 \le 0$. That’s Gibbs’ inequality. Equality requires every weight to lie on the tangent, that is, $x_i = 1$ and $q_i = p_i$ whenever $p_i > 0$, and also $\sum_{p_i > 0} q_i = 1$. Then nothing is left for the outcomes with $p_i = 0$, yet all the $q_i$ are positive; so there are no such outcomes, and $p_i = q_i$ everywhere.

The chosen outcome is one of five options with probabilities $\frac12$, $\frac14$, $\frac18$, $\frac1{16}$, $\frac1{16}$. What is the entropy of this distribution in bits? That’s how many yes/no questions are needed on average if you ask sensibly.

$H = \frac12 \cdot 1 + \frac14 \cdot 2 + \frac18 \cdot 3 + \frac1{16} \cdot 4 + \frac1{16} \cdot 4 = \frac12 + \frac12 + \frac38 + \frac14 + \frac14 = \frac{15}8 = 1.875$ bits. The strategy: “is it the first option?”, if not “the second?”, if not “the third?”, if not “the fourth?”. The first is guessed in one question, the second in two, the third in three, the fourth and fifth in four; on average exactly $1.875$ questions. For comparison, five equally likely options need $\log_2 5 \approx 2.32$ bits.

Huffman coding

Entropy is not only a measure of uncertainty but also the cost of writing something down. Here’s the cryptographer’s problem in reverse: not to hide a message but to send it as briefly as possible. Write each letter as a string of zeros and ones. A fixed-length code spends $5$ bits on each of $26$ letters. It’s better to give common letters short codes and rare ones long codes. That’s how Morse code works: the most common English letter, E, is sent as a single dot.

Codes of different lengths have a danger. If “a” is $0$ and “b” is $01$, how do you read $001$: “ab”, or “aa” and a fragment? Morse is saved by the pauses between signs. Without pauses, a rule saves the day: no codeword may be the beginning of another.

The frequency of the $i$th letter. The length of its codeword in bits. Example: letters with frequencies $\frac12$, $\frac14$, $\frac18$, $\frac18$ and the code $0$, $10$, $110$, $111$ give $L = \frac12 \cdot 1 + \frac14 \cdot 2 + \frac18 \cdot 3 + \frac18 \cdot 3 = 1.75$ bits per letter, exactly the entropy of this distribution. A fixed-length code for four letters would spend $2$ bits each.

Short words in a prefix code are in short supply: if $0$ is taken, all words beginning with zero are forbidden, and half the possibilities are lost. An exact account of this shortage is a single inequality.

The trick is to turn each codeword into a little piece of the interval $[0, 1)$.

To a codeword $w = w_1w_2\dots w_\ell$ assign the binary fraction $0.w_1w_2\dots w_\ell$ and the interval $\bigl[0.w,\ 0.w + 2^{-\ell}\bigr)$ of length $2^{-\ell}$: it contains all the binary fractions whose expansion begins with $w$. The word $0$ gets the left half of the interval, the word $10$ the third quarter, the word $110$ the seventh eighth. If $w$ is the beginning of the word $v$, then the interval of $v$ lies inside the interval of $w$: appending digits only narrows the set of fractions. If neither word is the beginning of the other, then at some position one has $0$ and the other $1$, and their intervals don’t overlap. For a prefix code the intervals are pairwise disjoint and all lie in $[0, 1)$, so the sum of their lengths is at most one: $\sum 2^{-\ell_i} \le 1$. Conversely: order the lengths increasingly and lay intervals of lengths $2^{-\ell_1}, 2^{-\ell_2}, \dots$ side by side, starting at zero. The inequality guarantees that they all fit into $[0, 1)$. Each next interval starts at the point equal to the sum of the previous lengths $2^{-\ell_j}$ with $\ell_j \le \ell_i$, which is a multiple of $2^{-\ell_i}$, and its binary expansion fits into $\ell_i$ digits. These digits will be the codeword: the word’s interval coincides with the interval laid down, the intervals don’t overlap, so the code is a prefix code.

Now we can prove that entropy is the limit of compression.

The extra bit is the price of whole-number lengths. It can be made as small as you like by coding not letters but blocks of $k$ letters: for independent letters the entropy of a block is $kH$, a code for blocks spends less than $kH + 1$ bits, that is, less than $H + \frac1k$ bits per letter. This is Shannon’s source coding theorem: a message can’t be compressed below $H$ bits per symbol, but it can come as close to that limit as you like.

A practical question remained: how do you find the code with the smallest average length? In 1951 it was solved by an MIT graduate student, David Huffman. As the story goes, Professor Robert Fano gave the students on his information theory course a choice: sit the exam or write a term paper on finding an optimal code. Fano didn’t mention that he and Shannon had themselves looked for such a method and not found it. Huffman was about to give up and study for the exam when he hit on building the code tree not from the top but from the bottom, starting with the rarest letters. The paper came out in 1952.

The trick is induction on the number of letters: merging the two rarest letters shrinks the problem and doesn’t change which code is best for it.

A prefix code is a binary tree: the codewords are paths from the root to the leaves, left $0$, right $1$, and a word’s length is the depth of its leaf. In an optimal tree every internal vertex has two children: if it has only one, that child can be lifted into its parent’s place, and all the words below it become a bit shorter. Let $x$ and $y$ be the two least likely letters. Take an optimal tree and its deepest leaf. Its parent has two children, and the other one is also a leaf of greatest depth: there’s nothing deeper in the tree. Swap $x$ and $y$ into the places of these two leaves. This doesn’t increase the average length. If the letter $x$ at depth $\ell_x$ swaps places with a letter $a$ at depth $\ell_a \ge \ell_x$, and $p_x \le p_a$, the length changes by $p_x\ell_a + p_a\ell_x - p_x\ell_x - p_a\ell_a = (p_a - p_x)(\ell_x - \ell_a) \le 0$. So there’s an optimal tree in which $x$ and $y$ are siblings at the deepest level. Merge the siblings $x$ and $y$ into one letter $z$ with probability $p_x + p_y$. The result is a tree for $n - 1$ letters in which the leaf $z$ is one level higher. For any tree where $x$ and $y$ are siblings, $L = L' + p_x + p_y$, where $L'$ is the average length after the merge: only the words for $x$ and $y$ were a bit longer than the word for $z$. Induction on $n$. For two letters the codes $0$ and $1$ of length $1$ are best: words can’t be shorter. Suppose the Huffman code is optimal for $n - 1$ letters. For $n$ letters the algorithm merges $x$ and $y$ and builds the Huffman code for $n - 1$ letters, so $L_{\text{Huffman}} = L'_{\min} + p_x + p_y$. And by step 2 an optimal code can have $x$ and $y$ as siblings, and then its length is $L' + p_x + p_y \ge L'_{\min} + p_x + p_y$. The Huffman code is no longer than an optimal one, so it’s optimal itself.

Four letters occur with frequencies $40$ %, $30$ %, $20$ % and $10$ %. Find the average length of the Huffman code in bits per letter.

Merge the two rarest: $0.1 + 0.2 = 0.3$. That leaves $0.4$, $0.3$ and $0.3$; merge the two $0.3$’s into $0.6$. The last merge: $0.4 + 0.6$. The depths of the leaves: the letter with frequency $0.4$ is at depth $1$, $0.3$ at $2$, $0.2$ and $0.1$ at $3$ each. The average length is $0.4 \cdot 1 + 0.3 \cdot 2 + 0.2 \cdot 3 + 0.1 \cdot 3 = 1.9$ bits. The entropy of this distribution is $\approx 1.846$ bits, so less than $0.06$ bits remain to the limit, while a fixed-length code would spend $2$.

How much information is in a letter

Back to the question we started with: how much information does a letter of English text carry? We’ll refine the answer like a cryptographer who learns more and more about the language.

If the $26$ letters and the space were equally likely and independent, each symbol would carry $\log_2 27 \approx 4.75$ bits. Taking frequencies into account lowers the estimate: an uneven distribution has less than the maximum entropy. Compute it in the Huffman widget on the text of this chapter and you’ll get a little over $4$ bits. Taking the link with the previous letter into account lowers it further. Let’s show this on Markov’s model, where only vowels and consonants are distinguished. Without memory each “vowel or consonant” symbol carries $H(0.432) \approx 0.987$ bits. With memory the uncertainty is different: after a vowel the choice is between probabilities $0.128$ and $0.872$, after a consonant between $0.663$ and $0.337$. Average the entropies of these choices over the stationary distribution:

$$0.432 \cdot H(0.128) + 0.568 \cdot H(0.663) \approx 0.432 \cdot 0.551 + 0.568 \cdot 0.922 \approx 0.762 \text{ bits}.$$

Knowing the previous letter removes almost a quarter of the uncertainty. The longer the memory, the less is left. In 1951 Shannon ran an experiment: a subject guessed an English text letter by letter, knowing everything before it, and Shannon recorded at which attempt each letter was guessed. From these data he estimated the entropy of English text with a long context at between $0.6$ and $1.3$ bits per letter, that is, about one bit. Of the $4.75$ bits that each of the $27$ symbols (the $26$ letters and the space) could carry, the language uses only about a quarter.

Already in his 1948 paper Shannon wrote that the redundancy of English is about $50$ % if links over distances of up to eight letters are counted; with long context it reaches about $75$ %. Redundancy isn’t waste but insurance. Th mnng f ths sntnc s clr vn wtht vwls: you’ve just read a sentence from which every vowel was removed. We don’t notice a typo in a word, we understand the person we’re talking to in a noisy room, and all this is thanks to redundancy. Error-correcting codes add redundancy to data deliberately and by calculation; see the chapter on rings and fields.

Prediction and compression are two sides of the same thing. The more confidently a model guesses the next symbol, the fewer bits are needed to record what actually happened: if the model gave the real symbol probability $p$, a good coder will spend about $-\log_2 p$ bits on it. Compressors build a model of the text on the fly and code according to it. And language models like Sprout learn on exactly this quantity: their training error is the average self-information of the real next symbol, $-\log p$, usually in natural logarithms. A model that writes convincingly is a model that compresses well, and vice versa.

You can compute entropies, code lengths and stationary distributions in the trainer.

Where next

In this chapter we freely used the words “proof”, “set”, “infinity”. We proved things by contradiction and by induction, reasoned about the set of all prefix codes and about a chain that steps on for ever. The earlier chapters were the same: “for every $\varepsilon$ there’s a $\delta$”, “a basis exists”, “for all natural $n$”. But what exactly do “for all” and “there exists” mean? Why does anything at all follow from a false statement, and why does “the set of all sets” lead to a contradiction? What the whole edifice of mathematics stands on is the subject of chapter 51.