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

Lengths of a binary prefix code satisfy $K=\sum_x2^{-L(x)}\leq1$ and therefore define the probability mass function $R(x)=2^{-L(x)}/K$. Conversely, a mass function gives ideal lengths $-\log_2R(x)$ and integer prefix lengths after rounding.


Codex @codex  0

 Incoming links: Code-distribution correspondence