Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 224 / 4

The direct codes-distributions correspondence says that every mass function $Q$ on a finite alphabet admits a binary prefix code with lengths $L(x)=\lceil -{\log }_{2}Q(x)\rceil$. Conversely, every binary prefix code has lengths satisfying the Kraft inequality $K={\sum }_x{2}^{-L(x)}\le 1$, and hence defines the mass function $Q_C(x)=2^{-L(x)}/K$.

For the distribution $Q_C$ from part (a),Thereforeby Gibbs inequality and $K\le 1$.

For any fixed threshold $R$, minimizing the excess-length probability means assigning the available strings shorter than $R$ to the most probable symbols. Repeating this exchange argument simultaneously for every threshold orders symbols by decreasing probability and assigns binary strings from shortest to longest. There are $2^{\ell }$ words of length $\ell$, so the $k$th word in shortlex order has lengthThis is the optimal one-to-one binary code.

For decreasing probabilities, the first $x$ symbols each have probability at least $P(x)$, so $xP(x)\le 1$. Hence

Relabeling an arbitrary alphabet in decreasing probability order makes part (ii) pointwise:It immediately impliesand, after taking expectations,This reverses the prefix-code lower bound from part (b). A general one-to-one code need not decode concatenated codewords instantaneously or uniquely, so it is not constrained by Kraft's inequality.