Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 224 / 4 / b / Solution

The Shannon lengths are $l_S(a)=\lceil {\log }_2(1/P(a))\rceil$. Their Competitive optimality of the Shannon code says that for every binary uniquely decodable code of lengths $l_C$ and every positive integer $k$,On this event, $P(X)<2^{-l_C(X)-k+1}$. Summing and applying the Kraft inequality proves