
> 
> Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$, and set $K=\sum\_i\sqrt{X(i)Y(i)}$ so that $Z:=\frac{1}{K}\sqrt{XY}$ is also a probability measure on $\{1,2,\dots,n\}$. How can we prove the inequality
> $$H(X)+H(Y)\geq 2K^2 H(Z),$$ where $H(X)=-\sum\_{i=1}^n X(i)\log X(i)$ is the [entropy function](http://en.wikipedia.org/wiki/Entropy_%28information_theory%29).
> 
> 
> 


The problem originates from this [math stack exchange post](https://math.stackexchange.com/questions/41340/im-not-sure-about-this-inequality-how-to-prove-or-disprove-it), and [cardinal's rewording](https://math.stackexchange.com/questions/41340/im-not-sure-about-this-inequality-how-to-prove-or-disprove-it#comment92485_41340) of it in the comments. Despite having being asked over two years ago, with numerous bounties posted, the problem was never solved, and for that reason I am posting it here.


I checked the inequality numerically on matlab for millions of choices of $X$ and $Y$, with $n$ up to size $100$, and it always held, which suggests that finding a counter example is unlikely.


**Remark:** By Cauchy Schwarz, $1\geq K^2,$ so the above inequality would be implied by $H(X)+H(Y)\geq 2H(Z).$ However it is worth noting that this inequality does not hold, so the factor of $K^2$ is important.



An entropy inequality
OK, having spent about 20 hours on the search of a nice proof (which extinguished my passion for beauty for the next several days at least), I'm resorting to the brute force. I will love to see someone else to avenge this pitiful defeat of mine... 


As I mentioned in the comment, the key to the solution is the inequality
$$
(1+a)\log(1+b)+(1+b)\log(1+a)\ge 2(1+c)\log(1+c)
$$
where $a,b,c>0, ab=c^2$.
Consider the function
$$
F(t)=(1+a)\log(1+bt)+(1+b)\log(1+at)-2(1+c)\log(1+ct)\,.
$$
We have
$$
\begin{aligned}
F'(t)&=\frac{(1+a)b}{1+bt}+\frac{(1+b)a}{1+at}-2\frac{(1+c)c}{1+ct}
\\
&=(a+b-2c)\frac{(c^2t-1)(ct-1)}{(1+at)(1+bt)(1+ct)}
\end{aligned}
$$
While the derivation of the last equality is tedious, to check it, it suffices to show that $F'(c^{-2})=F'(c^{-1})=0$ and to compute the free term in the numerator to get the right normalization factor, so I'll skip the explicit computations.
It will be convenient to denote $p=c^{-1}$. Then we need to show that
$$
\int\_0^1\frac{(t-p^2)(t-p)}{(1+at)(1+bt)(1+ct)}\,dt\ge 0\,.
$$ 
If $p>1$, there is nothing to do because the integrand is non-negative. So, we'll assume that $p<1$ from now on.
Since the denominator is increasing in $t$, and the numerator is positive on $(0,p^2)$, negative on $(p^2,p)$ and then positive again on $(p,1)$, we would be in good shape if we had
$$
\int\_0^p(t-p^2)(t-p)\,dt=-\frac{p^3}6+\frac{p^4}2\ge 0\,,
$$
which is true for $p\ge \frac 13$. Thus, we may assume that $p<\frac 13$.


Now we cannot just neglect the interval $[p,1]$. We shall neglect the interval $[0,p^2]$ instead. Assuming $a\ge c\ge b$, we write 
$$
\begin{multline}
\int\_{p^2}^p\frac{(t-p^2)(t-p)}{(1+at)(1+bt)(1+ct)}\,dt=
\int\_p^1\frac{(t-p)(t-1)p^2}{(p^{-1}+at)(1+bpt)(1+cpt)}\,dt
\\
\ge
\int\_p^1\frac{(t-p)(t-1)p^2}{(1+at)(1+bpt)(1+t)}\,dt
\end{multline}
$$
Combining this with $\int\_p^1$, we get the lower bound
$$
\int\_p^1\frac{(t-p)}{(1+at)}\left[\frac{(t-1)p^2}{(1+bpt)(1+t)}
+\frac{t-p^2}{(1+bt)(1+ct)}\right]\,dt
$$
Note now that $bp\le 1$ and the higher $b$ is, the harder it is for the last square bracket to be non-negative. Thus, it is enough to estimate the bracket for $bp=1$, i.e., to demonstrate that
$$
(1-t)(p+t)^2\le (t-p^2)(1+t)^2\,.
$$
However
$$
t-p^2\ge t(1-t)
$$
and
$$
(p+t)^2=2pt+p^2+t^2<t+2t^2<t(1+t)^2\,.
$$
I would appreciate it if someone checks this ugly monster before I post the remaining (almost trivial) part of the proof :). 


Edit: Assuming that those who upvoted took trouble to read and verify the above part, the end is as follows. 


Let $X=X\_j$, $Y=Y\_j$, and $K$ be as before. Then, as I said, $\sqrt{XY}\le K\le\sqrt{XY}+\sqrt{(1-X)(1-Y)}$ (Cauchy). We have $Z=Z\_j=\frac{\sqrt{XY}}K$, so it will suffice to show that
$$
2K^2 Z\log\frac 1Z=2K\sqrt{XY}\log\frac{K}{\sqrt{XY}}\le X\log\frac 1X+Y\log\frac 1Y\,.
$$
Note that the left hand side is convex in $K$ for fixed $X,Y$. If $K=\sqrt{XY}$, the inequality is trivial ($0$ is less than or equal to a non-negative number). Thus, we need only consider the case $K=\sqrt{XY}+\sqrt{(1-X)(1-Y)}$. Dividing by $XY$ and putting $X^{-1}=1+x, Y^{-1}=1+y$, so that $\frac{1-X}X=x,\frac{1-Y}Y=y$, we see that this case reduces exactly to the above inequality.


P.S. There is an [alternative proof](http://www.artofproblemsolving.com/Forum/viewtopic.php?f=51&t=547118) of the main inequality on AoPS. Alas, it also requires some tedious computations...


