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

If $X\to Y\to Z$ is a Markov chain, the two forms of the data processing inequality for mutual information areThe chain rule for mutual information and the Markov property $I(X;Z\mid Y)=0$ giveUsing the other order,because conditional mutual information is nonnegative. This proves the first inequality. Applying the same result to the reversed Markov chain $Z\to Y\to X$, which has the same conditional-independence statement, proves the second.

Let $V,V^{\prime },U$ be mutually independent, with $V,V^{\prime }$ identically distributed. Entropy submodularity for three independent sums givesIndependent addition cannot decrease discrete entropy, because $H(V+V^{\prime }+U)\ge H(V+V^{\prime }+U\mid U)=H(V+V^{\prime })$. Hence

Take $U$ to have the distribution of $-X$ and take $V,V^{\prime }$ to be independent copies of $X$, all mutually independent. Then $U+V$ and $U+V^{\prime }$ both have the distribution of $X-Y$, whereas $V+V^{\prime }$ has the distribution of $X+Y$ and $H(U)=H(X)$. HenceorThe denominator is nonnegative because conditioning on $Y$ recovers $X$ from $X-Y$, so $H(X-Y)\ge H(X-Y\mid Y)=H(X)$.

Stationarity gives $H(X_n)=H(X_{n+1})=H(X_1)$. The Markov relation $X_1\to X_n\to X_{n+1}$ and the data processing inequality for mutual information implyUsing $H(X_n\mid X_1)=H(X_n)-I(X_1;X_n)$ on both sides gives

The Markov property gives $I(X_1;X_4\mid X_3)=I(X_2;X_4\mid X_3)=0$. The chain rule therefore yieldsandConditional on $X_4$, the factorization of the chain still gives $X_1\to X_2\to X_3$. The conditional data-processing inequality thus givesRearranging proves