Back to the on-screen lesson ·
The exchange argument, the gap to entropy, and when the gap is zero.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to run Huffman's algorithm by hand and in code, read codeword lengths and codewords from the resulting tree, compute the average length as the sum of the merged weights, and compare it with the entropy. You will prove that Huffman codes are optimal among all uniquely decodable symbol codes through the exchange argument and induction, explain why the gap to the entropy is always below one bit and vanishes exactly for dyadic sources, and say what techniques recover the remaining fraction of a bit.
Huffman's code has the smallest expected length of any prefix code, hence of any uniquely decodable code. The proof is an exchange argument plus induction. First, in an optimal code a more probable symbol never has a longer codeword (swap them and $L$ drops). Second, the deepest level contains at least two codewords, since a lone deepest leaf could be shortened. So some optimal code has the two least probable symbols as siblings at maximum depth, differing in the last bit. Merging them into one symbol of combined probability turns an optimal code for the original source into an optimal code for the reduced source with $L$ smaller by exactly their combined probability, and conversely; induction on the number of symbols finishes the argument. The gap $L_{\text{Huffman}} - H$ lies in $[0, 1)$ and is $0$ exactly for dyadic sources. Huffman is optimal among symbol codes; blocks, arithmetic coding and adaptive schemes are how the remaining fraction of a bit is recovered in practice.
Another way: picture
A code tree with a lone leaf at the bottom: its parent has only one child, so the leaf can move up one level and every other codeword stays valid. An optimal tree never has this, so the deepest leaves come in sibling pairs.
Another way: steps
| Claim about some optimal code | Why | Consequence |
|---|---|---|
| $p_i > p_j \Rightarrow \ell_i \le \ell_j$ | swapping the two codewords changes $L$ by $(p_i - p_j)(\ell_j - \ell_i) < 0$ | rare symbols sit deepest |
| the deepest level holds $\ge 2$ codewords | a lone deepest leaf could move up one level | no wasted branch |
| the two rarest are siblings | reorder the deepest level; lengths are unchanged | exactly what the algorithm assumes |
With the three claims in hand, induction finishes the proof. Merge the two rarest symbols into one of combined probability $p_{m-1} + p_m$. Any code for the reduced source extends to one for the original by appending a bit to the merged codeword, and the expected length grows by exactly $p_{m-1} + p_m$ — the same constant for every code. So a code is optimal for the original source exactly when its reduction is optimal for the smaller one, and Huffman, which does precisely this merge, is optimal by induction on the number of symbols. Since Kraft (McMillan) covers uniquely decodable codes too, no such code beats Huffman.
Optimal is not the same as perfect. Huffman is the best symbol code, but it still spends whole bits, so $L \ge H$ with a gap that only vanishes for dyadic probabilities. The gap is at most $1$ bit and usually far less; the table above shows $0$ to $0.078$ bits. To do better you must stop coding one symbol at a time: block the symbols, or use arithmetic coding (lesson 11).
Common mistakes
Suppose an optimal code gives symbol $a$ ($p_a = 0.4$) length $3$ and symbol $b$ ($p_b = 0.1$) length $1$.
Longer word on the likelier symbol.
Swapping the codewords changes $L$ by $(0.4 - 0.1)(1 - 3) = -0.6$: shorter, contradiction. So optimal codes are monotone in probability.
$(0.4, 0.2, 0.2, 0.2)$: Huffman merges $0.4, 0.6, 1$, so $L = 2$ (a fixed-length code is optimal here).
$H = 1.922$: the gap $0.078$ bits per symbol is unavoidable for any symbol code, but blocks of two symbols already cut it.
Suppose a code gives $a$ ($p = 0.4$) length $3$ and $b$ ($p = 0.1$) length $1$.
Swap the two codewords: $L$ changes by $(0.4 - 0.1)(1 - 3) = -0.6$ bits.
The swap keeps the code prefix-free: only the labels move.
The code got shorter, so the original was not optimal: in an optimal code a more probable symbol never has a longer codeword.
Merges $0.4, 0.6, 1$: $L = 2$ bits — a fixed-length code is optimal here.
$H = 0.4 \cdot 1.322 + 3 \cdot 0.2 \cdot 2.322 = 1.922$ bits.
Gap $= 2 - 1.922 = 0.078$ bits per symbol, unavoidable for a symbol code but recoverable by blocking.
All probabilities are powers of two: dyadic.
Lengths $1, 2, 2$; $L = 1.5 = H$: yes, no gap.
For the probabilities $(0.5, 0.25, 0.125, 0.125)$ the Huffman code averages $1.75$ bits and the entropy is $1.75$ bits. By how many bits per symbol does the best symbol code exceed the entropy, to three decimal places?
Answer:
Which property of some optimal prefix code is the key to proving Huffman's algorithm optimal?
For the probabilities $(0.5, 0.25, 0.125, 0.125)$ the Huffman code averages $1.75$ bits and the entropy is $1.75$ bits. By how many bits per symbol does the best symbol code exceed the entropy, to three decimal places?
Answer:
When does a Huffman code achieve average length exactly equal to the entropy?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Which property of some optimal prefix code is the key to proving Huffman's algorithm optimal?
You can build the best symbol code for any source and say how far it is from the entropy. Next: typical sequences, which explain why long blocks reach the entropy.
9. Your turn: is a Huffman code for $(0.5, 0.25, 0.25)$ exactly at the entropy?, step 2