Data-Processing Inequality

Suppose that $X$ be a random variable.

We obtain a new random variable $Y$ by applying a stochastic mapping $f$ on $X$ , namely, $Y = f(X)$ .
We further post-process $Y$ by another stochastic mapping $g$ to obtain $Z$ , i.e., $Z = g(Y)$ .

The function $g$ depends only on $Y$ and is independent of $X$ . Therefore, the $X$ and $Y$ are conditionally independent given $Y$ . The random variables $X$ , $Y$ , $Z$ are said to form a Markov chain, denoted by

X \rightarrow Y \rightarrow Z.

The data processing inequality states that postprocessing can not increases the correlations.

Theorem (Data Processing Inequality). If the random variables $X, Y$ and $Z$ form a Markov chain: $X \rightarrow Y \rightarrow Z$ . Then
$I( X; Y) \ge I(X ; Z),\,\\ I( X; Y) \ge I(X; Y \mid Z).$

Proof. By chain rule of mutual information, we expand the mutual information in two different ways:

\begin{aligned} I(X; Y, Z) &= I(X ; Z) + I( X; Y \mid Z) \\ &= I(X ; Y) + I( X; Z \mid Y). \end{aligned}

Since $X$ and $Z$ are conditionally independent through $Y$ , it holds that

I(X; Z \mid Y) = 0.

Therefore,

I(X; Y) = I(X; Z) + I(X; Y \mid Z).

The inequalities follow form non-negativity of mutual information.

$\blacksquare$

Remark.

\begin{aligned} \small I(X; Y, Z) &= \sum p(x, y, z) \log \frac{ p (x, y, z) }{ p(x) p(y, z) } \\ &= \sum p(x, y, z) \log \frac{ p(y, z \mid x) }{ p(y, z) } \\ &= \sum p(x, y, z) \Big( \log \frac{ 1 }{ p(z) p(y \mid z) } - \log \frac{1}{ p(z \mid x) p(y \mid z, x) }\Big) \\ &= I(X; Z) + I(X; Y \mid Z). \end{aligned}

Remark. If $X$ and $Z$ are conditionally independent through $Y$ , then

I(X, Z \mid Y) = \sum p(x, y, z) \log \frac{ p(x, z \mid y) }{ p(x \mid y) p ( z \mid y ) } = 0,

since $p(x, z \mid y) = p(x \mid y ) p(z \mid y)$ .

Reference

[1] T. M. Cover and J. A. Thomas, “ELEMENTS OF INFORMATION THEORY,” p. 774.