Let $\mu,\nu$ be two distributions on the same discrete space. Is it true that

$$\mathrm{H}\left(\frac{\mu+\nu}{2}\right) \ge \mathbb{E}_{xy}-\log\left(\frac{\sqrt{\mu(x)\nu(y)}}{2} + \frac{\langle\mu, \nu\rangle}{2}\right)$$

where $x\sim\mu$ and $y\sim\nu$ independently. Here $\mathrm{H}(\rho) = -\sum_{z}\rho(z)\log\rho(z)$ is the Shannon's entropy function and $\langle\mu,\nu\rangle =\sum_z{\mu(z)\nu(z)}$.

Note that if $\langle\mu,\nu\rangle = 0$, then both LHS and RHS are $\frac{\mathrm{H}(\mu)+\mathrm{H}(\nu)}{2}+1$, so the inequality holds true.

On the other extreme, if $\mu = \nu$, then by convexity of $z\mapsto-\log z$, we have $$\frac{1}{2}\mathrm{H}(\mu) + \frac{1}{2}\mathrm{H}_2(\mu) \ge \mathrm{RHS}$$ where $H_2$ is the second order Renyi entropy which is never bigger than the Shannon entropy. Since LHS is $\mathrm{H}(\mu)$ in this case, this shows the inequality is again true.

I can also verify the inequality when $\mu,\nu$ are flat distributions.

I wonder if this holds true for all $\mu, \nu$.


Unfortunately, this is not true in general. Let $\mu=(x,1-x)$ for $x\in[0,1]$ and let $\nu=(1,0)$.

Now LHS is certainly at most 1 (assume the logarithms are to the base 2), however, the maximum of RHS over $x$ is bigger than one as can be see here.

  • $\begingroup$ you can accept your own answer $\endgroup$ – kodlu Jun 20 '17 at 11:22
  • $\begingroup$ Thanks, will do so in 24 hours (site restriction that applies to me) $\endgroup$ – boinkboink Jun 20 '17 at 11:27

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.