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 http://math.stackexchange.com/questions/748304/how-minimize-sum-p-b-lnp-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.

Also asked at https://math.stackexchange.com/questions/748304/how-minimize-sum-p-b-lnp-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 $p=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 http://math.stackexchange.com/questions/748304/how-minimize-sum-p-b-lnp-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.

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