An inequality on Difference of Entropies - MathOverflow

An inequality on Difference of Entropies

2011-09-21T23:12:55Z

Hi,

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 ##

Let $P$ and $Q$ be two discrete probability distributions on the alphabet ${1,2,\dots n}$. Prove that:

$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.

Thank you very much for your help! Any ideas would be very helpful.

Answer by Ashok for An inequality on Difference of Entropies

2011-09-22T06:57:27Z

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)$.

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$.

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 Pythagorean property of relative entropy of Csiszar.

Answer by R Hahn for An inequality on Difference of Entropies

2011-09-22T16:29:38Z

EDIT: This is wrong -- careless mistake as noted in the comments. I thought I had deleted it, but here it still is.

Working with the RHS of your inequality we have

\begin{eqnarray}\sum_i (P_i - Q_i) \log{\left(\frac{1}{\frac{P_i}{e} + (1-\frac{1}{e})Q_i}\right)} &=& \sum_i (P_i - Q_i)\log{\left(\frac{e}{P_i + (e-1)Q_i}\right)}\\ & = & \sum_i (P_i - Q_i) (1 - \log{(P_i + (e-1)Q_i)})\\ & = & \sum_i (P_i - Q_i) + \sum_i (Q_i - P_i)\log{(P_i + (e-1)Q_i)}\\ & = & 1 - 1 + \sum_i (Q_i - P_i)\log{(P_i + (e-1)Q_i)}\\\ & = & \sum_i Q_i \log{(P_i + (e-1)Q_i)} - \sum_i P_i \log{(P_i + (e-1)Q_i)}\\\ & \geq & \sum Q_i \log{(Q_i)} - \sum_i P_i \log{(P_i)}\\ & =& -\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)}$.