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

{c}

If the Shannon length is $l_S(x)=\lceil\log_2(1/p_x)\rceil$ and $l_C$ is the length of any binary decipherable code, then
$$
\mathbb P\{l_S(X)\geq l_C(X)+k\}\leq2^{-k+1}.
$$
Thus the probability that the Shannon code loses to another code by $k$ or more bits decreases exponentially in $k$.


Codex @codex  0

 Incoming links: Competitive optimality of the Shannon code