Data processing inequality

The Data processing inequality is an information theoretic concept which 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'.[1]

Definition

Let three random variables form the Markov chain ${\displaystyle X\rightarrow Y\rightarrow Z}$, implying that the conditional distribution of ${\displaystyle Z}$ depends only on ${\displaystyle Y}$ and is conditionally independent of ${\displaystyle X}$. Specifically, we have such a Markov chain if the joint probability mass function can be written as

${\displaystyle p(x,y,z)=p(x)p(y|x)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 :

${\displaystyle I(X;Y)\geqslant I(X;Z)}$

With the equality ${\displaystyle I(X;Y)=I(X;Z)}$ if and only if ${\displaystyle I(X;Y|Z)=0}$, i.e. ${\displaystyle Z}$ and ${\displaystyle Y}$ contain the same information about ${\displaystyle X}$, and ${\displaystyle X\rightarrow Z\rightarrow Y}$ also forms a Markov chain.[2]

See also

• Garbage in, garbage out

References

1. Beaudry, Normand (2012), "An intuitive proof of the data processing inequality", Quantum Information & Computation, 12 (5–6): 432–441, arXiv:1107.0740, Bibcode:2011arXiv1107.0740B
2. Cover; Thomas (2012). Elements of information theory. John Wiley & Sons.

External links

• http://www.scholarpedia.org/article/Mutual_information