3
$\begingroup$

I have a multiset $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$?

$\endgroup$
  • $\begingroup$ Can you say more about what it means to "fix" $q$? As I read the problem, $q$ must be of the form $s/n^2$, where $s$ is the sum of squares of positive numbers which (unsquared) add up to $n$, i.e., $s=m_1^2+\cdots+m_{|B|}^2$ where $m_i\ge1$ and $m_1+\cdots+m_{|B|}=n$. (Each $m$ counts the "multiplicity" of the distinct $a$'s.) $\endgroup$ – Barry Cipra Apr 10 '14 at 14:19
  • $\begingroup$ @BarryCipra Right. Sorry for any confusion. I just meant that the answer should be a function of $q$ and $n$. $\endgroup$ – octonots Apr 10 '14 at 14:26
  • $\begingroup$ octonots, thanks for the reply. My main point is that the possible values for $q$ depend rather strongly on $n$. If $n=4$, for example, the allowed values are $q=1/4$, $3/8$, $1/2$, $5/8$, and $1$. Have you worked out some small examples? $\endgroup$ – Barry Cipra Apr 10 '14 at 15:03
  • $\begingroup$ @BarryCipra Yes. The idea is that there is some $A$ but it is hidden and the only thing you know about it is $n$ and $q$. I know that the number of distinct integers in $A$ is at least $1/q$. I haven't worked out the minimum of $-\sum_{b \in B} p_b \ln{p_b}$ for small $n$ as I am not sure what the extreme cases are. $\endgroup$ – octonots Apr 10 '14 at 15:18
2
+50
$\begingroup$

Just to make contact with wikipedia, I'll note that $S=-\sum p_b \ln p_b$ is the entropy and $q$ is the Simpson index. As other people have noted, there's some trickiness with there being only certain allowed $(n,q)$ pairs, so to avoid this let's assume that $n$ is large and $q$ is not too close to 0 or 1.

To maximize the entropy, you want to spread out the distribution as much as possible, without having the Simpson index fall below $q$. The distribution that does this has $p_1 \approx \sqrt{q}$, $p_i=1/n$ for $i=2,\ldots,\sim n(1-\sqrt{q})$. (Obviously, for finite $n$, $p_1$ will have to be slightly smaller than $\sqrt{q}$.) This gives $S\sim (1-\sqrt{q})\ln n$.

To minimize the entropy, you want to concentrate the distribution as much as possible, without having the Simpson index go above $q$. To do this, let $|B|=\lceil 1/q\rceil$, and have $p_1, \ldots, p_{\lfloor 1/q \rfloor}$ close to $q$, with $p_{\lceil 1/q\rceil}$ getting the small remainder of the probability. This gives $S\sim -\ln q$.

Note that this also works the other way -- given $n$ and $S$, these same distributions give the maximum and minimum possible values of $q$.

$\endgroup$
  • $\begingroup$ That's very nice. Is it possible to argue the other way as well. That is if you are given the entropy and $n$, is there a range of possible values the Simpson index can take? $\endgroup$ – octonots Apr 19 '14 at 20:36
  • $\begingroup$ Yup, using the same distributions. I added this to the answer. $\endgroup$ – Daniel Weissman Apr 19 '14 at 22:34
0
$\begingroup$

A beginning:

In the first place a set $B:=[m]$ is given, and for each $k\in B$ we have a multiplicity $f(k)\in{\mathbb N}_{\geq1}$. The pair $(B,f)$ constitutes the multiset $A$ in your question.

Put $\sum_{k=1}^m f(k)=:n$. Then the probability that you choose the value $k$ when picking a random element from $A$ is ${f(k)\over n}=:p_k$, and the probability $q$ that you choose two equal values in two independent choices is given by $$q={1\over n^2}\sum_{k=1}^m f^2(k)=\sum_{k=1}^m p_k^2\ .$$ It follows that we have to maximize/minimize the function $$H(p):=-\sum_{k=1}^m p_k\>\log p_k$$ under the constraints $$p_k\geq0,\quad \sum_{k=1}^m p_k=1,\quad \sum_{k=1}^m p_k^2=q\ .$$ Consider this as a continuous optimization problem. Depending on the value of $q$, the sphere $\sum_k p_k^2=q$ may intersect the simplex $p_k\geq0$, $\>\sum_k p_k=1$ in a complicated way, and setting up a simple Lagrange multiplier scheme does not sufficiently take care of the global situation, so much the more as it will lead to transcendental equations. But it seems that the following Lemma is true: When $H$ is extremal at an admissible ${\bf p}$ then we cannot have three values $p_1>p_2>p_3>0$. This is corroborated by the follwing figure which shows the level lines of $H$ on a subsimplex $p_1+p_2+p_3=s$ for $s=0.4$ and in red a curve $p_1^2+p_2^2+p_3^2={\rm const.}\ $. One can see that the red curve is tangent to the level lines of $H$ only in points where two of the $p_k$ are equal.

enter image description here

Therefore one would have to do the following: For all possible choices of $m_1\geq0$, $m_2\geq0$ with $m_1+m_2\leq m$ solve $$m_1p_1+m_2p_2=1,\qquad m_1p_1^2+m_2p_2^2=q$$ for $p_1$ and $p_2$. When an admissible solution exists compute the corresponding $$H({\bf p})=-m_1\> p_1\log p_1-m_2\>p_2\log p_2\ .$$ The smallest and the largest values found in this way are the extremal values of $H$ under the given constraint.

$\endgroup$
  • $\begingroup$ Thank you for clarifying the question. Do you mean you have to know $m$ as well as $q$ to be able to solve the problem? $\endgroup$ – octonots Apr 13 '14 at 18:15
  • $\begingroup$ The quantities $m$ and $n$ are the only parameters of this problem. It may be that in the end you obtain a bound which is independent of $m$. $\endgroup$ – Christian Blatter Apr 13 '14 at 18:32
  • $\begingroup$ Another way of putting this is that $\sum_{k \in B} f(k) = n$ and $\sum_{k \in B} f(k)^2 = n^2 q$. And it seems that we want to minimize $\sum_{k \in B} f(k)(\log{n}-\log{f(k)})$. If we just take $q=1/2$ and $n=100$, say, I still can't see how to do this. $\endgroup$ – octonots Apr 13 '14 at 19:25

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.