= Data processing inequality
{title2=$I(X;Z)\leq\min\{I(X;Y),I(Y;Z)\}$}
{wiki}
= Data processing inequality for mutual information
{synonym}
For finite <discrete random variables>, suppose $X\to Y\to Z$ is a <Markov chain>: the final <channel> uses only $Y$, so $X$ and $Z$ have <conditional independence> given $Y$. In terms of the joint <probability mass function>,
$$
p(x,y,z)=p_X(x)p(y\mid x)p(z\mid y),
$$
and hence $I(X;Z\mid Y)=0$. Then the two data processing inequalities are
$$
I(X;Z)\leq I(X;Y),
\qquad
I(X;Z)\leq I(Y;Z).
$$
All <mutual informations> here use base-two <logarithms>. Thus deterministic or randomized processing cannot increase the information shared with an unprocessed variable.https://web.stanford.edu/class/cs229t/scribe_notes/12_05_final.pdf[Stanford CS229T/STATS231, Theorem 2.1 and its chain-rule proof]{ref}
For a concrete cascade, take a fair <bit> $X$ and <Bernoulli random variables> $N_q,N_r$ with <probabilities> $q=0.1$, $r=0.2$ of being one. Assume $X,N_q,N_r$ are jointly <independent random variables>, and pass through two <binary symmetric channels>:
$$
Y=X\oplus N_q,\qquad Z=Y\oplus N_r.
$$
The second noise is independent of both $X$ and $Y$, so this is a <Markov chain>. Both $Y$ and $Z$ are fair <bits>. The net <exclusive or> error is one exactly when one noise flips the <bit> and the other does not:
$$
s=\mathbb P(N_q\oplus N_r=1)
=q(1-r)+(1-q)r=q+r-2qr=0.26.
$$
Using the <binary entropy> $h_2(t)=-t\log_2t-(1-t)\log_2(1-t)$, the three <mutual informations> are fully determined:
$$
\begin{aligned}
I(X;Y)&=1-h_2(0.1)\approx1-0.4689955936\approx0.5310044064,\\
I(Y;Z)&=1-h_2(0.2)\approx1-0.7219280949\approx0.2780719051,\\
I(X;Z)&=1-h_2(0.26)\approx1-0.8267463725\approx0.1732536275.
\end{aligned}
$$
All numbers are in <bits>. The two losses are $I(X;Y\mid Z)\approx0.3577507789$ and $I(Y;Z\mid X)\approx0.1048182776$. Thus the cascade retains less information about the original source than either individual <channel> shares between its own input and output.
\Image[/data-processing-binary-cascade.png]
{title=Two noisy binary channels compose to a noisier channel and obey both data processing bounds}
With $q=0.1$ fixed and $0\leq r\leq1/2$, the effective error is $s=0.1+0.8r$. At $r=0$, $Z=Y$ and $I(X;Z)=I(X;Y)$; at $r=1/2$, $Z$ is independent of the previous variables and $I(X;Z)=I(Y;Z)=0$. The diagram plots these endpoints and the computed $r=0.2$ example.
The <data processing inequality> is useful for testing what a proposed decoder or data summary could possibly reveal: if its only input is $Y$, even randomized processing cannot provide more <mutual information> about $X$ than $Y$ already contains. The <Markov chain> hypothesis matters. In the <exclusive or> example from <conditional mutual information>, allowing a processor to use both $Y$ and $Z$ reveals $X$ exactly; that processor has additional input, so the conclusion for processing $Y$ alone does not apply.
The <chain rule for mutual information> proves both inequalities and identifies their exact gaps. First expand the information about $X$ in the two observation orders:
$$
\begin{aligned}
I(X;Y,Z)&=I(X;Y)+\underbrace{I(X;Z\mid Y)}_{0}\\
&=I(X;Z)+I(X;Y\mid Z).
\end{aligned}
$$
Therefore $I(X;Y)-I(X;Z)=I(X;Y\mid Z)\geq0$. Next use $Z$ as the variable being learned:
$$
\begin{aligned}
I(Z;X,Y)&=I(Z;Y)+\underbrace{I(Z;X\mid Y)}_{0}\\
&=I(Z;X)+I(Z;Y\mid X).
\end{aligned}
$$
Symmetry of <mutual information> gives $I(Y;Z)-I(X;Z)=I(Y;Z\mid X)\geq0$. Both signs follow from the nonnegativity of <conditional mutual information>; the first gap also gives <equality in data processing inequality>.
Back to article page
