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

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.