Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 2 / 12G (Coding and Cryptography)

The binary Huffman coding algorithm repeatedly merges the two currently least probable symbols into one meta-symbol whose probability is their sum. After recursively constructing a code for the smaller alphabet, append $0$ and $1$ to the meta-symbol's codeword to obtain codewords for the merged pair. The result is a binary prefix code.

To prove optimality, begin with an optimal prefix-code tree. It may be taken to be full, since an internal vertex with one child can be suppressed and all codewords below it shortened. Two leaves of maximum depth are siblings. By exchanging labels, without changing lengths, assign two least probable symbols to such a sibling pair: moving a smaller probability to a no-shorter codeword cannot increase the expected length. Contracting this pair to one leaf replaces their contribution $p_i{\ell }_i+p_j{\ell }_j$ by $(p_i+p_j)({\ell }_i-1)$ plus the constant $p_i+p_j$. If the contracted code were not optimal for the reduced alphabet, replacing it by a better one and then expanding the merged leaf would improve the original code. Mathematical induction on the number of symbols now proves that the Huffman construction minimizes expected word length.

False. For probabilities $(0.4,0.2,0.2,0.1,0.1)$, first merge the two $0.1$ symbols. Subsequent ties allow Huffman trees with length multisets $(2,2,2,3,3)$ and $(1,3,3,3,3)$, both of expected length $2.2$.

False. For probabilities $(0.30,0.25,0.25,0.20)$, every length-two code is optimal. A code in which the $0.30$ and $0.20$ symbols are sibling leaves is optimal, but no Huffman construction produces that labelled tree, because its first merge must pair $0.20$ with a $0.25$ symbol.

True. The Huffman tree is a full binary tree, so its leaves form a complete prefix code. The Kraft inequality is therefore an equality: