Write $p=(1+\mu)^{-1}$. Since $X$ and the <geometric distribution>[geometric random variable] $Z$ have the same <expected value> $\mu$,
$$
\begin{aligned}
D(P_X\Vert P_Z)
&=\sum_{k\geq0}P_X(k)\log_2\frac{P_X(k)}{p(1-p)^k}\\
&=-H(X)-\log_2p-\mu\log_2(1-p)\\
&=H(Z)-H(X).
\end{aligned}
$$
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)\geq H(-Z)=H(Z)$. Consequently
$$
\begin{aligned}
2d_R(X,Z)-D(P_X\Vert P_Z)
&=2H(X-Z)-H(X)-H(Z)-\{H(Z)-H(X)\}\\
&=2\{H(X-Z)-H(Z)\}\geq0,
\end{aligned}
$$
which is the required bound in terms of the <Entropic Ruzsa distance>.

Solution

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

 Solution

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