Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
This is called Gibb's inequality. – Srivatsan Oct 4 '11 at 20:24

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.

share|cite|improve this answer
@anon There's another, but similar, way. Show that $x \mapsto \ln x$ is concave, so that $\mathbf E[\ln Y] \leq \ln (\mathbf E[Y])$. Now, let $Y$ be a random variable that takes the value $(q_i/p_i)$ with probability $p_i$. Apply Jensen to $Y$. – Srivatsan Oct 4 '11 at 20:35
@Srivatsan, thanks, this might be considered as a (slightly...) simpler approach. – Did Oct 4 '11 at 20:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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