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

For feasible mass functions $Q_1,Q_2$ at distortion levels $d_1,d_2$, the mixture $Q=\lambda Q_1+(1-\lambda )Q_2$ has nonzero-symbol mass at most $\lambda d_1+(1-\lambda )d_2$. Concavity of information entropy givesTaking maximizing sequences proves

Regard the alphabet as the cyclic group $\mathbb{Z}/m\mathbb{Z}$ and put $E=X-Y$. For each $y$, subtraction by $y$ is a bijection, soBy concavity of $\varphi$, its monotonicity in the distortion allowance, and $\mathbb{E}{d}_Y=\mathbb{P}(X\ne Y)\le d$,Therefore

The previous part gives $R(d)\ge \log m-\varphi (d)$ for uniform $X$. To attain the bound, take $Y$ uniform on $\mathbb{Z}/m\mathbb{Z}$, choose an independent error $E$ whose mass function attains $\varphi (d)$, and set $X=Y+E$. Then $X$ is uniform, $\mathbb{P}(X\ne Y)=\mathbb{P}(E\ne 0)\le d$, andThus $I(X;Y)=\log m-\varphi (d)$ and equality holds. This is the rate-distortion function of a uniform source under Hamming distortion.