# (Elegant) proof of an inequality: $h(x) \geq 1- (1-\frac{x}{1-x})^2$, where $h$ is the binary entropy function

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.

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."

• 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... – Clement C. Apr 29 '16 at 14:10
• 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}]$. – Ewan Delanoy May 1 '16 at 17:59

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

• 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. – Clement C. Apr 29 '16 at 15:48
• @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. – Claude Leibovici Apr 30 '16 at 3:44
• 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$. – Clement C. May 4 '16 at 17:39

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.

• 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). – Clement C. May 12 '16 at 12:16
• @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$. – S.C.B. May 12 '16 at 14:15
• @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$. – S.C.B. May 12 '16 at 14:17
• 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? – Clement C. May 12 '16 at 14:19 • @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. – S.C.B. May 12 '16 at 14:25 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$. $$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. 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).$$ 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.$$

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