An inequality on Difference of Entropies - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T18:02:09Z http://mathoverflow.net/feeds/question/76093 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76093/an-inequality-on-difference-of-entropies An inequality on Difference of Entropies Kostas 2011-09-21T23:12:55Z 2011-09-26T15:58:56Z <p>Hi,</p> <p>I have the following problem that came up. It is not a homework problem or something similar. I did my simulations and it seems to hold but i was unable to prove it.## Heading ##</p> <p>Let $P$ and $Q$ be two discrete probability distributions on the alphabet ${1,2,\dots n}$. Prove that:</p> <p>$H(P)-H(Q) \leq \sum\limits_{i=1}^n \big [ (P_i-Q_i)\log(\frac{1}{\frac{P_i}{e}+(1-\frac{1}{e})Q_i}) \big ]$, where $e$ is the base of the natural log. All entropies are measured in nats.</p> <p>Thank you very much for your help! Any ideas would be very helpful.</p> http://mathoverflow.net/questions/76093/an-inequality-on-difference-of-entropies/76105#76105 Answer by Ashok for An inequality on Difference of Entropies Ashok 2011-09-22T06:57:27Z 2011-09-22T06:57:27Z <p>If $P=(P_i)$ and $Q=(Q_i)$ are two distributions then $\sum_i P_i\log \frac{1}{Q_i}=H(P)+D(P\|Q)$.</p> <p>Hence $\sum_i (P_i-Q_i)\log\left(\frac{1}{\frac{P_i}{e}+(1-\frac{1}{e})Q_i}\right)=H(P)-H(Q)+D(P\|R)-D(Q\|R)$, where $R=\frac{1}{e}P+(1-\frac{1}{e})Q$.</p> <p>So, if we can show that $D(P\|R)-D(Q\|R) \ge 0$, we are done. I hope this can be true from the <em>Pythagorean property</em> of relative entropy of <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aop/1176996454" rel="nofollow">Csiszar</a>.</p> http://mathoverflow.net/questions/76093/an-inequality-on-difference-of-entropies/76135#76135 Answer by R Hahn for An inequality on Difference of Entropies R Hahn 2011-09-22T16:29:38Z 2011-09-26T15:58:56Z <p>EDIT: This is wrong -- careless mistake as noted in the comments. I thought I had deleted it, but here it still is. </p> <p>Working with the RHS of your inequality we have</p> <p>\begin{eqnarray}\sum_i (P_i - Q_i) \log{\left(\frac{1}{\frac{P_i}{e} + (1-\frac{1}{e})Q_i}\right)} &amp;=&amp; \sum_i (P_i - Q_i)\log{\left(\frac{e}{P_i + (e-1)Q_i}\right)}\\ &amp; = &amp; \sum_i (P_i - Q_i) (1 - \log{(P_i + (e-1)Q_i)})\\ &amp; = &amp; \sum_i (P_i - Q_i) + \sum_i (Q_i - P_i)\log{(P_i + (e-1)Q_i)}\\ &amp; = &amp; 1 - 1 + \sum_i (Q_i - P_i)\log{(P_i + (e-1)Q_i)}\\\ &amp; = &amp; \sum_i Q_i \log{(P_i + (e-1)Q_i)} - \sum_i P_i \log{(P_i + (e-1)Q_i)}\\\ &amp; \geq &amp; \sum Q_i \log{(Q_i)} - \sum_i P_i \log{(P_i)}\\ &amp; =&amp; -\mbox{H}(Q) + \mbox{H}(P). \end{eqnarray} The inequality follows from $\log{(P_i)} \leq \log{(P_i + (e-1)Q_i)}$ and $\log{(Q_i)} \leq \log{(P_i + (e-1)Q_i)}$. </p>