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$,
$$
\mathbb P\{l_S(X)\geq l_C(X)+k\}\leq2^{-k+1}.
$$
On this event, $P(X)<2^{-l_C(X)-k+1}$. Summing and applying the <Kraft inequality> proves
$$
\mathbb P\{l_S(X)\geq l_C(X)+k\}
\leq2^{-k+1}\sum_a2^{-l_C(a)}\leq2^{-k+1}.
$$

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/iii/paper-224/4/b/solution