Let $$h(p) = -p\log_2(p) - (1-p)\log_2(1-p)$$ be the binary entropy function and $$H(p,q) = -p\log_2(p) -q\log_2(q) - (1-p-q)\log_2(1-p-q)$$ be the "ternary" entropy function. I would like to prove that for all possible values of $p \in [0,1/2]$ and $q \in [0,1/2]$, $$H(p,q) \leq h\bigg(\frac{1-p}{2}\bigg)+h\bigg(\frac{1-q}{2}\bigg).$$ Any help will be appreciated !


Let's write entropy in the standard form $H(p_1,..,p_n) = - \sum_i p_i\log_2(p_i)$ with $\sum_i p_i = 1$. We can make use of the sub-additivity of entropy (see e.g. here) to write

$$ H(a,1-a) + H(b,1-b) \geq H(0,a,b,1-a-b) $$ Further, $H(0,a,b,1-a-b) = H(a,b,1-a-b)$. Now set $a = (1-p)/2$ and $b = (1-q)/2$. So it suffices to show

$$ D(p,q) = H((1-p)/2, (1-q)/2, 1-(1-p)/2 - (1-q)/2)- H(p,q,1-p-q) \geq 0 $$

Now $D$ has one unique minimum since the two equations $d D / dp = 0$ and $d D / dq = 0$ have only one solution at $p=q=1/3$ with $D(1/3,1/3) = 0$, and since $D>0$ on the boundaries of the required area $[p=0, p=1/2, q = 0, q = 1/2]$.


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.