1
$\begingroup$

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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – R Hahn
    Commented Sep 22, 2011 at 7:15
  • $\begingroup$ 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.) $\endgroup$
    – Kostas
    Commented Sep 22, 2011 at 7:44
0
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ Are you assuming $Q_i\geq P_i$ for all $i$? :) $\endgroup$
    – Gjergji Zaimi
    Commented Sep 22, 2011 at 16:33
  • $\begingroup$ Nope, but I'm not seeing it -- where is that required? $\endgroup$
    – R Hahn
    Commented Sep 22, 2011 at 16:42
  • $\begingroup$ 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)) $\endgroup$
    – Gjergji Zaimi
    Commented Sep 22, 2011 at 17:29
  • $\begingroup$ 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. $\endgroup$
    – R Hahn
    Commented Sep 22, 2011 at 18:32
  • $\begingroup$ 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. $\endgroup$
    – Kostas
    Commented Sep 22, 2011 at 18:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .