1
$\begingroup$

Suppose that I know that a probability distribution with $n$ outcomes is very close to being uniform (that is: $\forall i,p_i=\frac{1}{n}$), and in particular for $n\epsilon\ll 1$ the distribution verifies $$\sum_{i=1}^n|\frac{1}{n}-p_i|=\epsilon$$ Now consider the Shannon entropy function: $$H(p_1,\ldots,p_n)=-\sum_{i=1}^np_i\log_2p_i$$ My question is: what are the probability distributions that, verifying the constraint, maximize and minimize the entropy? My guess is that $(\underbrace{\frac{1}{n},\ldots,\frac{1}{n}}_{n-2\text{ times}},\frac{1}{n}+\frac{\epsilon}{2},\frac{1}{n}-\frac{\epsilon}{2})$ minimizes the entropy and $(\underbrace{\frac{1}{n}-\frac{\epsilon}{n},\ldots,\frac{1}{n}-\frac{\epsilon}{n}}_{n/2\text{ times}},\underbrace{\frac{1}{n}+\frac{\epsilon}{n},\ldots,\frac{1}{n}+\frac{\epsilon}{n}}_{n/2\text{ times}})$ maximizes the entropy but I have not been able to prove any of them.

$\endgroup$
1
$\begingroup$

For the first, you have $H=-(n-2)\frac 1n \log_2 \frac 1n-(\frac 1n + \frac {\epsilon}2)\log_2 (\frac 1n + \frac {\epsilon}2)- (\frac 1n - \frac {\epsilon}2)\log_2 (\frac 1n - \frac {\epsilon}2) \\=-(n-2)\frac 1n \log_2 \frac 1n-(\frac 1n + \frac {\epsilon}2)[\log_2 \frac 1n +\log_2 (1+\frac {n\epsilon}2)]- (\frac 1n - \frac {\epsilon}2)[\log_2 \frac 1n - \log_2 (1-\frac {n\epsilon}2)] \\ \approx-\log_2\frac 1n-\frac {n\epsilon^2}{2 \ln 2}$

For the second you have $H=-\frac n2(\frac {1-\epsilon}n \log_2 \frac {1-\epsilon}n + \frac {1+\epsilon}n \log_2 \frac {1+\epsilon}n) \\=-\frac n2(\frac {1-\epsilon}n (\log_2 \frac 1n + \log_2(1-\epsilon)) + \frac {1+\epsilon}n (\log_2 \frac 1n + \log_2(1+\epsilon)) \\\approx-\log_2 \frac 1n-\frac {\epsilon^2}{2 \ln 2}$
So the second has lower change in entropy by a factor $n$

$\endgroup$
4
  • $\begingroup$ Thanks for your answer, so I see that in fact the first one is lower than the second one, but do you know if they maximize/minimize the entropy for all distributions verifying the constraint? $\endgroup$ – Euclean Jun 5 '13 at 17:42
  • 1
    $\begingroup$ @Euclean: I don't know, but suspect they do. $\endgroup$ – Ross Millikan Jun 5 '13 at 17:44
  • $\begingroup$ Yes, that's my guess, I suppose that it should be already proved somewhere. I won't accept the answer (provisionally) since I was looking mainly for the distributions that maximize/minimize the entropy $\endgroup$ – Euclean Jun 5 '13 at 17:50
  • $\begingroup$ I already figured out how to prove it. The first one goes by majorization and the second one by convexity of the entropy function. $\endgroup$ – Euclean Jun 6 '13 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.