# $H(p) \le H(q) + KL(p, q)$?

Let $$H(p) = \sum_i p_i\log\frac{1}{p_i}$$ be the entropy of $$p$$ and $$KL(p, q) = \sum_i p_i\log\frac{p_i}{q_i}$$ be the KL divergence between $$p$$ and $$q$$. Does it hold that $$H(p) \le H(q) + KL(p, q)$$?

If this is not true, can we bound $$H(p)$$ using $$H(q)$$ and $$KL(p, q)$$ in certain form?

Edit 1: The motivation of this problem is this. Suppose that we are a bunch of data points as features (say $$\{x_1, \dots, x_m\}$$). And we have different distributions of labels over them. Say the first distribution is $$q$$. We use $$q$$ for training, and somehow we achieved Bayes optimal classifier. The loss of this classifier is $$H(q)$$.

Now say the second distribution is $$p$$. We know that the Bayesian optimal classifier over $$p$$ achieves loss $$H(p)$$.

Now I want to capture what is the difference between these two optimal classifiers over $$p$$ and $$q$$? There are two natural ways to capture this:

1. $$H(p) - H(q)$$. This simply measures the absolute performance difference (namely if Bayes optimal classifier over $$q$$ is doing well, would the Bayes optimal classifier over $$p$$, possibly different though, also doing well). This boils down to exactly measure the difference of entropy of $$p$$ and $$q$$.

2. $$KL(p, q)$$. This arises if we apply cross entropy to $$p$$ and $$q$$, $$\ell(p, q) = H(p) + KL(p, q)$$. Which is about what happens if we actually use $$q$$ to predict $$p$$. In this case $$KL(p, q)$$ captures the divergence.

I basically want to ask if these 2 are related.

• Are you sure you want to write you inequality with $\mathit{KL}(p, q)$, not $\mathit{KL}(q, p)$? In information theory, $H(q) + \mathit{KL}(q, p)$ has a nice meaning (it is the cost to describe $q$ when using a description method optimized for $p$); while, as far as I know, $H(q) + \mathit{KL}(p, q)$ does not mean anything interesting… Dec 30 '19 at 15:11
• A similar question (with answer in continuous and discrete cases) appears here. Dec 30 '19 at 15:14
• @RémiPeyre: Replied with motivations on my side. Dec 31 '19 at 17:00

There are already nice negative answers by Steve and Rémi Peyre. In the comments, user111 mentioned this post by David Reeb who gives a bound on the difference of entropies in terms of the KL-divergence when $$p$$ and $$q$$ are probability distributions on a finite set. I want to mention two other such bounds.

Suppose that $$p$$ and $$q$$ are distributions on a finite set $$X$$. Let \begin{align} \|p-q\| &:= \frac{1}{2}\sum_{i\in X}|p_i-q_i|=\sup_{A\subseteq X}\big|p(A)-q(A)\big| \end{align} be the total variation distance between $$p$$ and $$q$$.

Bound 1: \begin{align} \big|H(p)-H(q)\big| &\leq \sqrt{2 KL(p,q)}\,\log\left[\frac{|X|}{\sqrt{2 KL(p,q)}}\right] \;, \end{align} provided that $$\|p-q\|\leq\frac{1}{4}$$.

Bound 2: \begin{align} \big|H(p)-H(q)\big| &\leq H\left(\sqrt{\frac{1}{2}KL(p,q)}\right) + \sqrt{\frac{1}{2}KL(p,q)}\log(|X|-1) \;, \end{align} provided that $$\|p-q\|\leq\frac{1}{2}$$, where $$H(\cdot)$$ on the right-hand side is the binary entropy function.

Both are based on Pinsker's inequality (Lemma 11.6.1 of the book of Cover and Thomas, 2nd edition), \begin{align} \|p-q\| &\leq \sqrt{\frac{1}{2}KL(p,q)} \;. \end{align} For Bound 1, we use Theorem 17.3.3 of Cover and Thomas, which gives the bound \begin{align} \big|H(p)-H(q)\big| &\leq 2\|p-q\|\log\frac{|X|}{2\|p-q\|} \end{align} when $$\|p-q\|\leq\frac{1}{4}$$. For Bound 2, we instead use the bound \begin{align} \big|H(p)-H(q)\big| &\leq H(\|p-q\|) + \|p-q\|\log(|X|-1) \end{align} discussed in this post, which is valid when $$\|p-q\|\leq\frac{1}{2}$$.

I believe that Bound 2 is the sharpest of all three.

Just a partial answer, but the proposed inequality doesn't hold.

Take $$p = [0.2, 0.8], q = [0.1, 0.9]$$.

Then $$H(p) = 0.2 \log(5) + 0.8 \log(1/0.8) \approx 0.5$$,

$$H(q) = 0.1 \log(10) + 0.9 \log(1/0.9) \approx 0.33$$

and $$KL(p, q) = 0.2 \log(2) + 0.8 \log(0.8/0.9) \approx 0.04$$.

No, there is no hope of getting something of this kind. Consider the probability distribution $$p$$ on $$\mathbf{N} \setminus \{0, 1\}$$ defined by $$p(n) := Z_p^{-1} n^{-1} \log^{-3/2} n$$; and likewise $$q(n) := Z_q^{-1} n^{-1} \log^{-3} n$$. Then $$H(p) = \infty$$, but $$H(q)$$, $$\mathit{KL}(p, q)$$ and $$\mathit{KL}(q, p)$$ all are finite…