13
$\begingroup$

Let $p+p'=1$ and $q+q'=1$.

If $\log(p/q)>\log(q'/p')$ then $(p+q)\log(p/q)>(p'+q')\log(q'/p')$.

This looks deceptively simple to prove, but it's not. I couldn't crack it using Jensen's Inequality.

However, it is surely true -- although very tight. I checked it out numerically. I asked a competent colleague, who was also stumped.

It came up as I was meditating on asymmetry properties for the Kullback-Leibler divergence.

$\endgroup$

2 Answers 2

5
$\begingroup$

Let $x=\frac{p}{q}$ and $y=\frac{q^{\prime}}{p^{\prime}}=\frac{1-q}{1-p}.\;\;\;$ We know that $x>y$ since $\ln x>\ln y$, and

we want to show that $\color{blue}{(p+q)\ln x>(p^{\prime}+q^{\prime})\ln y}$.

Since $p=xq$ and $q^{\prime}=p^{\prime}y,\;\;$ $p+q=q(x+1)$ and $p^{\prime}+q^{\prime}=p^{\prime}(y+1)$.

Then $\displaystyle q^{\prime}=p^{\prime}y\implies 1-q=(1-p)y\implies q=1-y+py=1-y+xqy\implies q=\frac{1-y}{1-xy}$,

and $\displaystyle p^{\prime}=1-p=1-xq=1-\frac{x(1-y)}{1-xy}=\frac{1-x}{1-xy}.$

Therefore we need to show that $\displaystyle\color{blue}{ x>y\implies \frac{1-y}{1-xy}(x+1)\ln x>\frac{1-x}{1-xy}(y+1)\ln y}$.

Since $\displaystyle f(x)=\frac{(x+1)\ln x}{1-x}$ is increasing on $(0,1)$ and decreasing on $(1,\infty)$,

1) When $x<1, y<1$, we have that $\displaystyle \frac{(x+1)\ln x}{1-x}>\frac{(y+1)\ln y}{1-y}$ since $f$ is increasing on $(0,1)$,

$\;\;\;$ so it follows that $ \displaystyle\frac{1-y}{1-xy}(x+1)\ln x>\frac{1-x}{1-xy}(y+1)\ln y$.

2) When $x>1, y>1$, we have that $\displaystyle\frac{(x+1)\ln x}{1-x}<\frac{(y+1)\ln y}{1-y}$ since $f$ is decreasing on $(1,\infty)$;

$\;\;\;$ so it follows that $ \displaystyle\frac{1-y}{1-xy}(x+1)\ln x>\frac{1-x}{1-xy}(y+1)\ln y$.

(Notice that if $x>1$, then $p>q\;$ so $1-q>1-p$ and therefore $y>1$.)

$\endgroup$
8
  • $\begingroup$ What of the case $x>1>y$? $\endgroup$
    – Macavity
    Commented Sep 10, 2015 at 2:21
  • $\begingroup$ @Macavity Good question - I will edit my answer to cover this case. $\endgroup$
    – user84413
    Commented Sep 10, 2015 at 15:42
  • $\begingroup$ I am just working through this proof, but I should add that I failed to mention that these are probability distributions, so I am primarily interested in the case 0<p,q<1. $\endgroup$
    – maibaita
    Commented Sep 10, 2015 at 16:09
  • $\begingroup$ Nicely done! +1 $\endgroup$
    – Macavity
    Commented Sep 10, 2015 at 16:30
  • $\begingroup$ @Macavity Thanks - I appreciate your positive response! $\endgroup$
    – user84413
    Commented Sep 10, 2015 at 16:53
1
$\begingroup$

Not an answer at all, but a too-long-for-comment hint to those who are trying :

The statement is equivalent to the following. For any positive numbers $a_1,a_2,b_1,b_2$ such that $a_1+a_2=1$ and $b_1+b_2=1$

$$ \log(a_1/b_1) + \log(a_2/b_2) > 0\implies (a_1+b_1) \log(a_1/b_1) + (a_2+b_2) \log(a_2/b_2) > 0$$

This assertion seems to be true, but the tempting generalization (for larger tuples, say $(a_1,a_2,a_3)$ and $(b_1,b_2,b_3)$ ) is false. This suggests that an attack via log-sum-inequality would probably not work.

$\endgroup$
1
  • $\begingroup$ leonbloy, yes the generalization is definitely false. Here is a counter-example for three dimensions: A=(1/3,1/3,1/3) and B=(1/2,1/4,1/4). $\endgroup$
    – maibaita
    Commented Sep 10, 2015 at 16:26

You must log in to answer this question.

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