Encyclopedia

Data processing inequality

Concept in information processing

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated August 22, 2024

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'.

01Statement

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.

02Proof

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)\geq 0$ .

Watch videos about Data processing inequalityExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Data processing inequality”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Data processing inequality

01Statement

02Proof

Sources and credits

Related topics

Garbage in, garbage out