Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 224 / 4

The binary Kraft inequality says that codeword lengths $l_1,l_2,\dots$ of a prefix code satisfyConversely, suppose positive integer lengths obey this inequality and arrange them in nondecreasing order. Construct codewords greedily in the infinite binary tree. Before assigning length $l_i$, each earlier codeword of length $l_j\le l_i$ excludes exactly $2^{l_i-l_j}$ nodes at depth $l_i$. Thus the number excluded iswhere strictness follows because the remaining term $2^{-l_i}$ occurs in the full Kraft sum. A free depth-$l_i$ node therefore exists. Assign it as the next codeword; choosing a node not below an earlier codeword preserves prefix-freeness. Induction constructs the required prefix code.

Write $p_k=\mathbb{P}(X=k)$. Monotonicity givesso $p_k\le 1/k$ and therefore ${\log }_{2}k\le {\log }_2(1/p_k)$ whenever $p_k>0$. Hence

A distribution on $\{1,2,\dots \}$ must have $\mu \ge 1$. For $\mu >1$, put $p=1/\mu$ and letFor any mass function $P$ with mean $\mu$, Gibbs inequality givesThus the geometric distribution uniquely maximizes entropy. For $\mu =1$, the only admissible law is the point mass at one, which is the limiting geometric case $p=1$.

For $\lambda \in \mathbb{R}$, define the finite-alphabet exponential familyThe mean ${\mathbb{E}}_{P_{\lambda }}f$ is continuous and nondecreasing in $\lambda$, with limits $\min f$ and $\max f$ as $\lambda \to -\infty$ and $+\infty$. The strict interior assumption on $v$ therefore supplies a $\lambda$ with ${\mathbb{E}}_{P_{\lambda }}f=v$.

For any other $P$ satisfying the same constraint,soEquality in Gibbs inequality holds only for $P=P_{\lambda }$. Hence this Gibbs-form mass function is the unique entropy maximizer.