What is the simplest proof that the mutual information $I(X:Y)$ is always non-negative?

Question

What is the simplest proof that mutual information is always non-negative? i.e., $I(X;Y)\ge0$

Answer 1

By definition, $$I(X;Y) = -\sum_{x \in X} \sum_{y \in Y} p(x,y) \log\left(\frac{p(x)p(y)}{p(x,y)}\right)$$ Now, negative logarithm is convex and $\sum_{x \in X} \sum_{y \in Y} p(x,y) = 1$, therefore, by applying Jensen Inequality we will get, $$I(X;Y) \geq -\log\left( \sum_{x \in X} \sum_{y \in Y} p(x,y) \frac{p(x)p(y)}{p(x,y)} \right) = -\log\left( \sum_{x \in X} \sum_{y \in Y} p(x)p(y)\right) = 0$$ Q.E.D

Answer 2

Another way to show this without using Jensen's inequality, but using the fact that $log(x) \leq x-1$ with equality iff $x = 1$

$I(X,Y) = \mathbb{E} \left(\log \left[\frac{f_{X,Y}(x,y)}{f_X(x) f_Y(y)}\right]\right)=\mathbb{E} \left(-\log \left[\frac{f_X(x) f_Y(y)}{f_{X,Y}(x,y)}\right]\right)$

But $log(x) \leq x-1$ throughout it's domain, and therefore $-\log(x)\geq 1-x$. Then we have: \begin{align*} I(X,Y) &\geq \mathbb{E} \left(1-\left[\frac{f_X(x) f_Y(y)}{f_{X,Y}(x,y)}\right]\right) \\ &= 1- \mathbb{E} \left(\left[\frac{f_X(x) f_Y(y)}{f_{X,Y}(x,y)}\right]\right)\\ &= 1-\int_{x}\int_{y} f_{X,Y}(x,y)\left[\frac{f_X(x) f_Y(y)}{f_{X,Y}(x,y)}\right]dx dy\\ &=1- \left[\int_{x}f_X(x) dx\right] \left[\int_{y} f_Y(y) dy\right] = 1-1\cdot 1 = 0 \end{align*}