Entropy inequality

Question

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?

Answer 1

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.

Answer 2

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.