# How to minimize $-\sum p_b \ln{p_b}$?

Consider multisets of the form $A = \{a_1,\dots,a_n\}$ of integers. Let $q = P(a_i = a_j)$ when $i$ and $j$ are chosen independently and uniformly from $\{1,\dots, n\}$. Let $B$ be the set of integers in $A$. We know that $|B| \leq n$. Finally let $p_b = P(a_i = b)$ when $i$ is chosen uniformly from $\{1,\dots, n\}$.

How small can $-\sum_{b \in B} p_b \ln{p_b}$ be as a function of $q$ and $n$?

In this setup we can vary $A$ as long as we maintain the constraints that $q = P(a_i = a_j)$ and the size of $A$ is $n$.

We can immediately infer that $|B| \geq 1/q$ . If $n = 100$ and $q=1/2$, say, it seems that $|B|$ can be as large as $20$. I imagine an exact answer may be hard to get so I would be happy with an estimate or bound.

• Not sure this is really the stuff of MathOverflow rather than math.stackexchange, but thanks for giving the link. – Tom Leinster Apr 14 '14 at 17:58

First note that $q = \sum_b p_b^2$. We're going to use an instance of the AM-GM inequality: $$\sum_b p_b\cdot p_b \geq \prod_b p_b^{p_b}.$$ This gives $$-\sum_b p_b \log p_b = \log \Bigl( \prod_b p_b^{-p_b} \Bigr) \geq \log \Bigl( 1\Big/\sum_b p_b^2\Bigr) = -\log q.$$ This gives a lower bound.
Equality holds iff all the $p_b$s are equal. So, for a given $n$ and $q$, we can achieve this lower bound if and only if we can choose $A$ and $B$ in such a way that all $p_b$ are equal. Now if all the $p_b$ are equal then for each $b$, we have $q = |B| p_b^2$ and so $p_b = \sqrt{q/|B|}$. On the other hand, for each $b$, $$p_b = \frac{1}{n} \cdot \bigl|\{ i : a_i = b\}\bigr|,$$ so $n p_b$ must be an integer. So if we're to achieve this minimum then $n\sqrt{q/|B|}$ must be an integer. Obviously this won't often be achievable for given $n$ and $q$. But I imagine it's the case that when $n$ is large, you can come close to this lower bound by a suitable choice of $A$ and $B$.
Incidentally, nothing about this question requires $A$ to be a multiset of integers. The elements of $A$ could be anything.
• Thank you! Under what conditions would $-\sum_{b \in B} p_b \ln{p_b}$ be maximized in this case? – octonots Apr 14 '14 at 18:24
• If you ignore the $q$ constraint, you end up maximizing the entropy on a distribution on $n$ objects. This is maximized with a uniform distribution and a value of $-\sum p_b\log(p_b) =\log(n)$. Adding the $q$ constraint back in, the value can only get smaller. You can also construct explicit examples for a fixed value of $q$ and sufficiently large $n$ that achieve $O(\log(n))$. So the maximum is $\Theta(\log(n))$ for fixed $q$ as $n$ grows. – Bill Bradley Apr 14 '14 at 20:18
• @BillBradley To make this explicit and aid my understanding, let's say $q= 1/\sqrt{n}$. What is the maximum in that case? – octonots Apr 14 '14 at 20:22
• The construction I had in mind gives a value of $(1−\sqrt{q})\log(n)$. That is optimal from a "big O notation" perspective for fixed $q$, but maybe one could improve the constant. For $q=1/\sqrt{n}$, that would of course give a value of $2(1−\sqrt{q})\log(q)$. – Bill Bradley Apr 14 '14 at 20:42