# Inequality of difference of entropy

Suppose $$p$$ and $$q$$ are finite dimensional probability vectors of dimension $$d$$. Define also the uniform probability vector $$u$$ for which $$u_i = 1/d$$. The Shannon entropy for vector $$a$$ is defined as

$$S(a) = -\sum_i a_i\log a_i,$$

with $$0\log 0 = 0$$. The following inequality is a conjecture for $$\lambda\in [0, 1]$$ $$|S(p) - S(q)| \geq |S((1-\lambda) p + \lambda u) - S((1-\lambda) q + \lambda u)| \tag{1}$$

It seems intuitive to me - mixing with the uniform probability vector makes the entropy difference smaller since the state is closer to the uniform probability vector. I'm not sure how to prove this. I also could not find a numerical counterexample.

Can one prove (1) or find a counterexample?

Possibly useful facts

1) The Shannon entropy is concave so $$S(\alpha p + (1-\alpha)q) \geq \alpha S(p) + (1-\alpha)S(q)$$

2) Tha maximum value of the Shannon entropy is achieved by $$u$$. $$S(u) \geq S(a) \ \ \forall a$$ and $$S(u) = \log(d)$$

Argument for d=2

Let $$p' = (1-\lambda) p + \lambda u$$ and $$q' = (1-\lambda) q + \lambda u$$. Let us assume without loss of generality that $$S(p) \geq S(q)$$.

$$S(p') - S(p) = \int_0^\lambda \frac{dS((1-\lambda') p + \lambda' u)}{d\lambda'} d\lambda'$$

$$S(q') - S(q) = \int_0^\lambda \frac{dS((1-\lambda') q + \lambda' u)}{d\lambda'} d\lambda'$$

For fixed $$\lambda'$$, we have $$S((1-\lambda') p + \lambda' u) \geq S((1-\lambda') q + \lambda' u)$$ and since entropy is a concave function $$\frac{dS((1-\lambda') p + \lambda' u)}{d\lambda'} \leq \frac{dS((1-\lambda') q + \lambda' u)}{d\lambda'}$$.

Hence, we have $$S(p') - S(p) \leq S(q') - S(q)$$ or after rearranging

$$S(p) - S(q) \geq S(p') - S(q')$$

• This is nice. I haven't found any proof for it, but I wonder if there is a clean proof. Have you proven it for $d=2$? I coded, and it seems like the conjecture is true for $d=2$. Nov 10, 2019 at 22:15
• @mathworker21 for $d=2$, I think I have an argument but this doesn't extend very well to higher $d$. Nov 11, 2019 at 17:36
• what does "very well" mean? are you saying that it does extend to higher $d$? Nov 12, 2019 at 1:24
• @mathworker21, I have added the argument for $d=2$ but it's not clear to me if it extends to all $d$. Nov 12, 2019 at 1:37
• where in that argument did you use $d=2$? Nov 12, 2019 at 2:51

## 1 Answer

Consider $$\lambda = 0.01$$ and $$p = [0.6742, 0.2737, 0.0521],\ q = [0.6833, 0.2596, 0.0571]$$ Then $$S(p) - S(q) = 0.0005725$$. We have $$(1-\lambda) p + \lambda u = [0.6708, 0.2743, 0.0549], \ (1-\lambda) q + \lambda u = [0.6798, 0.2603, 0.0599]$$ and $$S((1-\lambda) p + \lambda u) - S((1-\lambda) q + \lambda u) = 0.0006494 > S(p)-S(q)$$ as desired.

More formally, let $$p,q$$ have the same entropy and $$d>2$$. Suppose the claim holds. Then, for any $$\lambda \in [0,1]$$ we must have $$S((1-\lambda) p + \lambda u) - S((1-\lambda) q + \lambda u) = 0$$ Consider the function $$f(\lambda) = S((1-\lambda) p + \lambda u)$$. For small $$\lambda$$, we have that $$f(\lambda) \approx f(0) + \lambda f'(0)$$. We compute \begin{align} f'(\lambda) &= - \frac{d}{d\lambda} \sum \Big((1-\lambda)a_i+\frac{\lambda}{d}\Big)\log\Big((1-\lambda)a_i+\frac{\lambda}{d}\Big) \\\\ &= -\sum \Big(\frac{1}{d}-a_i \Big)\log\Big((1-\lambda)a_i+\frac{\lambda}{d}\Big)+\Big(\frac{1}{d}-a_i \Big) \\\\ \implies f'(0) &= -S(p) - \frac{1}{d}\sum \log a_i \end{align} For $$p,q$$ distinct with the same entropy, we then have that for $$\lambda$$ small $$S((1-\lambda) p + \lambda u) - S((1-\lambda) q + \lambda u) \approx \frac{\lambda}{d} (- \sum \log a_i +\sum \log b_i)$$ Therefore, if $$\sum \log a_i \not= \sum \log b_i$$, we can find $$\lambda$$ small so that $$S((1-\lambda) p + \lambda u) - S((1-\lambda) q + \lambda u) \not=0$$. Note that such $$p,q$$ exist iff $$d>2$$. If $$d=2$$, then $$S(p) = S(q)$$ implies that $$p=q$$ modulo permutation of the indices.

• I get $0.000732647$ for the smoothed version (still works). It also works for $\lambda=0.5$ Nov 12, 2019 at 3:53
• @AkshatAgrawal do you mean "$d > 2$" when you say "$d > 3$" at the end of your answer? Nov 12, 2019 at 9:13
• you're right, fixed Nov 12, 2019 at 9:26