6
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ 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$. $\endgroup$ Nov 10, 2019 at 22:15
  • $\begingroup$ @mathworker21 for $d=2$, I think I have an argument but this doesn't extend very well to higher $d$. $\endgroup$ Nov 11, 2019 at 17:36
  • $\begingroup$ what does "very well" mean? are you saying that it does extend to higher $d$? $\endgroup$ Nov 12, 2019 at 1:24
  • $\begingroup$ @mathworker21, I have added the argument for $d=2$ but it's not clear to me if it extends to all $d$. $\endgroup$ Nov 12, 2019 at 1:37
  • 1
    $\begingroup$ where in that argument did you use $d=2$? $\endgroup$ Nov 12, 2019 at 2:51

1 Answer 1

7
+50
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .