12
$\begingroup$

Denote $H(p) = -p \log_2 p - (1-p)\log_2(1-p)$ [Shannon entropy].

It is well-known that $H$ is a concave function that increases on $(0,\frac{1}{2})$ and decreases on $(\frac{1}{2}, 1)$.

Let $\beta, \beta_1, \beta_2 \in (0,\frac{1}{2})$ be real numbers such that $ H(\beta_1) + H(\beta_2) = 2 H(\beta).$

Let $r$ be a positive real number such that all values $\beta_1 + r, \beta_2 + r,\beta + r$ are less than $\frac{1}{2}$.

How to prove the following inequality? $$ H(\beta_1 + r - 2\beta_1 r) + H(\beta_2 + r - 2\beta_2 r) \ge 2H(\beta + r - 2\beta r)$$

UPD: Why I know that this inequality holds? Because it follows from rather deep result in Kolmogorov complexity theory. But I hope there is a simpler proof of this fact:)

$\endgroup$
2
  • $\begingroup$ Are you sure this result is right? By letting $$G(r) = H(\beta_1 + r - 2\beta_1 r) + H(\beta_2 + r - 2\beta_2 r) - 2H(\beta + r - 2\beta r)$$, I see that $G'(0)$ can be non null while it must be $0$ in order for the inequality to be true within a small neighbor of $0$ $\endgroup$ Jun 7, 2021 at 12:15
  • $\begingroup$ @ParesseuxNguyen Thank you, I have added that $r>0$ $\endgroup$ Jun 7, 2021 at 13:28

1 Answer 1

4
$\begingroup$

Nice result, it leads me to something wanted to craft but didn't. I will prove a better result

Proposition 1
Let $\beta, \beta_1, \beta_2 \in (0,\frac{1}{2})$ be real numbers such that $ H(\beta_1) + H(\beta_2) = 2 H(\beta).$
Then for all $r \in (0,1)$, we have: $$ H(\beta_1 + r - 2\beta_1 r) + H(\beta_2 + r - 2\beta_2 r) \ge 2H(\beta + r - 2\beta r)$$

Before going into details, I give one comparison lemma.

Lemma 2 (A lemma comparing convexity) Let $G$ and $g$ be two differentiable functions from a same domain $[a,b]$ to $\mathbb{R}$. Suppose that $G'$ is strictly positive and that the function $s \mapsto \frac{g'(s)}{G'(s)}$ is increasing with $s$, then
i) For all number $s,t,v \in (a,b)$ such that $G(s)+G(t)=2G(v)$, we have: $$g(s)+g(t) \ge 2g(v)$$

ii) $s \mapsto \frac{g(s)-g(b)}{G(s)-G(b)}$ is an increasing function.

Demonstration
i) Let $D=[G(a),G(b)]$ and let us consider the function $f(x)=g(G^{-1}(x))$ on $D$. Clearly, $f'(x)=\frac{g'(G^{-1}(x))}{G'(G^{-1}(x))}=\left(\frac{g'}{G}\circ G^{-1}\right)(x)$ is a composition of two increasing function hence $f'(x)$ is increasing, which means $f$ is a convex function i.e $$f(x)+f(y) \ge 2 f \left( \frac{x+y}{2}\right)$$ for all $x,y \in D$. Now choosing $x=G(s), y= G(t)$, we have our conclusion.

ii) For any $a\le s <t <b$ , by Cauchy's MVT, there are two real numbers $p \in (s,t) , q \in (t,b)$ such that: $$\frac{g(s)-g(t)}{G(s)-G(t) }=\frac{g'}{G'}(p) \quad \frac{g(t)-g(b)}{G(t)-G(b) }=\frac{g'}{G'}(q)$$

Thus $$\begin{align}\frac{g(s)-g(b)}{G(s)-G(b)} &= \left(\frac{G(t)-G(s)}{G(b)-G(s)}\right) \frac{g'}{G'}(p)+\left(\frac{G(b)-G(t)}{G(b)-G(s)}\right)\frac{g'}{G'}(q)\\&\le \frac{g'}{G'}(q) = \frac{g(t)-g(b)}{G(t)-G(b) } \end{align}$$ because of the monotonicity of $\frac{g'}{G}$ and the fact that $p<q$.
Hence the conclusion.

$\square$

Back to the demonstration of our Proposition 1.
Demonstration for the Proposition 1
Choosing $h(p)= H( r+p-2pr)$.
Note that $H'$ is strictly positive on $(0,1/2)$ (the boundary doesn't matter), based on the first of our lemma, what we need to do is to prove that $x \mapsto \frac{h'}{H'}(x)$ is an increasing function.
Then again, by noticing that $h'(1/2)=H'(1/2)=0$, based on the second part of our lemma, what we have to prove is that $\frac{h''}{H''}$ is an increasing function (we considered $G=-H', g=-h'$ for the second part of the lemma). And clearly, $$\begin{align}\frac{h''}{H''}(p)&=(1-2r)^2\frac{\frac{1}{(r+p-2rp)(1-r-p+2p)}}{\frac{1}{p(1-p)}} =(1-2r)^2\frac{1-(2p-1)^2}{1-(2r-1)^2(2p-1)^2}\\ &=1+\frac{(2r-1)^2-1}{1-(2r-1)^2(1-2p)^2} =1-\frac{4r(1-r)}{1-(2r-1)^2(1-2p)^2} \end{align}$$ is an increasing function $[0,1/2]$ as long as $ r \in [0,1]$. $\square$.

$\endgroup$
2
  • $\begingroup$ Good, thank you! Two comments: 1) Is it true that inequality becomes equality iff $\beta_1=\beta_2=\beta$? I think that this is true because of strict convexity. 2) I think some is wrong with denominators after "Thus" $\endgroup$ Jun 7, 2021 at 20:07
  • $\begingroup$ Thank you. I corrected it. For your question, I think it is true as long as $r \ne 1/2$, because in this case you will have the strict monotonicity of$h’/H’$ which leads to the strict convexity. The works seems to be obvious but surely we have to recheck it $\endgroup$ Jun 7, 2021 at 20:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .