5
$\begingroup$

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

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

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}$.

$\endgroup$
  • $\begingroup$ Can you please explain how you got step $(2)$ from $(1)$? $\endgroup$ – guest123456 Sep 12 '15 at 14:43
  • 2
    $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Sep 12 '15 at 14:52
  • $\begingroup$ Thank you very much sir, awesome explanation. It was too difficult for me to solve in examination hall :) $\endgroup$ – guest123456 Sep 12 '15 at 14:54
  • 2
    $\begingroup$ 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. $\endgroup$ – user21820 Sep 12 '15 at 14:54
  • 1
    $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Sep 12 '15 at 14:59
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – guest123456 Sep 12 '15 at 13:21
  • $\begingroup$ @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.. $\endgroup$ – user21820 Sep 12 '15 at 13:27
  • $\begingroup$ This is not an answer but just the sketch of it. Details are not so hard to be provided. $\endgroup$ – Jack D'Aurizio Sep 12 '15 at 14:26
  • $\begingroup$ @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. =) $\endgroup$ – user21820 Sep 12 '15 at 14:53
  • 1
    $\begingroup$ @user21820: ok, I am fine with that, I'll stop nitpicking :) $\endgroup$ – Jack D'Aurizio Sep 12 '15 at 15:12

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.