14
$\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 Jun 17 '12 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$ – Francisco Javier Delgado Ceped Aug 10 '18 at 18:44
20
$\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$
8
  • 1
    $\begingroup$ What if the variables are continuous? $\endgroup$ – becko Jan 13 '16 at 14:06
  • 1
    $\begingroup$ @becko The same arguments hold, you just have to replace the summations by integrals. $\endgroup$ – TenaliRaman Jan 13 '16 at 19:07
  • $\begingroup$ why must be the sum of p(x,y) = 1? $\endgroup$ – jester Apr 17 '18 at 14:09
  • 1
    $\begingroup$ @Peter p(x,y) is a probability distribution, and so the sum of p(x,y) = 1 $\endgroup$ – Sam Jun 12 '18 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 Mar 21 '19 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.