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$ 
 A: 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
A: 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*}
