The <code-distribution correspondence> starts from the <Kraft inequality>. For codeword lengths $L(x)$ put
$$
K=\sum_x2^{-L(x)}\leq1,
\qquad
R(x)=\frac{2^{-L(x)}}K.
$$
Conversely, a probability mass function determines ideal lengths $-\log_2R(x)$, up to integer rounding. For the source law $P_n$,
$$
\begin{aligned}
\mathbb E L(X_1^n)
&=-\sum_xP_n(x)\log_2\{K R(x)\}\\
&=H(P_n)+D(P_n\|R)-\log_2K\\
&\geq H(X_1^n),
\end{aligned}
$$
using nonnegativity of <Kullback-Leibler divergence> and $K\leq1$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 224 / 2 / b / Solution

 Solution

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