Let $p=(p_1,\dotsc,p_r), q=(q_1,\dotsc,q_r)$ be two different probability distributions. Define the relative entropy $h(p||q) = \sum_{i=1}^r p_i (\ln p_i - \ln q_i)$ Show $h(p||q)\geq 0$. I'm given the hint that I should show $-x\ln x$ is concave and then show for any concave function f(y)-f(x)\leq (y-x)f'(x) holds. I rewritten the relative entropy as $h(p||q)=\sum_{i=1}^r p_i \ln \left(\frac{p_i}{q_i}\right)= -\sum_{i=1}^r p_i \ln \left(\frac{q_i}{p_i}\right)$ which sort of looks like $-x\ln x$, and I did show that $-x\ln x$ is concave, but I don't really understand what I'm supposed to do, or even if this hint is helpful.
Relative entropy is non-negative
6
$\begingroup$
probability
-
1This is called [Gibb's inequality](http://en.wikipedia.org/wiki/Gibbs%27_inequality). – 2011-10-04
1 Answers
5
Assume that the random variable $X$ is such that $X=\dfrac{p_i}{q_i}$ with probability $q_i$, for every $i$. Then, $ h(p\mid\mid q)=\sum\limits_iq_i\frac{p_i}{q_i}\ln\left(\frac{p_i}{q_i}\right)=\mathrm E(X\ln X). $ Since the function $x\mapsto x\ln x$ is convex, $\mathrm E(X\ln X)\geqslant \mathrm E(X)\ln\mathrm E(X)$ by Jensen inequality.
To complete the proof one must simply compute $\mathrm E(X)$, and I will let you do that.
-
1@Srivatsan, thanks, this might be considered as a (slightly...) simpler approach. – 2011-10-04