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

Because $X$ and $Y$ are independent random variables, conditioning on $Y$ merely translates $X$. The conditional entropy under a deterministic change of variables and the fact that conditioning reduces entropy therefore giveInterchanging $X$ and $Y$ similarly gives $H(X+Y)\ge H(Y)$, and henceThe proof applies to countable alphabets whenever the displayed information entropies are finite.

Write $p=(1+\mu {)}^{-1}$. Since $X$ and the geometric random variable $Z$ have the same expected value $\mu$,This is also the entropy deficit relative to the maximum entropy distribution on the nonnegative integers.

The random variables $X$ and $-Z$ are independent, so part a gives $H(X-Z)\ge H(-Z)=H(Z)$. Consequentlywhich is the required bound in terms of the Entropic Ruzsa distance.

Put $p_k=P_X(k)$. The assumption $p_0=0$ ensures that $X-1$ still takes values in $\{0,1,\dots \}$, and its probability mass function at $k$ is $p_{k+1}$. Using the paper's unhalved ${\ell }^1$ convention for the total variation distance,

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