Data processing inequality

Let three random variables form the Markov chain X \rightarrow Y \rightarrow Z, implying that the conditional distribution of Z depends only on Y and is conditionally independent of X. Specifically, we have such a Markov chain if the joint probability mass function can be written as :p(x,y,z) = p(x)p(y|x)p(z|y)=p(y)p(x|y)p(z|y) In this setting, no processing of Y, deterministic or random, can increase the information that Y contains about X. Using the mutual information, this can be written as : : I(X;Y) \geqslant I(X;Z), with the equality I(X;Y) = I(X;Z) if and only if I(X;Y\mid Z)=0 . That is, Z and Y contain the same information about X, and X \rightarrow Z \rightarrow Y also forms a Markov chain. ==Proof==

One can apply the chain rule for mutual information to obtain two different decompositions of I(X;Y,Z): : I(X;Z) + I(X;Y\mid Z) = I(X;Y,Z) = I(X;Y) + I(X;Z\mid Y) By the relationship X \rightarrow Y \rightarrow Z, we know that X and Z are conditionally independent, given Y, which means the conditional mutual information, I(X;Z\mid Y)=0. The data processing inequality then follows from the non-negativity of I(X;Y\mid Z)\ge0. ==See also==