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

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

• Convexity of the function $t\mapsto t\log t$.
– Did
Commented Jun 17, 2012 at 15:33
• In addition, the convexity properties require the coefficients in the linear combination sum 1. Then, as p(x,y) is a probability distribution, it fullfits such condition. Commented Aug 10, 2018 at 18:44

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

• What if the variables are continuous?
– a06e
Commented Jan 13, 2016 at 14:06
• @becko The same arguments hold, you just have to replace the summations by integrals. Commented Jan 13, 2016 at 19:07
• why must be the sum of p(x,y) = 1? Commented Apr 17, 2018 at 14:09
• @Peter p(x,y) is a probability distribution, and so the sum of p(x,y) = 1
– Sam
Commented Jun 12, 2018 at 23:29
• But how does $\sum_{x \in X} \sum_{y \in Y} p(x,y) = 1$ imply that $\sum_{x \in X} \sum_{y \in Y} p(x)p(y) = 1$? Commented Mar 21, 2019 at 16:07

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*}