## An inequality on Difference of Entropies

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

## 2 Answers

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.

-

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 2011 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 2011 at 7:44

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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

-

Are you assuming $Q_i\geq P_i$ for all $i$? :) – Gjergji Zaimi Sep 22 2011 at 16:33
Nope, but I'm not seeing it -- where is that required? – R Hahn Sep 22 2011 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 2011 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 2011 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 2011 at 18:46
show 1 more comment
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9201187491416931, "perplexity_flag": "head"}