Let $M=\max_kp_k$ and choose an index $m$ with $p_m=M$. Splitting the overlap sum at $m$ gives
$$
q\leq\sum_{k<m}p_k+\sum_{k\geq m}p_{k+1}=1-p_m=1-M,
$$
so $1-q\geq M$. Moreover, <information entropy dominates min-entropy> gives $H(X)\geq-\log_2M$, and hence $2^{-H(X)}\leq M\leq1-q$.

Apply <Pinsker's inequality> in natural logarithms. Because the paper writes total variation as the full $\ell^1$ distance, part c yields
$$
(\log_e2)D(P_X\Vert P_{X-1})
=D_e(P_X\Vert P_{X-1})
\geq\frac12\lVert P_X-P_{X-1}\rVert_1^2
=2(1-q)^2.
$$
Combining the two estimates proves
$$
(\log_e2)D(P_X\Vert P_{X-1})
\geq2(1-q)^2
\geq2M^2
\geq2^{-2H(X)+1}.
$$

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-224/1/d/solution