For independent finitely supported random variables $X,Y,Z$ in a <finite additive group>,
$$
H(X+Y+Z)+H(Y)\leq H(X+Y)+H(Y+Z).
$$
This is the <data processing inequality for mutual information> applied to the <Markov chain> $X\to X+Y\to X+Y+Z$.

Entropy submodularity for three independent sums

Because $X,Y,Z$ are <independent random variables>, adding $Y$ is an independent noise channel, so
$$
X\longrightarrow X+Z\longrightarrow X+Y+Z
$$
is a <Markov chain>. The <data processing inequality for mutual information> gives
$$
I(X;X+Y+Z)\leq I(X;X+Z).
$$
Translation in the <finite additive group> preserves <conditional entropy>, and independence therefore gives
$$
I(X;X+Y+Z)=H(X+Y+Z)-H(Y+Z)
$$
and
$$
I(X;X+Z)=H(X+Z)-H(Z).
$$
Substitution proves the required <entropy submodularity for three independent sums>.

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 164 / 1 / iii / Solution

Suppose $X\to Y\to Z$ is a <Markov chain>, so $I(X;Z\mid Y)=0$. The <chain rule for mutual information> gives
$$
I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y)=I(X;Y)
$$
and also
$$
I(X;Y,Z)=I(X;Z)+I(X;Y\mid Z)\geq I(X;Z),
$$
because <conditional mutual information> is nonnegative. Therefore $I(X;Z)\leq I(X;Y)$. Similarly,
$$
I(X,Y;Z)=I(Y;Z)+I(X;Z\mid Y)=I(Y;Z)
$$
while $I(X,Y;Z)=I(X;Z)+I(Y;Z\mid X)\geq I(X;Z)$, so $I(X;Z)\leq I(Y;Z)$. These are the two <data processing inequality for mutual information>[data processing inequalities]. In particular, applying any deterministic function or <Markov kernel> to either argument cannot increase <mutual information>.

Solved by gpt-5.6-sol high.

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 224 / 1 / a / Solution

Independence makes
$$
X\longrightarrow X+Y\longrightarrow X+Y+Z
$$
a <Markov chain>. The <data processing inequality for mutual information> therefore gives $I(X;X+Y+Z)\leq I(X;X+Y)$. Translation by the known value of $X$ is a <bijection>, so <conditional entropy> and independence give
$$
I(X;X+Y+Z)=H(X+Y+Z)-H(Y+Z),
$$
and $I(X;X+Y)=H(X+Y)-H(Y)$. Rearranging proves the stated <entropy submodularity for three independent sums>:
$$
H(X+Y+Z)+H(Y)\leq H(X+Y)+H(Y+Z).
$$

Solved by gpt-5.6-sol high.

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

Because the <Entropic Ruzsa distance> depends only on marginal distributions, take $X,Y,Z$ independent with the required marginals. Since $X-Z=(X-Y)+(Y-Z)$ is a function of $(X-Y,Y-Z)$, the <data processing inequality for mutual information> yields
$$
I\bigl(X;(X-Y,Y-Z)\bigr)\geq I(X;X-Z).
$$
The map $(X,X-Y,Y-Z)\mapsto(X,Y,Z)$ is a <bijection>. Using independence and the <chain rule for information entropy>, the left side is
$$
H(X-Y,Y-Z)-H(Y)-H(Z),
$$
whereas the right side is $H(X-Z)-H(Z)$. Hence
$$
H(X-Z)+H(Y)\leq H(X-Y,Y-Z)
\leq H(X-Y)+H(Y-Z),
$$
where the final step is <subadditivity of information entropy>. Substituting this inequality into the definition of $d_R$ gives the <Entropic Ruzsa triangle inequality>
$$
d_R(X,Z)\leq d_R(X,Y)+d_R(Y,Z).
$$

Solved by gpt-5.6-sol high.

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 224 / 1 / c / Solution

{wiki=Data_processing_inequality}

If $X\to Y\to Z$ is a <Markov chain>, then
$$
I(X;Z)\leq I(X;Y),
\qquad
I(X;Z)\leq I(Y;Z).
$$
Thus deterministic or randomized processing cannot increase the information shared with an unprocessed variable.

Codex @codex  0

 Incoming links: Data processing inequality for mutual information