3
$\begingroup$

Let $P,Q$ be probabilities on a finite set $A$ with $Q(a)\gt 0$, for all $a\in A$, and let $H(P)$, $H(Q)$ denote their entropies and $D(P\,\|\,Q)$ denote their Kullback-Leibler distance.

Is it always true that

$$H(P)+D(P\,\|\,Q) \geq H(Q)?$$

This comes up in the theory of types where it is strongly suggested by some interpretations. However it reduces to

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} P(a)\log(Q(a))$$

which is not the "right" inequality which one usually runs into, namely

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} Q(a)\log(P(a))\qquad (\text{i.e. }D(Q\,\|\,P))\geq 0).$$

Nonetheless it may or may not be true. Have you seen it or can you prove or disprove it?

$\endgroup$
3
  • $\begingroup$ I put in some dollar signs and TeX commands for the inequalities. $\endgroup$ – theHigherGeometer Apr 10 '15 at 16:41
  • 2
    $\begingroup$ Hint: Consider $P(b) = 1$ where $b = \mathrm{arg}\max_{a \in A} \log Q(a)$. $\endgroup$ – cardinal Apr 10 '15 at 17:22
  • $\begingroup$ @cardinal: thanks, what the type theory really suggests is the inequality $H(P)+D(P||Q)\geq H(P)$, which is a trivial consequence of $D(P||Q)\geq0$. $\endgroup$ – carnivorous mushroom Apr 10 '15 at 20:14
2
$\begingroup$

The quantity $H(P)+D(P\,\|\, Q)$ is known as the cross entropy of $(P,Q)$, sometimes denoted by $H_c(P,Q)$. It holds that

$$ H_c(P,Q)\geq H(P)\;\text{ and } H_c(P,Q)\geq H_{\infty}(Q), $$

where $H_\infty$ is the min-entropy. The second inequality above is tight, by the example given above by cardinal. (The distribution $P$ deterministically chooses the maximum coordinate of $Q$)

Therefore, the inequality is not correct as stated, but becomes true if you relax Shannon entropy to min-entropy.

$\endgroup$
1
$\begingroup$

If you fix $P,$then the difference between the left and the right hand sides of your inequality is a convex function, so has a unique minimum, which, by Lagrange multipliers, is achieved when the function $\frac{Q(x)}{P(x)} - \log(Q(x)$ is a constant. You can presumably go from there.

$\endgroup$
1
  • 1
    $\begingroup$ Actually the hint of cardinal provides a trivial counterexample. I will have to check my intuition about types, it must obviously be wrong. $\endgroup$ – carnivorous mushroom Apr 10 '15 at 20:04

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.