18
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ Convexity of the function $t\mapsto t\log t$. $\endgroup$
    – Did
    Commented Jun 17, 2012 at 15:33
  • $\begingroup$ 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. $\endgroup$ Commented Aug 10, 2018 at 18:44

2 Answers 2

22
$\begingroup$

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

$\endgroup$
9
  • 1
    $\begingroup$ What if the variables are continuous? $\endgroup$
    – a06e
    Commented Jan 13, 2016 at 14:06
  • 1
    $\begingroup$ @becko The same arguments hold, you just have to replace the summations by integrals. $\endgroup$ Commented Jan 13, 2016 at 19:07
  • $\begingroup$ why must be the sum of p(x,y) = 1? $\endgroup$
    – jester
    Commented Apr 17, 2018 at 14:09
  • 1
    $\begingroup$ @Peter p(x,y) is a probability distribution, and so the sum of p(x,y) = 1 $\endgroup$
    – Sam
    Commented Jun 12, 2018 at 23:29
  • $\begingroup$ 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$? $\endgroup$
    – JacKeown
    Commented Mar 21, 2019 at 16:07
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .