# Entropy inequality

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?

• I put in some dollar signs and TeX commands for the inequalities. – theHigherGeometer Apr 10 '15 at 16:41
• Hint: Consider $P(b) = 1$ where $b = \mathrm{arg}\max_{a \in A} \log Q(a)$. – cardinal Apr 10 '15 at 17:22
• @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$. – carnivorous mushroom Apr 10 '15 at 20:14

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