Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 224 / 1 / d / Solution

Let $M={\max }_k{p}_k$ and choose an index $m$ with $p_m=M$. Splitting the overlap sum at $m$ givesso $1-q\ge M$. Moreover, information entropy dominates min-entropy gives $H(X)\ge -{\log }_{2}M$, and hence $2^{-H(X)}\le M\le 1-q$.

Apply Pinsker's inequality in natural logarithms. Because the paper writes total variation as the full ${\ell }^1$ distance, part c yieldsCombining the two estimates proves