Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 31 / 1

Take $m\ge 2$, as required for the lower bound in this part. A binary Huffman code has a full binary tree: every merge has two children, and all codewords are leaves. More generally an optimal prefix code for positive-probability symbols cannot have an internal vertex with only one child, since suppressing that vertex shortens its descendant codewords and reduces the expected length.

Choose a leaf of maximum depth $s$. Its sibling must also be a leaf, since an internal sibling would have a descendant deeper than $s$. These two leaves give the deepest sibling property of an optimal prefix code, and there are only $m$ leaves altogether. ThereforeFor the degenerate singleton alphabet, an empty codeword suffices and $n_s=1$; the stated lower bound consequently excludes $m=1$.

If all leaves of a full binary tree have depth $s$, all binary paths of length $s$ end in leaves. Thus it has exactly $2^s$ leaves and $m=2^s$. Equivalently, equality in the Kraft inequality gives $m{2}^{-s}=1$.

Conversely, when $m=2^k$ a complete depth-$k$ tree is a prefix code with mean length $k$. For any prefix lengths $s_i$, convexity givesso $L\ge {\log }_{2}m=k$. The complete tree is optimal. A Huffman code attains this optimum, and equality in the strictly convex first inequality forces all its lengths to equal $k$. Hence, for $m\ge 2$,This also proves that ties in the Huffman construction do not change the conclusion.

Use the balancing fact proved by the exchange argument in part d: every leaf of an optimal tree has depth $s-1$ or $s$. A full binary tree with this property has all $2^{s-1}$ possible vertices at level $s-1$; at least one of these is split into two deepest leaves. ThusThese inequalities characterize the maximum codeword length exactly:In the suggested notation $m=a{2}^k$, $1\le a<2$, this is $s=k$ for $a=1$ and $s=k+1$ for $1<a<2$. The distinction at a power of two is important.

Suppose a leaf has depth $t\le s-2$. By part a there is a sibling pair of leaves at depth $s$. These leaves are disjoint from the shallow leaf and its descendants, since a leaf has no descendants. Modify the prefix tree of a code by splitting the shallow leaf into two leaves at depth $t+1$ and replacing the deepest sibling pair by their parent as one leaf at depth $s-1$. The number of leaves remains $m$, so assign the equiprobable source letters bijectively to the new leaves.

The sum of depths for the three affected leaves changes from $t+2s$ to $2(t+1)+(s-1)$. The change isAll other depths are unchanged. Since probabilities are equal, this strictly decreases the expected codeword length, contradicting the optimality of the Huffman code. This is the balancing exchange for a uniform optimal prefix code. There is therefore no leaf of depth at most $s-2$, provingThe argument applies to every optimal binary prefix tree for the uniform source, independently of how Huffman ties are resolved.

A full binary tree has Kraft sum one. For example, place mass one at the root and divide each internal vertex's mass equally between its children; a leaf at depth $l$ receives $2^{-l}$, and the total mass on leaves remains one. Using part d gives the two equationsMultiplying the second equation by $2^s$ and subtracting the first gives the uniform-source Huffman length distributionIf $m=2^s$, the first number is zero and every codeword has length $s$. Otherwise both levels occur. The corresponding mean length is $L=s-(2^s-m)/m$.

For the uniform 27-symbol model, $s=\lceil {\log }_{2}27\rceil =5$. The uniform-source Huffman length distribution givesThus five symbols receive four-bit codewords and the other 22 receive five-bit codewords. To realize these lengths, start with all 32 binary words of length five and collapse any five disjoint sibling pairs into their four-bit parents. This leaves exactly five leaves at depth four and 22 at depth five. All source letters have the same probability, so which five letters receive the shorter codewords is arbitrary.

The expected codeword length isThe 27 symbols may represent 26 letters and a space, but this idealization keeps them equiprobable; it is not an empirical frequency model of English.