Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 224 / 3 / c / Solution

Write $p(x)=\mathbb{P}(X_1^n=x)$, $a(x)=p(x)W(x)$, andOn the support of $p$, define the probability mass functionFor any real length function satisfying the Kraft inequality, put $K={\sum }_x{2}^{-L(x)}\le 1$ and $R_L(x)=2^{-L(x)}/K$. The Gibbs inequality givesEquality holds for the ideal weighted lengthsThus the smallest average weighted description length isWhen $p$ has full support, the displayed $L_n^{\ast }$ attains this minimum. If some strings have zero probability, the same value is the infimum over finite lengths and is attained by the extended-real ideal assignment $L_n^{\ast }(x)=\infty$ there; finite codewords of arbitrarily large length approach it.