7

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.

anon
  • 115

1 Answers1

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.

Did
  • 279,727
  • 2
    @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 04 '11 at 20:35
  • 1
    @Srivatsan, thanks, this might be considered as a (slightly...) simpler approach. – Did Oct 04 '11 at 20:43