3
$\begingroup$

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 .

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

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.

$\endgroup$
  • $\begingroup$ Thank you! Under what conditions would $-\sum_{b \in B} p_b \ln{p_b}$ be maximized in this case? $\endgroup$ – octonots Apr 14 '14 at 18:24
  • $\begingroup$ 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. $\endgroup$ – Bill Bradley Apr 14 '14 at 20:18
  • $\begingroup$ @BillBradley To make this explicit and aid my understanding, let's say $q= 1/\sqrt{n}$. What is the maximum in that case? $\endgroup$ – octonots Apr 14 '14 at 20:22
  • $\begingroup$ 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)$. $\endgroup$ – Bill Bradley Apr 14 '14 at 20:42

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.