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.


Also asked at <https://math.stackexchange.com/questions/748304/how-minimize-sum-p-b-lnp-b> .



How to minimize $-\sum p_b \ln{p_b}$?
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. 


