37
$\begingroup$

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.

The problem originates from this math stack exchange post, and cardinal's rewording 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.

$\endgroup$
11
  • 2
    $\begingroup$ (+1) Thanks for reminding me of this question. I played with it pretty intensely for a couple of afternoons when it was first posted, but it seemed quite tight, and then I had to move on to other things and it faded from memory. Seeing a solution would be nice. $\endgroup$
    – cardinal
    Jul 31, 2013 at 22:49
  • 1
    $\begingroup$ It is likely I am simply misreading it, but I think the $\mathbb E$ should be replaced by sums everywhere it occurs. $\endgroup$
    – cardinal
    Aug 1, 2013 at 1:47
  • 1
    $\begingroup$ @cardinal: Thank you, corrected. I wrote things incorrectly. $\endgroup$ Aug 1, 2013 at 2:20
  • 3
    $\begingroup$ Looks like you can do it entry-wise if you take into account that $\sqrt{X_jY_j}\le K\le\sqrt{X_jY_j}+\sqrt{(1-X_j)(1-Y_j)}$ for every $j$. I'll see if I can pull it through. $\endgroup$
    – fedja
    Aug 3, 2013 at 21:43
  • 11
    $\begingroup$ I believe I have reduced it to $x,y,z>0,xy=z^2\Longrightarrow (1+x)\log(1+y)+(1+y)\log(1+x)\ge 2(1+z)\log(1+z)$. Still have no elegant proof of that one (I prefer to avoid brute force differentiation unless completely cornered). Any ideas? $\endgroup$
    – fedja
    Aug 3, 2013 at 23:37

3 Answers 3

19
$\begingroup$

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 of the main inequality on AoPS. Alas, it also requires some tedious computations...

$\endgroup$
6
  • $\begingroup$ The connection is just terrible and rendering LaTeX in the process makes the browser stop, cursor jump, etc. I'll try to finish but each line is a fight :(. $\endgroup$
    – fedja
    Aug 12, 2013 at 9:18
  • $\begingroup$ I'm confused; in the bit after "Assuming $a\ge c\ge b$", the inequality seems the wrong way round. Because $p^{-1}>1$ so $(p^{-1}+at)^{-1} < (1+at)^{-1}$, right? $\endgroup$ Aug 12, 2013 at 17:57
  • $\begingroup$ Of course. But it is a factor in the negative part! $\endgroup$
    – fedja
    Aug 12, 2013 at 18:40
  • $\begingroup$ Oh, silly me! By the way, you should maybe post this as an answer on the original Math.SE post as well. $\endgroup$ Aug 12, 2013 at 21:07
  • 1
    $\begingroup$ @fedja Thank you for sharing your answer. I posted a link to this page on Math.StackExchange. $\endgroup$ Aug 21, 2013 at 1:45
4
$\begingroup$

Here is another alternative proof of the inequality $$ (1+a)\ln(1+b)+(1+b)\ln(1+a)\ge 2(1+c)\ln(1+c) \tag{1} $$ with $$a,b,c>0,\ ab=c^2,\tag{2}$$ proved in the above answer.

The left-hand side of $(1)$ goes to $\infty$ as $a$ or $b$ does so while keeping condition $(2)$. So, it remains to show that a conditional local extremum given $(2)$ can only be attained when $a=b$ and hence $a=b=c$. Without loss of generality, $a<b$. By Lagrange multipliers, for any such local extremum $(a,b)$ one has $\ln(1+b)+\frac{1+b}{1+a}=\lambda b$ and $\ln(1+a)+\frac{1+a}{1+b}=\lambda a$ for some real $\lambda$. Multiplying these two equations by $a$ and $b$, respectively, and then subtracting one from the other, for
$$d(a,b):=a\ln(1+b)+a\,\frac{1+b}{1+a}-b\ln(1+a)-b\,\frac{1+a}{1+b} $$ one has $d(a,b)=0$ if $(a,b)$ is a local extremum. But $d''_{b,a}(a,b)=\frac b{1 + b^2}- \frac a{1 + a^2}$, which vanishes only if $a=b$ or $ab=1$. Next, $$d'_b(a,b)=\frac{a^2 b+a b (b+3)-1}{(1+a) (1+b)^2}-\ln(1+a). $$ So, $d'_b(0+,b)=-1/(1+b)^2<0$, $d'_b(1/b,b)\big|_{b=1/a}=\frac a{1+a}-\ln(1+a)<0$, and $d'_b(b,b)=\frac{2b-1}{1+b}-\ln(1+b)<0$ (the latter two inequalities easily checked by differentiation). So, $d'_b(a,b)<0$ whenever $0<a<b$. So, $d(a,b)<d(a,a)=0$ whenever $0<a<b$, which contradicts the necessary condition $d(a,b)=0$ for $(a,b)$ to be a conditional local extremum. This completes the proof.

$\endgroup$
1
$\begingroup$

Remark: This is to give an alternative proof of the inequality in fedja's nice answer: $$ (1+a)\log(1+b)+(1+b)\log(1+a)\ge 2(1+c)\log(1+c) $$ where $a, b, c>0$ with $ab=c^2$.

Proof.

WLOG, assume that $a \le b$. Let $x = \frac{a}{c} \in (0, 1]$. It suffices to prove that $$f(x) := (1 + cx)\ln(1 + c/x) + (1 + c/x)\ln(1 + cx) - 2(1 + c)\ln(1 + c) \ge 0.$$

We have $$f'(x) = c\ln(1 + c/x) - \frac{c(1+cx)}{x(x + c)} - \frac{c\ln(1 + cx)}{x^2} + \frac{c(x+c)}{x(1+cx)}$$ and $$f''(x) = \frac{2c}{x^2(x+c)} - \frac{c^2(1+cx)}{x^2(x+c)^2} + \frac{2c\ln(1+cx)}{x^3} - \frac{2c^2}{x^2(1+cx)} - \frac{c^2(x+c)}{x(1+cx)^2}.$$

Let $g(x) := x^3 f''(x)$. We have \begin{align*} g'(x) &= \frac{c^2(1-x^2)}{(x+c)^3(1+cx)^3}\\ &\qquad \times [cx^4 + (c^2 + 3)x^3 + (2c^5 - 6c^3 + 10c)x^2 + (c^2 + 3)x + c]\\ & \ge 0. \end{align*} Also, $g(0) = 0$. Thus, $g(x) \ge 0$ on $(0, 1]$. Thus, $f''(x) \ge 0$ on $(0, 1]$. Also, $f'(1) = 0$. Thus, $f'(x) \le 0$ on $(0, 1]$. Also, $f(1) = 0$. Thus, $f(x) \ge 0$ on $(0, 1]$.

We are done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.