# Optimization of entropy for fixed distance to uniform

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.

## 1 Answer

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$

• 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? – Euclean Jun 5 '13 at 17:42
• @Euclean: I don't know, but suspect they do. – Ross Millikan Jun 5 '13 at 17:44
• 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 – Euclean Jun 5 '13 at 17:50
• I already figured out how to prove it. The first one goes by majorization and the second one by convexity of the entropy function. – Euclean Jun 6 '13 at 9:22