Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

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.

share|improve this answer
    
Notice, (if I am not mistaken), that nothing in this requires that $e$ is the base of natural log. Rather, what is crucial is just that $R$ is a convex combination of $P$ and $Q$. –  R Hahn Sep 22 '11 at 7:15
    
This does not hold for any convex combination of $P$ and $Q$. For example if we choose $R$ to be very close to $P$ then the first term is close to zero whereas the second is always positive. Therefore the number $e$ plays an important role. I have corroborated these with simulations. Number $\frac{1}{e}$ seems to be the largest number for which this holds for all the $P$ and $Q$ I have tested. (if we choose something less than $\frac{1}{e}$ then we get "closer" to $Q$ and this difference can become negative.) –  Kostas Sep 22 '11 at 7:44
add comment

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

share|improve this answer
    
Are you assuming $Q_i\geq P_i$ for all $i$? :) –  Gjergji Zaimi Sep 22 '11 at 16:33
    
Nope, but I'm not seeing it -- where is that required? –  R Hahn Sep 22 '11 at 16:42
    
Could you elaborate on the last sentence then? I see the inequality is equivalent to ∑Pi(log(Pi+(e−1)Qi)−log(Pi))≤∑Qi(log(Pi+(e−1)Qi)−log(Qi)) –  Gjergji Zaimi Sep 22 '11 at 17:29
    
In the fourth line I assume that the {P_i} and the {Q_i} sum to one. I guess I'm not 100% sure that is what the OP intended. –  R Hahn Sep 22 '11 at 18:32
    
Hi, in the 5th to the 6th line you use the same inequality for both the positive and negative term of the formula. For the positive term you can lower bounded by the inequality that you give. Yet the for the negative term it does not hold. –  Kostas Sep 22 '11 at 18:46
show 1 more 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.