= 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).
$$
Back to article page
