The data processing inequality is an information theoretic concept that states that the information content of a signal cannot be increased via a local physical operation. This can be expressed concisely as 'post-processing cannot increase information'.
Let three random variables form the Markov chain X → Y → Z {\displaystyle X\rightarrow Y\rightarrow Z} , implying that the conditional distribution of Z {\displaystyle Z} depends only on Y {\displaystyle Y} and is conditionally independent of X {\displaystyle X} . Specifically, we have such a Markov chain if the joint probability mass function can be written as
In this setting, no processing of Y {\displaystyle Y} , deterministic or random, can increase the information that Y {\displaystyle Y} contains about X {\displaystyle X} . Using the mutual information, this can be written as :
with the equality I ( X ; Y ) = I ( X ; Z ) {\displaystyle I(X;Y)=I(X;Z)} if and only if I ( X ; Y ∣ Z ) = 0 {\displaystyle I(X;Y\mid Z)=0} . That is, Z {\displaystyle Z} and Y {\displaystyle Y} contain the same information about X {\displaystyle X} , and X → Z → Y {\displaystyle X\rightarrow Z\rightarrow Y} also forms a Markov chain.
One can apply the chain rule for mutual information to obtain two different decompositions of I ( X ; Y , Z ) {\displaystyle I(X;Y,Z)} :
By the relationship X → Y → Z {\displaystyle X\rightarrow Y\rightarrow Z} , we know that X {\displaystyle X} and Z {\displaystyle Z} are conditionally independent, given Y {\displaystyle Y} , which means the conditional mutual information, I ( X ; Z ∣ Y ) = 0 {\displaystyle I(X;Z\mid Y)=0} . The data processing inequality then follows from the non-negativity of I ( X ; Y ∣ Z ) ≥ 0 {\displaystyle I(X;Y\mid Z)\geq 0} .
Garbage in, garbage out
