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

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.