Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
This is called Gibb's inequality. –  Srivatsan Oct 4 '11 at 20:24
add comment

1 Answer

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|improve this answer
1  
@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
add comment

Your Answer

 
discard

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.