14
$\begingroup$

I am looking for the most concise and elegant proof of the following inequality: $$ h(x) \geq 1- \left(1-\frac{x}{1-x}\right)^2, \qquad \forall x\in(0,1) $$ where $h(x) = x \log_2\frac{1}{x}+(1-x) \log_2\frac{1}{1-x}$ is the binary entropy function. Below is a graph of the two functions.

enter image description here

Of course, an option would be to differentiate $1,2,\dots,k$ times, and study the function this way — it may very well work, but is not only computationally cumbersome, it also feels utterly inelegant. (For my purposes, I could go this way, but I'd rather not.)

I am looking for a clever or neat argument involving concavity, Taylor expansion around $1/2$, or anything — an approach that would qualify as "proof from the Book."

$\endgroup$
  • $\begingroup$ A possible idea would be to show $h(x) \geq f(x) \geq g(x)$ for all $x\in (0,1)$, where $g(x) = 1-\left(\frac{x}{1-x}\right)^2$ and the "middle function" $f$ is defined by $f(x) = 1-4\left(\frac{1}{2}-x\right)^2$. The advantage is that $h,f$ are both symmetric around $1/2$ and concave, so that may be useful; and $f,g$ are both rational functions, with also may make things simpler. Yet, it still does not feel very clean... $\endgroup$ – Clement C. Apr 29 '16 at 14:10
  • 1
    $\begingroup$ Your graph suggests that $g(x)\geq g(1-x)$ for $x\in[0,\frac{1}{2}]$, and a simple computation confirms that : $g(x)-g(1-x)=\left(\frac{x}{1-x}-\frac{1-x}{x}\right) \left(2-\frac{x}{1-x}-\frac{1-x}{x}\right) $ and this will be $\geq 0$ by AM-GM. Since $h(1-x)=h(x)$, it suffices to show the inequality for $x\in[0,\frac{1}{2}]$. $\endgroup$ – Ewan Delanoy May 1 '16 at 17:59
4
$\begingroup$

I do not think that this is elegant enough.

Considering $$ h(x) = x \log_2\frac{1}{x}+(1-x) \log_2\frac{1}{1-x}$$ $$g(x)=1- \left(1-\frac{x}{1-x}\right)^2$$ $$f(x)=h(x)-g(x)$$ Expanding $f(x)$ as a Taylor series built at $x=\frac 12$, the result is $$f(x)= \left(16-\frac{2}{\log (2)}\right)\left(x-\frac{1}{2}\right)^2+64 \left(x-\frac{1}{2}\right)^3+ O\left(\left(x-\frac{1}{2}\right)^4\right)$$

$\endgroup$
  • $\begingroup$ Quick question: for that to apply to the full range $[0,1)$, shouldn't a a quantitative version of the expansion be used (e.g., Taylor-McLaurin)? Otherwise, for $\lvert x-1/2\rvert$ "big enough" the negative (odd-order) terms could conceivably make the whole thing negative, if they had big enough coefficients. $\endgroup$ – Clement C. Apr 29 '16 at 15:48
  • $\begingroup$ @ClementC.. I totally agree with your point about the very large coefficients and their possible impact for big enough $\lvert x-1/2\rvert$. I shall continue thinking about it. Cheers. $\endgroup$ – Claude Leibovici Apr 30 '16 at 3:44
  • $\begingroup$ I have the feeling that proving $h \geq f$ using this Taylor expansion at $1/2$ is much simpler (with $f(x) = 1-4(x-1/2)^2$ as in a comment of mine above). Since $f\geq g$ is almost immediate, this would give the (slightly stronger) $h\geq f\geq g$. $\endgroup$ – Clement C. May 4 '16 at 17:39
4
+200
$\begingroup$

Hopefully, this is right!

Note that from the weighted AM-GM inequality, We have that $$h(x)=\log_2{\frac{1}{x^x(1-x)^{1-x}}} \ge \log_2\frac{1}{x^2+(1-x)^2}$$ Thus we have to show $$\left(1-\frac{x}{1-x}\right)^2 \ge 1-\log_2\frac{1}{2x^2-2x+1}=\log_2{(4x^2-4x+2)}$$ Substitute $x=\frac{a+1}{a+2}$, and we have $$f(a)=a^2 -\log_2\left(\frac{a^2}{(a+2)^2}+1 \right) \ge 0$$ For $a \ge -1$. Differentiating gives $$f'(a)=2a\left(1-\frac{1}{(a+2) (a^2+2 a+2) \log(2)}\right)$$ and this $f'(a)>0$ for $a>0$ alternatively $f(a) \ge f(0)=0$ for $a \ge 0$.

Also, notice the local maxima lies between $-1$ and $0$. But since $f(-1)=f(0)=0$, we have that $f(a) \ge 0$ for $-1 \le a \le 0$.

Our proof is done.

$\endgroup$
  • $\begingroup$ Regarding the last part: between $-1$ and $0$, you're arguing that the local maxima are in $[-1,0]$, and that the function cancels at these two bounds. How does that immediately imply $f\geq 0$ on $[-1,0]$ (I may be missing something). $\endgroup$ – Clement C. May 12 '16 at 12:16
  • $\begingroup$ @ClementC. Originally I had this explained: notice that if the local maxima is between the two points, assume we have that local maxima at $\alpha$. Notice $f(x)$ is decreasing between $0$ and $\alpha$. For any values in between $f(x) \ge f(0)=0$. $\endgroup$ – S.C.B. May 12 '16 at 14:15
  • $\begingroup$ @ClementC Similarly, one can argue that beween $-1$ and $\alpha$, we have that $f(x)$ is increasing, and thus $f(x) \ge f(-1)=0$. $\endgroup$ – S.C.B. May 12 '16 at 14:17
  • $\begingroup$ I guess what is not immediately apparent to me is why there is only one local maximum (maxima is plural, isn't it?) and why there couldn't be then a local minimum between $\alpha$ and $0$ (i.e., you seem to assume there is only one local extermum in [-1,0]$, and that it's a maximum. Is that obvious? $\endgroup$ – Clement C. May 12 '16 at 14:19
  • $\begingroup$ @ClementC. Note that this local minimum shall satisfy $(\alpha+2)(\alpha^2+2\alpha+2)=\log_2(e)$. However, the derivative of $f(\alpha)=(\alpha+2)(\alpha^2+2\alpha+2)$ is $3\alpha^2+8\alpha+6$, which is always larger than $0$. Thus $f(\alpha)$ is always increasing, and thus $f(\alpha)=\log_2(e)$ has at most one zero. $\endgroup$ – S.C.B. May 12 '16 at 14:25
2
+100
$\begingroup$

As noted in my comment, it suffices to show the inequality for $x\in[0,\frac{1}{2}]$. Note that the inequality becomes an equality at the endpoints, $0$ and $\frac{1}{2}$. The inequality is tighter around $\frac{1}{2}$ than around $0$. In our proof, we will distinguish two (overlapping) cases, $x$ near $0$ or $x$ near $\frac{1}{2}$. When $x$ is near $\frac{1}{2}$, we Taylor-expand the logs at $\frac{1}{2}$. When $x$ is near $0$, we use cruder (constant, in fact) bounds on the logs.

We have to show that

$$ x\log(x)+(1-x)\log(1-x) \leq \log(2)\left(\frac{3x^2-2x}{(1-x)^2}\right) \tag{1} $$

As $\frac{\log(1-x)-\log(\frac{1}{2})}{\frac{1}{2}-x}\leq 2 \leq \frac{\log(\frac{1}{2})-\log(x)}{\frac{1}{2}-x}$, we have $\log(x) \leq (-1-\log(2))+2x$ and $\log(1-x) \leq (1-\log(2))-2x$, so (1) will be true whenever

$$ x\left[(-1-\log(2))+2x\right]+(1-x)\left[(1-\log(2))+2x\right] \leq \log(2)\left(\frac{3x^2-2x}{(1-x)^2}\right) \tag{2} $$

By construction, (2) is simplifiable by $(x-\frac{1}{2})^2$ and a little cleanup massaging shows that (2) is equivalent to $(1-x)^2 \leq \log(2)$. This shows (1) for $x\geq 1-\sqrt{\log(2)}$. Note that the number $1-\sqrt{\log(2)} \approx 0.167$ is strictly less than $0.2$.

Now, let us deal with the case when $x\leq 0.2$. Then $\log(x)\leq\log(0.2)$ and $\log(1-x)\leq 0$, so that it (1) is true whenever $$ x\log(0.2) \leq \log(2)\left(\frac{3x^2-2x}{(1-x)^2}\right) \tag{3} $$

Clearly, (3) is equivalent to $$ \frac{\log(0.2)}{\log(2)} \leq \frac{3x-2}{(1-x)^2} $$ Now, the RHS can be rewritten $-\frac{35}{16}+\frac{35(\frac{1}{5}-x)(\frac{3}{7}-x)}{16(1-x)^2}$ and we conclude the proof by noting that $\frac{\log(0.2)}{\log(2)} < -\frac{35}{16}$ because $\frac{\log(0.2)}{\log(2)} \approx -2.32$ and $-\frac{35}{16} \approx -2.18$.

$\endgroup$
2
$\begingroup$

$$h(x) = x \log_2\frac{1}{x}+(1-x) \log_2\frac{1}{1-x}\ge1- \left(1-\frac{x}{1-x}\right)^2$$

If we let $x=\frac{1+y}{2}$ and push through the algebra, the claim is equivalent to:

$$1-\frac{1}{2}\log_2(1-y^2)-\frac{y}{2}\log_2\left(\frac{1+y}{1-y}\right)\ge1-\frac{4y^2}{(1-y)^2}$$

which can be rearranged to:

$$\frac{8y^2}{(1-y)^2}\ge \log_2(1-y^2) + y\log_2\left(\frac{1+y}{1-y}\right)$$

Now, using the well-known $\ln u\le u-1$:

$$\ln v^2\le v^2-1\implies \ln v \le \frac{v^2-1}{2}$$

and taking $v=\frac{1+y}{1-y}$, this becomes:

$$\ln\left(\frac{1+y}{1-y}\right)\le \frac{2y}{(1-y)^2}$$

Noting that $\log_2(1-y^2)\le0$, we can see

$$\log_2(1-y^2) + y\log_2\left(\frac{1+y}{1-y}\right)\le y\frac{1}{\ln2}\frac{2y}{(1-y)^2}=\frac{2}{\ln2}\frac{y^2}{(1-y)^2}\le \frac{8y^2}{(1-y)^2}$$

and we are done for $y>0$.

For $y<0$ it's a little trickier, because the other $\log$ term does come into play - still working out a nice argument for how to bound things appropriately.

$\endgroup$
0
$\begingroup$

The long and painful way: "differentiating, and differentiating."

Define $f,g\colon (0,1)\to \mathbb{R}$ by $f(x) = 1-4\left(x-\frac{1}{2}\right)^2$ and $g(x) = 1-\left(1-\frac{x}{1-x}\right)^2$. We will show $$ h(x) \geq f(x) \geq g(x), \qquad x\in(0,1). $$

enter image description here


Claim. $h(x) \geq f(x)$ for all $x\in(0,1)$.

Proof. Both functions are $C^\infty$, and we have $$ h''(x) - f''(x) = \frac{-8}{x(1-x)} \left(x^2-x+\frac{1}{8\ln 2}\right) $$ which cancels at $x_0 \stackrel{\rm def}{=} \frac{1-\sqrt{1-\frac{1}{2\ln 2}}}{2}\simeq 0.236$ and $x_1 = 1-x_0$.

We thus have the following, as $\lim_{0^+} (h''-f'') = \lim_{1^-} (h''-f'') = -\infty$: $$ \begin{array}{|c|ccc|} \hline x & 0 & &x_0 & \frac{1}{2} & x_1 && 1 \\ \hline h''-f'' & -\infty &-&0&+&0& - &-\infty\\ \hline \end{array} $$

Moreover, since $h'(x) - f'(x) = \frac{1}{\ln 2}\left(8\ln 2 \cdot x + \ln\frac{1-x}{x} - 4\ln 2 \right)$, we have $\lim_{0^+} (h'-f') = - \lim_{1^-} (h'-f') = \infty$ and $(h'-f')(\frac{1}{2})=0$. Since $x_0 < \frac{1}{4}$ and $(h'-f')(\frac{1}{4}) = \frac{\ln\frac{3}{4}}{\ln 2} < 0$, we know that $(h'-f')(x_0) = -(h'-f')(x_1) < 0$.

$$ \begin{array}{|c|ccc|} \hline x & 0 & &x_0 && \frac{1}{2} && x_1 && 1 \\ \hline h''-f'' & -\infty &-&0&&+&&0& - &-\infty\\ \hline h'-f' & +\infty &\searrow&-&\nearrow& 0&\nearrow&+& \searrow &-\infty\\ \hline \end{array} $$ This in turn implies that $h'-f'$ has exactly three roots, namely $r_0 < \frac{1}{2} < r_1$ with $r_1 = 1-r_0 \in (0,x_0)$.

$$ \begin{array}{|c|ccc|} \hline x & 0 & &r_0 && \frac{1}{2} && r_1 && 1 \\ \hline h'-f' &&+&0&-& 0&+&0& - &\\ \hline h-f &0&\nearrow&&\searrow& 0&\nearrow&& \searrow 0&\\ \hline \end{array} $$ This implies the claim, as $\lim_{0^+}(h-f) = (h-f)(1/2) = \lim_{1^-}(h-f) =0$: $h\geq f$ on $(0.1)$.


Claim. $f(x) \geq g(x)$ for all $x\in(0,1)$.

Proof. Writing out the expression and massaging it, we get that for all $x\in (0,1)$ $$ f(x) - g(x) = \frac{x (2-x) (1-2 x)^2}{(1-x)^2}\geq 0.$$

$\endgroup$
  • $\begingroup$ I feel my proof is similar to yours. $\endgroup$ – S.C.B. May 12 '16 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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