# An upper bound of binary entropy

Binary entropy is given by $$H_{\mathrm b}(p) = -p \log_2 p - (1 - p) \log_2 (1 - p), \hspace{6 mm} p \le \frac{1}{2}$$ How can I prove that $$H_{\mathrm b}(p) \le 2 \sqrt{p(1-p)}$$

• Is $\mathrm{b}$ supposed to be equal to $2$? If not, then what is it? ${}\qquad{}$ – Michael Hardy Sep 14 '15 at 17:31
• $b$ stands for binary. – guest123456 Sep 15 '15 at 1:37

## 2 Answers

Given $I=(0,1)$, for any $x\in I$ let $g(x)=-x\log x$ and $f(x)=g(x)+g(1-x)$.

Obviously $f\in C^{\infty}(I)$, $\,f(x)=f(1-x)$, $\,f>0$ and $$\lim_{x\to 0^+}f(x)=\lim_{x\to 1^-}f(x) = 0.$$ We have $f'(x)=\log(1-x)-\log(x)$, hence:

$$\begin{eqnarray*} \frac{d}{dx}\frac{f(x)^2}{x(1-x)}&=&f(x)\cdot\frac{-x\log x+(1-x)\log(1-x)}{x^2(1-x)^2}\\&=&\frac{g(x)^2-g(1-x)^2}{x^2(1-x^2)}.\tag{1}\end{eqnarray*}$$ Since $g(x)>g(1-x)$ over $J=\left(0,\frac{1}{2}\right)$ (the proof of this fact comes later), the function $\frac{f(x)^2}{x(1-x)}$is increasing over $J$, hence:

$$f(x)\leq 2\cdot f\left(\frac{1}{2}\right)\cdot\sqrt{x(1-x)}=\color{blue}{\left(2\log 2\right)}\sqrt{x(1-x)} \tag{2}$$

follows. Back to the missing part: obviously $g(x)-g(1-x)$ vanishes at $0,\frac{1}{2},1$. In order to prove that these points are the only zeros, it is enough to check that $h(x)=g(x)-g(1-x)$ is concave over $J$. Pretty easy:

$$\frac{d^2}{dx^2}h(x) = \frac{2x-1}{x(1-x)}.\tag{3}$$ The proof is finished by noticing that $f(p)=\log(2)\cdot H_{\mathrm b}(p)$.

An very tight approximation for the binary entropy function is given by:

$$H_{\mathrm{b}}(p) \approx \left(4p(1-p)\right)^{\frac{3}{4}}.\tag{4}$$

It does not hold as an upper bound or a lower bound, the the absolute value of the difference between the RHS and the LHS is always less than $8\cdot 10^{-3}$.

• Can you please explain how you got step $(2)$ from $(1)$? – guest123456 Sep 12 '15 at 14:43
• @guest123456: since $\frac{f(x)^2}{x(1-x)}$ is increasing over $\left(0,\frac{1}{2}\right)$, we have: $$\frac{f(x)^2}{x(1-x)}\leq \frac{f(1/2)^2}{1/4} = 4\,f(1/2)^2 = 4 \log^2 2$$ and rearranging $f(x) \leq 2\log(2)\sqrt{x(1-x)}$ follows. – Jack D'Aurizio Sep 12 '15 at 14:52
• Thank you very much sir, awesome explanation. It was too difficult for me to solve in examination hall :) – guest123456 Sep 12 '15 at 14:54
• The error is that the problem specifies binary logarithm, so there should not be a $\ln(2)$ in your answer. Meaning your comment on the question is also not correct. – user21820 Sep 12 '15 at 14:54
• @user21820: thank you, I removed it and I am fixing the answer. Anyway, the inequality about my $f(x)$ is right. We just have to scale it by a factor $\log(2)$ to prove the wanted bound on the binary entropy. – Jack D'Aurizio Sep 12 '15 at 14:59

This inequality is actually not trivial. Here is a proof sketch. We know that there are three equality cases, so to get rid of the ones at the ends we take $\frac{H(p)}{2\sqrt{p(1-p)}}$. By differentiating with respect to $p$ and slowly analyzing the result (elementary algebra plus the inequality $x-\frac{1}{2}x^2 \le \ln(1+x) \le x$ for $x \ge 0$) it is possible to show that it is decreasing for $p > \frac{1}{2}$, which by symmetry means that it is maximum when $p = \frac{1}{2}$. It is not that hard but not elegant.

• Seems a lot of calculation, and as you said not elegant. But I am OK with it. Actually this problem was given in my Information Theory exam today and was marked as a difficult problem. So maybe there isn't any simple and elegant proof. – guest123456 Sep 12 '15 at 13:21
• @guest123456: I came up with this inequality last year when trying to find a reasonable bound for the binary entropy function, and spent a good deal of time finding a way to prove it. Should be unrelated to your exam question haha.. – user21820 Sep 12 '15 at 13:27
• This is not an answer but just the sketch of it. Details are not so hard to be provided. – Jack D'Aurizio Sep 12 '15 at 14:26
• @JackD'Aurizio: Sure it's not meant to be a full answer since I don't find joy in posting what I consider inelegant computations. =) – user21820 Sep 12 '15 at 14:53
• @user21820: ok, I am fine with that, I'll stop nitpicking :) – Jack D'Aurizio Sep 12 '15 at 15:12