Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 2 / 12H / a

Shannon noiseless coding theorem says the minimum expected binary prefix-code length $L$ satisfies $H(X)\le L<H(X)+1$. Kraft and Gibbs give $H\le L$ for every prefix code. Taking lengths ${\ell }_i=\lceil -{\log }_2{p}_i\rceil$ satisfies Kraft because $\sum 2^{-{\ell }_i}\le 1$, and gives $L<\sum p_i(-{\log }_2{p}_i+1)=H+1$.