The Tiny Shakespeare text that the site's language model walkthrough trains on has 1,115,394 characters from an alphabet of 65, and stored at one byte per character it fills 1.115 megabytes. Entropy computes the entropy of its character frequencies as 4.78 bits, and the walkthrough's final model reaches a validation loss of 1.48 nats per character. Are those two numbers statements about storage? They are. No code that can be decoded stores characters drawn with these frequencies in fewer than 4.78 binary digits each on average. A code that comes within one digit always exists. And a model's loss, converted to bits, is the length per character of a code built from the model.
A code assigns each symbol of an alphabet a string of binary digits, its codeword. A prefix code is one in which no codeword is the beginning of another. The perplexity of a model on a text is the base of the logarithm raised to the model's cross-entropy on that text. It is the number of equally likely choices that would be as hard to predict.
First we ask what a code must satisfy to be decodable, and prove Kraft's inequality in both directions, for prefix codes and for all uniquely decodable codes. Then we prove the source coding bound: the expected length of a code is the entropy plus a divergence, so it cannot go below the entropy. Next come Shannon's code, which is within one bit, Huffman's code, which is the best possible, and block codes, which remove the last bit. Then the same accounting is applied to the integer codes of Index Compression. Finally we define perplexity, prove its properties, and measure it for character and token models of the text. The article assumes Entropy and uses Gibbs' inequality from Cross-Entropy and Kullback–Leibler Divergence.
This article is the home of source coding and of perplexity on this site. It proves the lower bound that Index Compression states with a citation to a textbook, and its definition of perplexity agrees with the one that Evaluating Topic Models and The Bigram Language Model use.
Notation
Notation follows the rest of the Information Theory unit. A source is a random variable $X$ on an alphabet $\mathcal{X}$ with mass function $p(x)$; a second distribution or a model on the same alphabet is $q$. $H(p)$ is the entropy, $H(p, q) = -\sum_x p(x)\log q(x)$ the cross-entropy, and $D(p \,\|\, q) = \sum_x p(x)\log\frac{p(x)}{q(x)}$ the Kullback–Leibler divergence, so that $H(p, q) = H(p) + D(p \,\|\, q)$. In this article codes are binary and code lengths are counted in bits, so logarithms are $\log_2$ unless a loss in nats is being quoted; one nat is $1/\ln 2 = 1.4427$ bits. The length of the codeword of $x$ is $\ell(x)$, and the expected length of a code is
$$L = \sum_{x} p(x)\,\ell(x) \quad \text{bits per symbol}.$$
Alphabets are finite except where the integer codes are treated, and those passages say what changes.
What a code must allow
The smallest example that shows everything is the five vowels. Among the 288,037 lowercase vowels of the text, the counts are:
| Vowel | Count | Share $p$ | $\log_2 \frac{1}{p}$ |
|---|---|---|---|
| e | 94,611 | 0.3285 | 1.61 |
| o | 65,798 | 0.2284 | 2.13 |
| a | 55,507 | 0.1927 | 2.38 |
| i | 45,537 | 0.1581 | 2.66 |
| u | 26,584 | 0.0923 | 3.44 |
Call a source that emits vowels independently with these shares the vowel source. Its entropy is 2.2099 bits. Three codes for it show what can go wrong and what can be gained.
| Vowel | Fixed length | Too short | Prefix code |
|---|---|---|---|
| e | 000 |
0 |
00 |
| o | 001 |
1 |
01 |
| a | 010 |
00 |
10 |
| i | 011 |
01 |
110 |
| u | 100 |
10 |
111 |
The fixed-length code spends 3 bits on every vowel. The second code is shorter everywhere, and useless: the string 00 is the codeword of a and also two codewords of e, so a reader cannot tell which was sent. The third code spends 2 bits on the three common vowels and 3 on the two rare ones, and it can be read without ambiguity. The string 011111100010 splits in only one way, as 01, 111, 110, 00, 10, which is o u i e a. A reader knows where each codeword ends as soon as its last bit arrives, because no codeword continues into another.
Two properties are being distinguished here.
- A code is uniquely decodable if no string of bits can be split into codewords in two ways. Formally, the map that sends a finite sequence of symbols to the concatenation of their codewords is one to one.
- A code is a prefix code (also called prefix-free or instantaneous) if no codeword is a prefix of another codeword.
Every prefix code is uniquely decodable. Given a string that is a concatenation of codewords, the first codeword is determined: if two different codewords both began the string, the shorter would be a prefix of the longer. Remove it and repeat. The converse fails. The code 0, 01, 11 is not a prefix code, since 0 begins 01. But it is uniquely decodable: read backward it is a prefix code, so a string can be split from its end. Its reader may have to wait for the end of the message before decoding the first symbol.
A prefix code is a binary tree. Each codeword is a path from the root, a 0 for a left branch and a 1 for a right branch. The prefix condition says that no codeword lies on the path to another: codewords sit at leaves. The question of how short the codewords can be is a question about how many leaves fit at each depth.
Kraft's inequality
Short codewords are expensive. A codeword of length 1, say 0, removes half of all longer strings from use, since none of them may begin with 0. A codeword of length 3 removes an eighth. Here is the idea in one sentence: a codeword of length $\ell$ uses up a fraction $2^{-\ell}$ of a budget of 1, and a prefix code exists for a list of lengths exactly when the list stays within the budget.
Theorem (Kraft's inequality). (a) The codeword lengths $\ell_1, \dots, \ell_m$ of any binary prefix code satisfy
$$\sum_{i=1}^{m} 2^{-\ell_i} \le 1.$$
(b) Conversely, if positive integers $\ell_1, \dots, \ell_m$ satisfy this inequality, there is a prefix code with exactly these lengths.
The sum is called the Kraft sum of the code.
Proof of (a). Let $\ell_{\max}$ be the largest length. A codeword of length $\ell_i$ can be extended to a string of length $\ell_{\max}$ in $2^{\ell_{\max} - \ell_i}$ ways. No string of length $\ell_{\max}$ extends two different codewords: if it did, both would be beginnings of the same string, and the shorter would be a prefix of the longer (or they would be equal), which a prefix code forbids. So the sets of extensions are disjoint, and together they contain at most all $2^{\ell_{\max}}$ strings of that length:
$$\sum_{i=1}^{m} 2^{\ell_{\max} - \ell_i} \le 2^{\ell_{\max}}.$$
Dividing by $2^{\ell_{\max}}$ gives the inequality. $\square$
Proof of (b). The plan is to hand out codewords in order of length, each time taking the first string that is still free. Number the lengths so that $\ell_1 \le \ell_2 \le \cdots \le \ell_m$, and let
$$c_i = \sum_{j < i} 2^{-\ell_j}$$
be the budget spent before codeword $i$, with $c_1 = 0$. Two facts about $c_i$ are needed. First, it is a whole multiple of $2^{-\ell_i}$: each earlier term is $2^{-\ell_j} = 2^{\ell_i - \ell_j} \cdot 2^{-\ell_i}$, and $\ell_i - \ell_j \ge 0$. Second, $c_i + 2^{-\ell_i} \le \sum_{j} 2^{-\ell_j} \le 1$. So $c_i = k_i / 2^{\ell_i}$ for an integer $k_i$ with $0 \le k_i \le 2^{\ell_i} - 1$. Let codeword $i$ be $k_i$ written in binary with exactly $\ell_i$ digits, padded with zeros on the left. In other words, codeword $i$ is the first $\ell_i$ digits after the point in the binary expansion of $c_i$.
This is a prefix code. Take $i < j$ and suppose codeword $i$ were a prefix of codeword $j$. The numbers whose binary expansions begin with the $\ell_i$ digits of codeword $i$ are those in the interval from $c_i$ up to but not including $c_i + 2^{-\ell_i}$, so $c_j$ would lie in that interval. But $c_j \ge c_{i+1} = c_i + 2^{-\ell_i}$, a contradiction. Codeword $j$ cannot be a prefix of codeword $i$ either: it is at least as long, so it would have to equal codeword $i$, which makes codeword $i$ a prefix of codeword $j$, the case just excluded. $\square$
On the vowels. The prefix code in the table above has lengths 2, 2, 2, 3, 3 and Kraft sum $\tfrac34 + \tfrac28 = 1$: the budget is spent exactly. The useless code has lengths 1, 1, 2, 2, 2 and Kraft sum $1 + \tfrac34 = \tfrac74$, so by part (a) no prefix code has those lengths. The fixed-length code has Kraft sum $\tfrac58$, which leaves room: three of the eight strings of length 3 are unused. For the lengths 2, 3, 3, 3, 4, whose Kraft sum is $\tfrac{11}{16}$, the construction of part (b) gives $c = 0, \tfrac14, \tfrac38, \tfrac12, \tfrac58$ and the codewords 00, 010, 011, 100, 1010.
The script runs the construction on all 271 lists of up to six lengths between 1 and 5 whose Kraft sum is at most 1 and confirms a prefix code each time. For every list of up to five lengths between 1 and 3 whose Kraft sum exceeds 1, an exhaustive search finds no prefix code.
Infinitely many codewords. The integer codes below give a codeword to every positive integer. Both parts of the theorem hold for a countably infinite list of lengths. For (a), every finite part of an infinite prefix code is a prefix code, so every partial sum of the series is at most 1, and so is its limit. For (b), a convergent Kraft sum allows at most $2^{\ell}$ lengths equal to $\ell$, so the lengths can be listed in nondecreasing order, and the construction and its proof go through unchanged, one codeword at a time.
Uniquely decodable codes gain nothing
Prefix codes are a convenience. Could a code that is uniquely decodable without being a prefix code, like 0, 01, 11, have shorter codewords than any prefix code? It could not: such codes obey the same inequality.
Theorem (McMillan's inequality). The codeword lengths of any uniquely decodable binary code satisfy $\sum_i 2^{-\ell_i} \le 1$.
The idea is to look at long messages. Unique decodability says that different sequences of $k$ symbols give different bit strings, and there are only so many bit strings of each length. That caps the $k$th power of the Kraft sum by a quantity that grows only in proportion to $k$, which is possible only if the sum is at most 1.
Proof. Let $S = \sum_{i=1}^{m} 2^{-\ell_i}$ and let $\ell_{\max}$ be the largest length. Fix $k \ge 1$ and expand the $k$th power, one term for each sequence $(i_1, \dots, i_k)$ of $k$ symbols:
$$S^k = \sum_{i_1, \dots, i_k} 2^{-(\ell_{i_1} + \cdots + \ell_{i_k})}.$$
The exponent $\ell_{i_1} + \cdots + \ell_{i_k}$ is the length of the bit string that encodes the sequence. It lies between $k$ and $k\,\ell_{\max}$. Let $N_t$ be the number of sequences of $k$ symbols whose encoding has length $t$. Because the code is uniquely decodable, these sequences have $N_t$ different encodings, all of them bit strings of length $t$, so $N_t \le 2^t$. Grouping the terms by $t$,
$$S^k = \sum_{t = k}^{k\ell_{\max}} N_t\,2^{-t} \le \sum_{t = k}^{k\ell_{\max}} 2^{t}\,2^{-t} = k\,\ell_{\max} - k + 1 \le k\,\ell_{\max}.$$
This holds for every $k$. If $S$ were greater than 1, the left side would grow geometrically in $k$ and the right side only linearly, so the inequality would fail for large $k$. Hence $S \le 1$. For a code with infinitely many codewords, apply the result to each finite part. $\square$
Combined with part (b) of Kraft's theorem, this says that whatever lengths a uniquely decodable code has, a prefix code has the same lengths. Nothing is lost by using prefix codes only. The script checks the theorem by enumeration, on the 1,470 codes with at most four distinct codewords of length at most 3. It decides unique decodability by a test that follows the leftover suffixes of overlapping codewords until one is a codeword or none is new. It finds 686 uniquely decodable codes, 458 of them prefix codes and 228 not, and every one of the 686 has a Kraft sum of at most 1.
The two results have separate origins. In MacKay's account (2003, Section 5.2), Kraft proved that a prefix code exists whenever the inequality holds, and McMillan (1956) proved that unique decodability implies the inequality. MacKay suggests the name Kraft–McMillan inequality for that reason. McMillan's abstract states his half for an alphabet of any size: if every string of words drawn from a list of words over an alphabet of $a$ letters is uniquely decipherable, then the word lengths $l_i$ satisfy $\sum_i a^{-l_i} \le 1$. The abstract presents the result as extending a remark of J. L. Doob, "who derived the same inequality for lists of a more restricted kind", and does not name Kraft; only the abstract of the note was read for this article. The work of Kraft's listed in the references is his 1949 master's thesis; it was not consulted, and what it proves is stated here on MacKay's authority.
The source coding bound
Kraft's inequality limits the lengths. The frequencies of the symbols now decide how to spend the budget, and the bound on the result is the entropy.
Theorem (source coding bound). Let $X$ have mass function $p$ with finite entropy. Every uniquely decodable binary code for $X$ has expected length
$$L \ge H(p) \quad \text{(in bits)},$$
with equality exactly when $\ell(x) = \log_2\frac{1}{p(x)}$ for every $x$ in the support of $p$.
The plan of the proof is to read the lengths as a probability distribution. A length $\ell$ behaves like the probability $2^{-\ell}$, and the expected length is then a cross-entropy, which Gibbs' inequality bounds below by the entropy.
Proof. Let $z = \sum_x 2^{-\ell(x)}$ be the Kraft sum over a set of symbols that contains the support of $p$: the support itself, or the whole alphabet. Define
$$q(x) = \frac{2^{-\ell(x)}}{z},$$
a mass function on that set, called the distribution implied by the code. Then $\ell(x) = \log_2\frac{1}{q(x)} - \log_2 z$, and
$$L = \sum_x p(x)\,\ell(x) = \sum_x p(x)\log_2\frac{1}{q(x)} - \log_2 z = H(p, q) + \log_2\frac{1}{z} = H(p) + D(p \,\|\, q) + \log_2\frac{1}{z}. \qquad (1)$$
By McMillan's inequality $z \le 1$, so $\log_2\frac1z \ge 0$. By Gibbs' inequality $D(p \,\|\, q) \ge 0$, with equality exactly when $q = p$ (Cross-Entropy and Kullback–Leibler Divergence, section "Gibbs' inequality"). Hence $L \ge H(p)$. Equality needs both $z = 1$ and $q = p$, which together say $2^{-\ell(x)} = p(x)$ on the support (and then no symbol outside the support has a codeword, since the Kraft budget is spent). Conversely, if $2^{-\ell(x)} = p(x)$ on the support then, with $z$ taken over the support, $z = 1$, $q = p$, and $L = H(p)$. $\square$
There is a shorter route to the inequality alone. Cross-Entropy and Kullback–Leibler Divergence proves Gibbs' inequality for any nonnegative numbers $q(x)$ that sum to at most 1, not only for mass functions. The numbers $2^{-\ell(x)}$ are of that kind, by McMillan's inequality, and for them the inequality reads $\sum_x p(x)\log_2\frac{p(x)}{2^{-\ell(x)}} \ge 0$, which is $L - H(p) \ge 0$. The proof above normalizes the numbers first. It uses the same two facts, and in exchange it shows where the excess goes: into a divergence and into unspent budget, separately.
Identity (1) is worth more than the bound. It splits the cost of any code into three parts. The first is the entropy, which no code avoids. The second is the divergence of the source from the distribution the code implies, which is the price of a code designed for the wrong frequencies. The third is $\log_2\frac1z$, the price of leaving part of the Kraft budget unspent. A code is a distribution in disguise, and choosing a code is choosing a model of the source.
Equality requires every probability to be a power of $\tfrac12$. For other sources the ideal lengths $\log_2\frac{1}{p(x)}$ are not whole numbers, and the bound cannot be met by a code that assigns one codeword to each symbol. For the vowels the ideal lengths are 1.61, 2.13, 2.38, 2.66 and 3.44 bits. How close a real code can come is settled by the next two sections.
The bound is the half of Shannon's source coding theorem that says what cannot be done. Shannon (1948, Section 9, Theorem 9) stated the theorem for a source of entropy $H$ bits per symbol sent over a noiseless channel: no encoding transmits at an average rate above the channel's capacity divided by $H$. MacKay (2003, Section 5.3) gives the proof used here, through the implied probabilities and Gibbs' inequality.
Shannon's code: within one bit
The ideal length is $\log_2\frac{1}{p(x)}$. The simplest way to make it a whole number is to round up.
Theorem (Shannon code). The lengths $\ell(x) = \left\lceil \log_2\frac{1}{p(x)} \right\rceil$ satisfy Kraft's inequality, and the prefix code built from them has
$$H(p) \le L < H(p) + 1.$$
Proof. Rounding up gives $\ell(x) \ge \log_2\frac{1}{p(x)}$, so $2^{-\ell(x)} \le p(x)$ and $\sum_x 2^{-\ell(x)} \le \sum_x p(x) = 1$. By part (b) of Kraft's theorem a prefix code with these lengths exists. Rounding up adds less than 1, so $\ell(x) < \log_2\frac{1}{p(x)} + 1$. Multiplying by $p(x)$ and summing gives $L < H(p) + 1$. The lower bound is the source coding bound. $\square$
Shannon gave this code in his second proof of Theorem 9 (1948, Section 9): arrange the messages in order of decreasing probability, and encode message $s$ by expanding the cumulative probability of the messages before it as a binary number to $m_s$ places, where $m_s$ is the integer with $\log_2\frac{1}{p_s} \le m_s < 1 + \log_2\frac{1}{p_s}$. That is the construction in the proof of Kraft's theorem, with the probabilities themselves as the budget. Shannon adds that the method is substantially the same as one found independently by R. M. Fano.
On the vowels. Rounding the ideal lengths up gives 2, 3, 3, 3, 4, the list for which the codewords 00, 010, 011, 100, 1010 were built above. The expected length is 2.7638 bits, which is 0.5539 above the entropy of 2.2099. Identity (1) accounts for the excess. The Kraft sum is $\tfrac{11}{16}$, so $\log_2\tfrac{16}{11} = 0.5406$ bits are lost to unused budget, and the remaining 0.0133 bits are the divergence of the vowel shares from the implied distribution. Nearly all of the loss is waste that a better choice of lengths could recover.
The price of the wrong model. The same argument answers a second question, and the answer is what gives cross-entropy its meaning. Suppose the code is built from a distribution $q$, a model or an estimate, and the symbols really follow $p$. Assume $q(x) > 0$ wherever $p(x) > 0$. Otherwise some symbol that occurs has no codeword, and the cross-entropy is infinite. Let $\ell(x) = \left\lceil \log_2\frac{1}{q(x)} \right\rceil$. These lengths satisfy Kraft's inequality as before, and $\log_2\frac{1}{q(x)} \le \ell(x) < \log_2\frac{1}{q(x)} + 1$. Taking the expectation under $p$ gives
$$H(p, q) \le L < H(p, q) + 1.$$
So the cross-entropy $H(p, q)$ in bits is, to within one bit, the average length of the code built for $q$ when the source is $p$. The divergence $D(p \,\|\, q) = H(p, q) - H(p)$ is what believing $q$ costs per symbol.
Huffman's code and its optimality
Rounding up wastes budget. Which lengths are the best possible? Huffman (1952) gave a construction that answers the question exactly. It builds the code tree from the leaves:
- Take the two least probable symbols. Make them the two children of a new node, one reached by
0and one by1. - Replace the two symbols by a single merged symbol whose probability is the sum of theirs.
- Repeat until one symbol, the root, is left. The codeword of each original symbol is the path from the root to its leaf.
On the vowels. The two least probable vowels are u (0.0923) and i (0.1581). They merge into a node of weight 0.2504. Among e (0.3285), o (0.2284), a (0.1927) and the new node (0.2504), the two smallest are now a and o, which merge into a node of weight 0.4211. Then the node of 0.2504 and e merge into 0.5789, and finally 0.4211 and 0.5789 merge into the root. Reading the tree from the root gives e, o and a depth 2 and i and u depth 3: the lengths 2, 2, 2, 3, 3 of the prefix code in the first table. Each merge adds one bit to the codeword of every symbol beneath it, so the expected length is the sum of the merged weights,
$$L = 0.2504 + 0.4211 + 0.5789 + 1 = 2.2504 \ \text{bits},$$
only 0.0404 above the entropy. The Kraft sum is 1, so by identity (1) all of that excess is divergence: the code is exactly right for a source with probabilities $\tfrac14, \tfrac14, \tfrac14, \tfrac18, \tfrac18$, and the vowels are close to it.
Theorem (optimality of Huffman's code). For a source with finitely many symbols, no uniquely decodable binary code has a smaller expected length than the code Huffman's construction produces.
Here is the plan. By the previous two sections it is enough to compare prefix codes. We show that some best prefix code makes the two least probable symbols siblings at the greatest depth, which is Huffman's first step. Merging those siblings turns a code for $m$ symbols into a code for $m - 1$ symbols and lowers the expected length by a fixed amount, so the best code for $m$ symbols comes from the best code for $m - 1$, and induction finishes the proof.
Proof. Let the symbols be $1, \dots, m$ with probabilities $p_1 \ge p_2 \ge \cdots \ge p_m > 0$ and $m \ge 2$. By McMillan's inequality and part (b) of Kraft's theorem, every uniquely decodable code has the lengths of some prefix code, so it suffices to show that the Huffman code has the least expected length among prefix codes.
A best prefix code exists. The fixed-length code with $B = \lceil \log_2 m \rceil$ bits has expected length $B$. A code that gives some symbol a length above $B/p_m$ has expected length above $B$, because that symbol alone contributes more than $p_m \cdot B/p_m$. So only codes with all lengths at most $B/p_m$ can be best. There are finitely many lists of such lengths, hence finitely many values of $L$ to compare, and the least of them is attained. Call a prefix code optimal if it attains it.
Step 1: in an optimal code every codeword of greatest length has a sibling. Two codewords are siblings if they differ only in their last bit. Let $w$ be a codeword of the greatest length $\ell_{\max}$ in an optimal code, and let $w'$ be $w$ with its last bit flipped. If $\ell_{\max} = 1$, every codeword has one bit; there are $m \ge 2$ of them and they are distinct, so they are 0 and 1, and $w'$ is a codeword. Let $\ell_{\max} \ge 2$, and suppose $w'$ were not a codeword. Let $u$ be $w$ without its last bit, which is not empty, and replace $w$ by $u$. The result is still a prefix code. A codeword that is a prefix of $u$ would be a prefix of $w$, which is impossible. A codeword that $u$ is a prefix of would have to be longer than $u$ (it cannot equal $u$, which is a prefix of $w$), so it has length $\ell_{\max}$ and is $u$ followed by one bit, that is, $w$ or $w'$. The first has been removed and the second is not a codeword. The new code is shorter by one bit for a symbol of positive probability, so the original was not optimal. Hence $w'$ is a codeword.
Step 2: some optimal code makes symbols $m - 1$ and $m$ siblings. Take an optimal code and, by step 1, two sibling codewords $w$ and $w'$ of length $\ell_{\max}$, belonging to symbols $a$ and $b$. If one of them is symbol $m$, name it $a$. Otherwise exchange the codewords of $a$ and $m$. The expected length changes by
$$(p_a\ell_m + p_m\ell_a) - (p_a\ell_a + p_m\ell_m) = (p_a - p_m)(\ell_m - \ell_a) \le 0,$$
because $p_a \ge p_m$ and $\ell_m \le \ell_{\max} = \ell_a$. The code was optimal, so the change is 0 and the new code is optimal too, with symbol $m$ holding $w$. Now $b$ is a symbol other than $m$, so $p_b \ge p_{m-1}$. If $b$ is not $m - 1$, exchange the codewords of $b$ and $m - 1$; by the same calculation the code stays optimal. Symbols $m - 1$ and $m$ now hold the siblings $w$ and $w'$.
Step 3: merging and splitting. Write $s = p_{m-1} + p_m$. The reduced source has $m - 1$ symbols: the symbols $1, \dots, m - 2$ with their probabilities, and one merged symbol with probability $s$. Codes for the two sources correspond as follows.
- Splitting. Given a prefix code for the reduced source in which the merged symbol has codeword $u$, give symbols $m - 1$ and $m$ the codewords $u0$ and $u1$ and keep the rest. This is a prefix code. A codeword $v$ of another symbol cannot be a prefix of $u0$: it is not $u0$ (then $u$ would be a prefix of $v$), so it would be a prefix of $u$. And $u0$ cannot be a prefix of $v$, since then $u$ would be. The same holds for $u1$. The two new codewords are one bit longer than $u$, so the expected length rises by exactly $s$.
- Merging. Given a prefix code for the original source in which symbols $m - 1$ and $m$ hold siblings $u0$ and $u1$, give the merged symbol the codeword $u$ and keep the rest. This is a prefix code. If $u$ were a prefix of another codeword $v$, then $v$ would be longer than $u$ (if $v = u$, it would be a prefix of $u0$) and would begin with $u0$ or $u1$, making one of those a prefix of $v$. If $v$ were a prefix of $u$, it would be a prefix of $u0$. The expected length falls by exactly $s$.
Step 4: induction on $m$. For $m = 2$ Huffman's construction gives the codewords 0 and 1, with expected length 1, and no code has a codeword shorter than one bit, so it is optimal. Suppose the construction is optimal for every source with $m - 1$ symbols, and consider a source with $m \ge 3$ symbols. Huffman's construction merges two least probable symbols. Number the symbols so that these are $m - 1$ and $m$; where probabilities are tied, any such numbering still has $p_1 \ge \cdots \ge p_m$, which is all that step 2 used. The construction then builds its code $C'$ for the reduced source, and splits. By the induction hypothesis $C'$ is optimal for the reduced source, with expected length $L'$. The Huffman code $C$ for the original source therefore has expected length $L' + s$. Now let $D$ be any prefix code for the original source. By step 2 there is an optimal code $D^*$ in which $m - 1$ and $m$ are siblings, and $L(D^*) \le L(D)$. Merging $D^*$ gives a prefix code for the reduced source with expected length $L(D^*) - s$, which is at least $L'$ because $C'$ is optimal. So
$$L(D) \ge L(D^*) \ge L' + s = L(C).$$
No prefix code is better than the Huffman code. $\square$
Cover and Thomas (2006) treat the result in their Section 5.8, "Optimality of Huffman Codes", and MacKay (2003, Exercise 5.16 and its solution) proves it by comparing the Huffman code with a rival. The script checks the theorem against brute force on 300 random sources of two to six symbols: in each, the Huffman expected length equals the minimum over every list of lengths that satisfies Kraft's inequality.
Since the Shannon code is one prefix code among those Huffman's is compared with, the Huffman code inherits its guarantee: $H(p) \le L_{\text{Huffman}} < H(p) + 1$.
The 65 characters. For the character frequencies of the whole text, the three benchmarks are:
| Code for one character | Bits per character |
|---|---|
| Fixed length, 7 bits (enough for 65) | 7 |
| Shannon code | 5.3058 |
| Huffman code | 4.8170 |
| Entropy (lower bound) | 4.7794 |
The Huffman code is 0.0377 bits above the entropy. Its shortest codeword, for the space, has 3 bits; e has 4, q 11, Z 12, and the dollar sign shares the longest, 15 bits, with the ampersand. The dollar sign occurs once in the file. The Shannon code agrees on the space, e and q, gives Z 13 bits, and spends 21 bits on the dollar sign, whose ideal length is 20.09. Its Kraft sum is 0.7047, so nearly three tenths of its budget is unused. With the Huffman code the file takes 0.672 megabytes, 60.2 percent of the 1.115 megabytes it takes at eight bits per character and well under the 0.976 megabytes of a seven-bit code.
Closing the last bit: codes on blocks
A code that gives each symbol its own codeword cannot spend less than one bit on any symbol, however predictable the source. The remedy is to encode several symbols at once.
Theorem (block coding). Let $X_1, X_2, \dots$ be independent with the same mass function $p$. For each $n$ there is a prefix code for blocks $(X_1, \dots, X_n)$ whose expected length $L_n$ satisfies
$$H(p) \le \frac{L_n}{n} < H(p) + \frac{1}{n},$$
and no uniquely decodable code for blocks of $n$ has $L_n/n < H(p)$.
Proof. A block is a single symbol from the alphabet of all sequences of length $n$, with probability $p(x_1)\cdots p(x_n)$. Its entropy is $H(X_1, \dots, X_n) = n\,H(p)$, because the entropies of independent variables add (Entropy, subadditivity with its case of equality). Apply the source coding bound and the Shannon code theorem to this one symbol: $nH(p) \le L_n < nH(p) + 1$. Divide by $n$. $\square$
So the entropy is not only a lower bound but the exact limit of what coding can achieve. The cost per symbol can be brought as close to $H(p)$ as desired, and never below. This is Shannon's theorem for a source of independent symbols. The price is the size of the code, since a block code needs a codeword for each of $|\mathcal{X}|^n$ blocks.
Space or not. A source with two symbols shows the effect most clearly. Of the 1,115,394 characters of the text, 169,892 are spaces, a share of 0.1523. Consider a source that emits "space" with that probability and "other" otherwise, independently each time. Its entropy is 0.6156 bits, but any code for single symbols spends exactly 1 bit. Huffman codes on blocks do better:
| Block length $n$ | Huffman, bits per symbol | Upper bound $H + 1/n$ |
|---|---|---|
| 1 | 1.0000 | 1.6156 |
| 2 | 0.7169 | 1.1156 |
| 3 | 0.6356 | 0.9489 |
| 4 | 0.6256 | 0.8656 |
| 6 | 0.6279 | 0.7823 |
| 8 | 0.6202 | 0.7406 |
| 10 | 0.6197 | 0.7156 |
Example (longer blocks are not always better). Blocks of six cost 0.6279 bits per symbol and blocks of four cost 0.6256. The theorem promises only that $L_n/n$ lies between $H$ and $H + 1/n$, and that interval shrinks; it does not promise that each increase of $n$ helps. How well whole-number lengths fit the block probabilities varies from one $n$ to the next.
The characters of a real text are not independent, so its limit is at most the entropy of its character frequencies, and for this text it is well below, as the table of context models at the end of this article shows. For a source with memory the limit is the entropy per symbol of long blocks, the entropy rate. The theorem that a single long sample reveals it for stationary ergodic sources is cited here, not proved (the Shannon–McMillan–Breiman theorem; Jurafsky and Martin, 2026, Section 3.7, state it and give the references). The models at the end of this article approach that limit from above by conditioning on earlier characters.
Codes for the integers, as distributions
Index Compression stores the postings of Reuters-21578 as gaps and encodes each gap with a code for the positive integers: variable byte, Elias gamma, Elias delta, or a Rice code. It shows that the Kraft sum of the gamma code is exactly 1. Identity (1) turns that observation into a complete account of each code. A code with Kraft sum $z$ implies the distribution $q(G) = 2^{-\ell(G)}/z$ on gaps, and its average length on gaps distributed as $p$ is $H(p) + D(p \,\|\, q) + \log_2\frac1z$. Here $z$ is the sum over all positive integers, not only over the gaps that occur, so the codewords a code reserves for gaps that never occur count toward the divergence, not toward the unused budget.
The pooled distribution of the 725,793 gaps has 8,911 distinct values and an entropy of 7.19 bits. The worked problems below show that the gamma and delta codes have Kraft sum 1 and the variable byte code $\tfrac{127}{128}$. The table gives each code's average length, and the divergence of the gap distribution from the distribution the code implies:
| Code | Bits per gap | Divergence $D(p \,\|\, q)$, bits | Unused budget $\log_2\frac1z$, bits |
|---|---|---|---|
| Entropy of the gaps | 7.19 | ||
| Huffman code for the pooled gaps | 7.21 | 0.03 | 0 |
| Shannon code for the pooled gaps | 7.64 | ||
| Elias delta | 8.08 | 0.90 | 0 |
| Elias gamma | 8.63 | 1.44 | 0 |
| Variable byte | 9.57 | 2.37 | 0.0113 |
The three rows from Index Compression are reproduced exactly, and each excess over 7.19 bits is now explained. The gamma code is the Shannon code of the distribution $q_\gamma(G) = 2^{-(2\lfloor\log_2 G\rfloor + 1)}$, which lies between $1/(2G^2)$ and $2/G^2$, and the Reuters gaps are 1.44 bits per gap away from that distribution. The delta code's implied distribution is closer, at 0.90 bits. In the language of the last section of this article, the gaps are as unpredictable as a uniform choice among $2^{7.19} = 146$ values, although 8,911 occur. Measured on these gaps, the gamma code's model has perplexity $2^{8.63}$, about 395: it codes them as if each were a uniform choice among about 395 values. That number belongs to the pair of code and data. The distribution $q_\gamma$ itself has an entropy of only 3 bits, a perplexity of 8, because half of its probability is on the gap 1. A gap of 1, which is 15.0 percent of all gaps, has an ideal length of 2.73 bits. The Huffman code gives it 3, the gamma code 1, and the variable byte code 8.
The Huffman code for the pooled gaps comes within 0.030 bits of the entropy, and would store the postings in 0.655 megabytes against the 0.783 of the gamma code (the entropy bound is 0.652). It is not what an index uses, and the comparison is not a fair one. The Huffman code is fitted to this collection. Its table of 8,911 codewords, up to 19 bits long, must be stored and consulted, and it has no codeword for a gap that did not occur. The gamma and delta codes are fixed in advance, cover every positive integer, and decode by counting bits. The bound also concerns only codes that give each gap value one codeword for the whole collection. A code that changes with the postings list, such as a Rice code with a parameter per list, is a different model, one distribution per list, and can go below the pooled entropy.
Perplexity
A language model assigns a probability to each possible next symbol given what came before. Write $q(x_i \mid c_i)$ for the probability the model gives to the symbol $x_i$ that actually occurred at position $i$ of a test text, where $c_i$ is the context the model sees, the earlier symbols or as many of them as it uses. For a test text of $N$ symbols, the model's average loss, or empirical cross-entropy, is
$$\hat{H}_b = -\frac{1}{N}\sum_{i=1}^{N}\log_b q(x_i \mid c_i),$$
in bits per symbol for $b = 2$ and nats per symbol for $b = e$. This is the quantity that training minimizes as the cross-entropy loss; Cross-Entropy and Kullback–Leibler Divergence shows that it is the average negative log-likelihood. The perplexity of the model on the text is
$$\mathrm{PP} = b^{\hat{H}_b} = \left(\prod_{i=1}^{N} q(x_i \mid c_i)\right)^{-1/N}.$$
Jurafsky and Martin (2026, Section 3.3) define perplexity by the second form, as the inverse probability of the test set normalized by the number of words, and derive the first form in their Section 3.7. The word comes from speech recognition. Jelinek, Mercer, Bahl and Baker (1977), writing from the IBM Thomas J. Watson Research Center, proposed it in a meeting abstract as a measure of the difficulty of a recognition task, after showing that vocabulary size and branching factors are inadequate ones: "Information theoretic arguments show that perplexity (the logarithm of which is the familiar entropy) is a more appropriate measure of equivalent choice." Jurafsky and Martin (2026, Chapter 3, "Historical Notes") state that the term was first used for this technology by the IBM group.
When the model ignores context, $q(x_i \mid c_i) = q(x_i)$, the sum can be grouped by symbol. If $\hat{p}(x)$ is the share of the test text's symbols equal to $x$, then $\hat{H}_b = -\sum_x \hat{p}(x)\log_b q(x) = H(\hat{p}, q)$, the cross-entropy of the unit's notation, and $\mathrm{PP} = b^{H(\hat{p}, q)}$. With context, the same grouping over pairs of context and symbol gives a conditional cross-entropy. Five properties follow from the definition.
1. Perplexity does not depend on the base. Changing the base multiplies $\hat{H}$ by a constant and changes the base of the power to match: $2^{\hat{H}_2} = e^{\hat{H}_e}$, because $\hat{H}_2 = \hat{H}_e/\ln 2$ and $2^{1/\ln 2} = e$. The second form of the definition contains no logarithm at all. A loss must state its unit; a perplexity has none.
2. A uniform model on $V$ symbols has perplexity $V$. Every factor is $1/V$, so the product is $V^{-N}$ and its $-1/N$ power is $V$. This is the sense in which perplexity counts choices: a model with perplexity 12 was, on average, as uncertain as a uniform guess among 12 symbols. In bits, $\log_2 \mathrm{PP}$ is the average number of yes-or-no questions' worth of uncertainty per symbol.
3. Perplexity is a geometric mean, and that matters. $\mathrm{PP}$ is the geometric mean of the reciprocal probabilities $1/q(x_i \mid c_i)$. By Jensen's inequality for the concave function $\ln$ (Probability Inequalities, section "Jensen's inequality"), applied to the $N$ values with equal weights, the mean of the logarithms is at most the logarithm of the mean. Applied to the values $q_i = q(x_i \mid c_i)$ and to the values $1/q_i$ this gives
$$\frac{1}{\frac1N\sum_i q_i} \le \mathrm{PP} \le \frac1N\sum_i \frac{1}{q_i}.$$
Example (perplexity 12 does not mean a probability of 1/12 on average). The add-one bigram model of The Bigram Language Model has perplexity 11.96 on the validation text, so the geometric mean of the probabilities it gave to the characters that occurred is $1/11.96 = 0.0836$. The arithmetic mean of those probabilities is 0.1519, nearly twice as large. Its reciprocal, 6.58, is the lower bound in the display. The arithmetic mean of the reciprocals, the upper bound, is 43.3. Perplexity lies between them and is pulled toward the positions where the model was badly wrong, because a single probability near zero multiplies the whole product. One probability of exactly zero makes the perplexity infinite, which is why the models below are smoothed.
4. No model beats the entropy, in two senses. On the test text itself, a model without context has $\hat{H} = H(\hat{p}, q) \ge H(\hat{p})$ by Gibbs' inequality, so its perplexity is at least $b^{H(\hat{p})}$, the perplexity of the text's own frequencies. The validation text has a character entropy of 4.81 bits, so no context-free model has perplexity below $2^{4.81} = 28.1$ on it. The training frequencies reach 28.4, and the difference of 0.014 bits is the divergence of the validation text's frequencies from the smoothed training frequencies. In expectation, if the symbols are drawn from a true distribution $p$, the expected loss of any model $q$ is $H(p, q) \ge H(p)$. A model's cross-entropy is an upper bound on the entropy of the source, and the gap is the divergence.
5. Bits per symbol is a code length. A model defines a probability for every text of length $N$,
$$Q(x_1, \dots, x_N) = \prod_{i=1}^{N} q(x_i \mid c_i),$$
and these probabilities sum to 1 over all texts of length $N$, because summing over the last symbol first gives 1 for each context, then the same for the symbol before, and so on. So $Q$ is a mass function on texts, and the Shannon code for it gives the text $x_1 \dots x_N$ a codeword of
$$\left\lceil \log_2\frac{1}{Q(x_1, \dots, x_N)} \right\rceil = \left\lceil N\hat{H}_2 \right\rceil < N\hat{H}_2 + 1 \ \text{bits}.$$
The whole text can be written in $N\log_2\mathrm{PP}$ bits plus at most one. A model with perplexity $\mathrm{PP}$ is a compressor that spends $\log_2 \mathrm{PP}$ bits per symbol, and the source coding bound is the reason no model's expected loss goes below the entropy.
Measured on the site's small language models
The walkthrough's models are trained on the first 90 percent of the text, 1,003,854 characters, and validated on the last 10 percent, 111,540 characters. The simplest language models on those splits are tables of counts: a model with context length $k$ predicts the next character from the $k$ before it, with probability
$$q(x \mid c) = \frac{\operatorname{count}(c\,x) + \alpha}{\operatorname{count}(c) + 65\alpha}$$
from the training counts, where $\alpha > 0$ is a smoothing constant that keeps unseen continuations from having probability zero. Context length 0 is the character frequencies, and context length 1 is the bigram table that The Bigram Language Model trains by gradient descent. The table gives the loss in bits per character. The training column uses the counts themselves ($\alpha = 0$) on the training text, which is the lowest loss any model with that context can reach there.
| Context $k$ | Contexts seen | Training, bits | Validation, $\alpha = 1$ | $\alpha = 0.1$ | $\alpha = 0.01$ |
|---|---|---|---|---|---|
| 0 | 1 | 4.77 | 4.83 | 4.83 | 4.83 |
| 1 | 65 | 3.54 | 3.58 | 3.58 | 3.59 |
| 2 | 1,380 | 2.75 | 2.98 | 2.95 | 2.98 |
| 3 | 11,228 | 2.15 | 2.82 | 2.57 | 2.59 |
| 4 | 48,539 | 1.75 | 3.14 | 2.58 | 2.55 |
| 5 | 133,293 | 1.42 | 3.74 | 2.96 | 2.89 |
| 6 | 264,623 | 1.10 | 4.37 | 3.52 | 3.41 |
As perplexities, $2^{\text{bits}}$:
| Context $k$ | Training perplexity | Best validation perplexity |
|---|---|---|
| 0 | 27.4 | 28.4 |
| 1 | 11.6 | 12.0 |
| 2 | 6.7 | 7.7 |
| 3 | 4.4 | 6.0 |
| 4 | 3.4 | 5.9 |
| 5 | 2.7 | 7.4 |
| 6 | 2.1 | 10.7 |
Three things can be read from this experiment.
- Context is worth bits. A uniform guess among 65 characters costs $\log_2 65 = 6.02$ bits. Knowing one earlier character lowers the validation loss from 4.83 to 3.58 bits, and four earlier characters bring it to 2.55 bits, a perplexity of 5.9 (1.77 nats). The rows for context 0 and 1 agree with the reference losses in The Bigram Language Model: 3.35 and 2.48 nats on validation, perplexities 28.4 and 12.0.
- The training loss says little about the model. At context 6 the training text costs 1.10 bits per character and the validation text 3.41. With 264,623 distinct contexts in a million characters, most contexts were seen a handful of times, and the table has memorized what followed them. Perplexity is meaningful only on text the model was not fitted to. Jurafsky and Martin (2026, Section 3.3) make the same point about test sets.
- Where the Transformer stands. In the run described in Scaling the Shakespeare GPT, the final model's validation loss is 1.48 nats per character. That is $1.48/\ln 2 = 2.14$ bits, a perplexity of $e^{1.48} = 4.4$, below every count-based model here. The figure is taken from that article; no neural model was trained for this one.
These are observations about one text and one family of smoothed tables. Better smoothing would lower the validation losses at long contexts; the table shows the pattern, not the best that counting can do.
Perplexity per token is not perplexity per character
The walkthrough's last model reads the text as tokens produced by byte-pair encoding (A BPE-Tokenized Shakespeare GPT). Trained as that article describes, the tokenizer has a vocabulary of 12,715 tokens. It turns the training split into 274,795 tokens and the validation split into 31,856, which is 0.2856 tokens per character, or 3.50 characters per token. Count-based models of the tokens give:
| Model of the validation text | Bits per token | Perplexity per token | Bits per character |
|---|---|---|---|
| Uniform over 12,715 tokens | 13.63 | 12,715 | 3.89 |
| Token frequencies, $\alpha = 1$ | 8.96 | 499 | 2.56 |
| Token frequencies, $\alpha = 0.1$ | 9.03 | 524 | 2.58 |
| Token bigrams interpolated with frequencies | 7.98 | 252 | 2.28 |
| Character model, context 4, $\alpha = 0.01$ | 5.9 per character | 2.55 |
The interpolated model gives each token half the weight of its bigram relative frequency and half the weight of its smoothed frequency ($\alpha = 0.1$); the half is a fixed choice, not tuned.
Example (a perplexity of 499 against a perplexity of 5.9). The token-frequency model has perplexity 499 and the character model 5.9, and the two models are about equally good. The perplexities differ because a token is a larger thing to predict than a character. What can be compared is the total code length for the same text, or that total divided by a common unit. The token model spends $8.96 \times 0.2856 = 2.56$ bits per character, against the character model's 2.55. In general, if a text has $N_c$ characters and $N_t$ tokens,
$$\text{bits per character} = \frac{N_t}{N_c} \times \text{bits per token}, \qquad \mathrm{PP}_{\text{per character}} = \mathrm{PP}_{\text{per token}}^{\,N_t/N_c},$$
and $499^{0.2856} = 5.90$. Jurafsky and Martin (2026, Section 3.3) state the rule this example illustrates: the perplexities of two models are comparable only if they use identical vocabularies.
Notice also what the tokenizer alone achieves. A model that knows nothing about token frequencies, the uniform one, already spends 3.89 bits per character, less than the 4.83 of character frequencies. The vocabulary itself records which strings of characters occur. And token frequencies with no context match four characters of context. (The tokenizer was trained on the whole file, as the walkthrough's program trains it, so the vocabulary has seen the validation text. Also, 226 of the validation text's distinct tokens never occur in the training split.)
A model is a compressor
Property 5 can be evaluated on the validation text. No encoder was run for this article: the figure that follows is a code length computed from the model's probabilities, not the size of a file. Under the character model with context 4 and $\alpha = 0.01$, with a uniform guess for the first four characters, $\log_2\frac{1}{Q}$ for the whole text is 284,908.3 bits. The Shannon code's codeword for the text would therefore have 284,909 bits, which is 35.6 kilobytes, or 2.55 bits per character. The text itself is 111.5 kilobytes. For comparison, two general-purpose compressors were run on the validation text alone. Their output files are 44.5 kilobytes (zlib at its highest level, 3.19 bits per character) and 36.7 kilobytes (bz2, 2.64 bits per character).
The comparison needs two cautions beyond that one. The model's code is not self-contained. A decoder must hold the same table of counts, which is far larger than the text, while zlib and bz2 carry everything needed in their output. And the Shannon code for a whole text is a statement that a codeword of that length exists. It is not a practical encoder, since it treats the text as one symbol from an astronomically large alphabet. Arithmetic coding is the practical method. It produces the codeword one symbol at a time from the model's conditional probabilities. MacKay (2003, Section 6.2) states that its output is within two bits of $\log_2\frac{1}{Q}$ for the whole message; that bound is cited here, not proved. On this text an arithmetic coder driven by the same model would therefore produce at most 284,911 bits, still 35.6 kilobytes. With an arithmetic coder, any language model becomes a compressor that spends its cross-entropy. For a decoder that already holds the model, a lower perplexity is then a smaller file, to within two bits for the whole text.
What is proved, what is cited, what the experiment shows
Proved here: Kraft's inequality in both directions, for finite and countably infinite prefix codes; McMillan's inequality for uniquely decodable codes; the source coding bound with its case of equality, through identity (1); the one-bit guarantee of the Shannon code and its form for a mismatched model; the optimality of Huffman's code among all uniquely decodable codes; the block coding theorem for independent symbols; and the five properties of perplexity.
Borrowed, with the proof on a linked page: Gibbs' inequality (Cross-Entropy and Kullback–Leibler Divergence), the additivity of entropy for independent variables (Entropy), and Jensen's inequality (Probability Inequalities).
Cited, not proved: the entropy rate as the limit for sources with memory and the Shannon–McMillan–Breiman theorem; the two-bit bound for arithmetic coding, as MacKay states it; the attribution of the two halves of the inequality to Kraft and McMillan, which follows MacKay's account and, for McMillan's half, the abstract of his note; the origin of the word perplexity, from the abstract of Jelinek, Mercer, Bahl and Baker (1977) and the historical notes of Jurafsky and Martin (2026); and the validation loss of the walkthrough's Transformer, which is the figure reported in the walkthrough.
Shown by computation: every number about the Tiny Shakespeare text and the Reuters gaps. The tables of losses describe count-based models with add-$\alpha$ smoothing on one text with one split; they are not general rankings of context lengths, tokenizers or compressors.
Worked problems
These problems are posed for this article, on the integer codes and Reuters postings of Index Compression, on the Tiny Shakespeare text and on small exact cases, one for each main result. The script tools/experiments/statistics/perplexity-and-source-coding.py checks every number.
Problem 1 (Kraft sums of the integer codes). The codes of Index Compression give a gap $G \ge 1$ a codeword of $2\lfloor\log_2 G\rfloor + 1$ bits (gamma), of $2\lfloor\log_2(k + 1)\rfloor + 1 + k$ bits with $k = \lfloor\log_2 G\rfloor$ (delta), of $j + 1 + k$ bits with $j = \lfloor (G - 1)/2^k \rfloor$ (Rice with parameter $k$), and of $8\lceil(\lfloor\log_2 G\rfloor + 1)/7\rceil$ bits (variable byte). Find the Kraft sum of each over all positive integers, and say what the variable byte code leaves unused.
Solution. The gamma, delta and Rice codes have Kraft sum exactly 1, and the variable byte code $\tfrac{127}{128}$.
Gamma. There are $2^k$ integers with $\lfloor\log_2 G\rfloor = k$, namely $2^k$ to $2^{k+1} - 1$, each with a codeword of $2k + 1$ bits. So the sum is $\sum_{k \ge 0} 2^k \cdot 2^{-(2k+1)} = \sum_{k \ge 0} 2^{-(k+1)} = 1$, as Index Compression shows.
Delta. Write $\ell_\gamma(n) = 2\lfloor\log_2 n\rfloor + 1$. The $2^k$ integers with $\lfloor\log_2 G\rfloor = k$ each have a codeword of $\ell_\gamma(k + 1) + k$ bits, so they contribute $2^k \cdot 2^{-k} \cdot 2^{-\ell_\gamma(k+1)} = 2^{-\ell_\gamma(k+1)}$. Summing over $k \ge 0$ is summing $2^{-\ell_\gamma(n)}$ over $n = k + 1 \ge 1$, which is the gamma sum: 1.
Rice. For each quotient $j \ge 0$ there are $2^k$ gaps, from $j2^k + 1$ to $(j + 1)2^k$, each with $j + 1 + k$ bits. They contribute $2^k \cdot 2^{-(j+1+k)} = 2^{-(j+1)}$, and $\sum_{j \ge 0} 2^{-(j+1)} = 1$.
Variable byte. A gap takes $j$ bytes when it has between $7(j-1) + 1$ and $7j$ binary digits, that is, when $128^{j-1} \le G \le 128^j - 1$. For $j = 1$ that is the 127 gaps from 1 to 127, and for $j \ge 2$ it is $128^j - 128^{j-1} = 127 \cdot 128^{j-1}$ gaps, which is the same formula. Each has a codeword of $8j$ bits, so the sum is
$$\sum_{j \ge 1} 127 \cdot 128^{j-1} \cdot 2^{-8j} = \frac{127}{128}\sum_{j \ge 1}\left(\frac{128}{256}\right)^{j} = \frac{127}{128}\sum_{j \ge 1} 2^{-j} = \frac{127}{128} = 0.9922.$$
The missing $\tfrac{1}{128}$ is two byte patterns that never begin a codeword, each worth $2^{-8} = \tfrac{1}{256}$ of the budget. One is 10000000, which would be the code of a gap of 0. The other is 00000000 as a first byte, which would be a leading group of seven zeros. By identity (1) the unused budget costs $\log_2\tfrac{128}{127} = 0.0113$ bits per gap. That is negligible beside the 2.37 bits of divergence. The variable byte code is expensive on Reuters because its implied distribution fits the gaps poorly, giving every gap up to 127 the same probability, not because it wastes codewords.
All four Kraft sums are at most 1, as Kraft's inequality requires of prefix codes. The script confirms the partial sums in exact arithmetic: over the gaps below $2^K$ the gamma sum is $1 - 2^{-K}$, and over the gaps below $128^k$ the variable byte sum is $\tfrac{127}{128}(1 - 2^{-k})$.
Problem 2 (the distribution a Rice code is right for). For which distribution of gaps does the Rice code with $k = 3$ have expected length equal to the entropy? Find that distribution's mean and entropy, and measure how far the gaps of oil in Reuters-21578 are from it.
Solution. The distribution is $q(G) = 2^{-(j + 4)}$, where $j = \lfloor (G-1)/8 \rfloor$ is the quotient. It has mean 12.5 and entropy 5 bits, and the gaps of oil are 0.16 bits per gap away from it.
By the source coding bound, equality holds exactly when $p(G) = 2^{-\ell(G)}$, and by Problem 1 these values sum to 1, so they form a distribution: $q(G) = 2^{-(\lfloor (G-1)/8 \rfloor + 1 + 3)}$. It is a staircase. The gaps 1 to 8 have probability $\tfrac{1}{16}$ each, the gaps 9 to 16 have $\tfrac{1}{32}$ each, and each further block of eight has half the probability of the block before. The quotient therefore takes the value $j$ with probability $8 \cdot 2^{-(j+4)} = 2^{-(j+1)}$ for $j \ge 0$, and its mean is $\sum_{j \ge 0} j\,2^{-(j+1)} = 1$. (The series is $\tfrac12\sum_j j\,r^j$ at $r = \tfrac12$, and $\sum_j j\,r^j = r/(1-r)^2 = 2$.) Within block $j$ the gaps $8j + 1, \dots, 8j + 8$ are equally likely with average $8j + 4.5$, so the mean gap is $8 \cdot 1 + 4.5 = 12.5$. The entropy equals the expected length, the mean quotient plus 4, which is $1 + 1 + 3 = 5$ bits.
The term oil occurs in 1,038 stories, with a mean gap of 10.4. Index Compression reports that the Rice code with $k = 3$ stores its gaps in 5,000 bits, 4.82 bits per gap, against 5,728 bits, 5.52 per gap, for the gamma code. The 1,038 gaps take 60 distinct values, and the entropy of their distribution is 4.66 bits. By identity (1), with both Kraft sums equal to 1, the divergence of the list's gap distribution from the staircase is $4.82 - 4.66 = 0.16$ bits, and from the gamma code's implied distribution it is $5.52 - 4.66 = 0.86$ bits. The Rice code wins on this list because its implied distribution, which decays geometrically, is the closer model of how the gaps of a frequent term are spread. The entropy of 4.66 bits is that of the list's own frequencies. A code that reached it would have to be built from those 60 frequencies and stored with the list, so it is a benchmark, not an alternative.
Problem 3 (a block code by hand). For the source that emits "space" with probability 0.1523 and "other" with probability 0.8477, build the Huffman code for pairs of symbols, and compare its cost per symbol with the entropy and with the bound of the block coding theorem.
Solution. The code has lengths 1, 2, 3, 3 and costs 0.7169 bits per symbol, between the entropy 0.6156 and the bound 1.1156.
The four pairs have probabilities $0.8477^2 = 0.7186$ (other, other), $0.8477 \times 0.1523 = 0.1291$ (other, space), 0.1291 (space, other) and $0.1523^2 = 0.0232$ (space, space). Huffman's construction merges the two least probable, 0.0232 and 0.1291, into a node of 0.1523; then that node and the remaining 0.1291 into a node of 0.2814; then that node and 0.7186 into the root. The pair (other, other) has depth 1, one mixed pair depth 2, and the other mixed pair and (space, space) depth 3. One assignment is 0 for (other, other), 10 for (other, space), 110 for (space, other) and 111 for (space, space). The expected length is the sum of the merged weights, $0.1523 + 0.2814 + 1 = 1.4337$ bits per pair, which is 0.7169 bits per symbol. (The page's probabilities are rounded to four places; the script uses the exact counts.)
A code for single symbols must spend 1 bit, so pairing saves 0.28 bits per symbol. The entropy is 0.6156 bits, so 0.10 bits per symbol of excess remain, and the theorem's bound for $n = 2$ is $0.6156 + \tfrac12 = 1.1156$. The Kraft sum of the lengths is $\tfrac12 + \tfrac14 + \tfrac28 = 1$, so by identity (1) the excess is entirely the divergence of the pair probabilities from $\tfrac12, \tfrac14, \tfrac18, \tfrac18$.
Problem 4 (converting between tokens, characters, nats and bits). (a) A token-level model of Tiny Shakespeare reports a validation loss of 5.0 nats per token. Is it better or worse than the character-level Transformer's 1.48 nats per character? (b) What per-token loss and perplexity would exactly match the Transformer?
Solution. (a) With this tokenizer it is better: 5.0 nats per token is 2.06 bits per character, below the Transformer's 2.14. (b) The matching loss is 5.18 nats per token, a perplexity of 178 per token.
For (a), a loss in nats per token becomes bits per token on division by $\ln 2$, and bits per character on multiplication by the number of tokens per character. That ratio belongs to the tokenizer and the text, and is 0.2856 for this tokenizer on the validation text: $5.0/0.6931 \times 0.2856 = 2.06$. The Transformer's $1.48/0.6931 = 2.1352$ bits per character is higher, so on the same text the token model's code would be shorter. For (b), the two models spend the same total when the per-token loss is the per-character loss divided by the tokens per character: $1.48/0.2856 = 5.18$ nats per token, which is a perplexity of $e^{5.18} = 178$. A token model must have perplexity below about 178 to beat a character model whose perplexity is 4.4. This is the conversion that A BPE-Tokenized Shakespeare GPT states; that page illustrates it with a ratio of one quarter.
Problem 5 (the perplexity of two test sets together). A model has perplexity 8 on a test set of 300 tokens and perplexity 64 on another of 100 tokens. What is its perplexity on the 400 tokens together?
Solution. It is 13.45, not the weighted average 22.
Perplexities do not average; log-perplexities do. The total code length of the combined set is the sum of the two totals: $300\log_2 8 + 100\log_2 64 = 900 + 600 = 1{,}500$ bits. Dividing by 400 tokens gives 3.75 bits per token, and $2^{3.75} = 13.45$. In general the perplexity of a union is the geometric mean of the parts' perplexities weighted by their token counts, here $8^{0.75} \times 64^{0.25}$. The weighted arithmetic mean, $(300 \times 8 + 100 \times 64)/400 = 22$, is larger, as the inequality between the two means requires. The same reasoning is why the definition of perplexity for a collection of documents in Evaluating Topic Models divides the total log-probability by the total number of words.
What we have learned
A code that can be decoded must fit its codeword lengths inside a budget, $\sum 2^{-\ell} \le 1$, and any lengths inside the budget can be realized by a prefix code. Reading $2^{-\ell}$ as a probability turns the expected length of a code into the entropy of the source plus the divergence from the distribution the code implies, plus a charge for unused budget. So the entropy in bits is the least average number of binary digits per symbol. The Shannon code comes within one bit of it, the Huffman code is the best code for single symbols, and codes on blocks approach the entropy as closely as desired. A model that assigns probabilities to symbols is a code that spends its cross-entropy, and perplexity is that cost turned back into a count of equally likely choices. On the Tiny Shakespeare text the count falls from 65 for a uniform guess to 28.4 for character frequencies, 5.9 for the best table of counts, and 4.4 for the walkthrough's Transformer.
Every result here concerned symbols from a countable alphabet, and chose a code or a model for a distribution that was given. The two remaining articles of the unit leave each of those restrictions. Differential Entropy and the Gaussian establishes what remains of entropy for a variable with a density, where no finite number of bits records a value exactly. Maximum Entropy Distributions turns the modeling problem around: given only a few facts about a distribution, such as its mean, it finds the distribution of greatest entropy, the one that commits to the least beyond those facts. The geometric decay that made the Rice code fit the gaps of oil is one of its answers.
References
- Cover, T. M., and Thomas, J. A. (2006). Elements of Information Theory, 2nd edition. Wiley. Chapter 5, "Data Compression" (Section 5.2, "Kraft Inequality"; Section 5.4, "Bounds on the Optimal Code Length"; Section 5.5, "Kraft Inequality for Uniquely Decodable Codes"; Section 5.8, "Optimality of Huffman Codes"). record · 8 pages
- Huffman, D. A. (1952). A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9), 1098–1101. record
- Jelinek, F., Mercer, R. L., Bahl, L. R., and Baker, J. K. (1977). Perplexity—a measure of the difficulty of speech recognition tasks. The Journal of the Acoustical Society of America, 62(S1), S63. doi:10.1121/1.2016299 record
- Jurafsky, D., and Martin, J. H. (2026). Speech and Language Processing, 3rd edition draft of August 19, 2026. Chapter 3, "N-gram Language Models" (Section 3.3, "Evaluating Language Models: Perplexity"; Section 3.7, "Advanced: Perplexity's Relation to Entropy"; "Historical Notes"). https://web.stanford.edu/~jurafsky/slp3/ record
- Karpathy, A. (2015). char-rnn [Software and data]. https://github.com/karpathy/char-rnn (the file
data/tinyshakespeare/input.txt). record · 3 pages - Kraft, L. G. (1949). A device for quantizing, grouping, and coding amplitude-modulated pulses. Master's thesis, Department of Electrical Engineering, Massachusetts Institute of Technology. record
- Lewis, D. D. (1997). Reuters-21578 text categorization test collection, distribution 1.0. record · 11 pages
- MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. Chapter 5, "Symbol Codes" (Sections 5.2 to 5.5; Exercise 5.16), and Section 6.2, "Arithmetic codes". record · 5 pages
- McMillan, B. (1956). Two inequalities implied by unique decipherability. IRE Transactions on Information Theory, 2(4), 115–116. doi:10.1109/TIT.1956.1056818 record
- Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3), 379–423, and 27(4), 623–656. Section 9, "The fundamental theorem for a noiseless channel". record · 6 pages