 Data processing inequality

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,and hence $I(X;Z\mid Y)=0$. Then the two data processing inequalities areAll mutual informations here use base-two logarithms. Thus deterministic or randomized processing cannot increase the information shared with an unprocessed variable.^[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: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:Using the binary entropy $h_2(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$, the three mutual informations are fully determined:All numbers are in bits. The two losses are $I(X;Y\mid Z)\approx 0.3577507789$ and $I(Y;Z\mid X)\approx 0.1048182776$. Thus the cascade retains less information about the original source than either individual channel shares between its own input and output.

With $q=0.1$ fixed and $0\le r\le 1/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:Therefore $I(X;Y)-I(X;Z)=I(X;Y\mid Z)\ge 0$. Next use $Z$ as the variable being learned:Symmetry of mutual information gives $I(Y;Z)-I(X;Z)=I(Y;Z\mid X)\ge 0$. Both signs follow from the nonnegativity of conditional mutual information; the first gap also gives equality in data processing inequality.