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

For a binary prefix code with length function $L_n:A^n\to \mathbb{N}$, the Kraft inequality is

For the direct half of the code-distribution correspondence, let $L$ be the length function of a binary prefix code and putThen $R$ is a probability mass function andThus every prefix code determines a distribution whose ideal description lengths do not exceed the codeword lengths.

Conversely, given a probability mass function $R$, setfor $R(x)>0$. Then $2^{-L(x)}\le R(x)$, so the Kraft inequality is satisfied. Its converse supplies a binary prefix code with these lengths, andIf real lengths are allowed, the ideal choice $L(x)=-{\log }_{2}R(x)$ satisfies Kraft with equality.

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.