2
$\begingroup$

Consider a multiset $S=\{a_1,a_2,...,a_{2n}\}$ of natural numbers. There are $2n$ elements (not necessarily unique since $S$ is a multiset) in $S$. All elements of $S$ belong to a set of natural numbers $R$ with size $N$ (i.e |R|=N). The probability that a number $i$ is in the multiset $S$ is $P_i$. Each element $a_i$ is independent identically distributed over the set $R$. Now let's consider a matrix with $n$ columns and arbitrary number of rows. If we want to put all elements of $S$ in the matrix in such a way that no same elements are on the same row, how many average number of rows do we need?

For example if all $2n$ elements of the multiset are unique, we need 2 rows to fit all elements in the matrix and if all $2n$ elements are same, we need $2n$ rows.

[note: I asked this question on mathstack exchange but did not get any answer]

$\endgroup$
  • $\begingroup$ Your answer can't be determined without knowing a good deal more about the distribution. For example, suppose $S=(a_1, a_2, \ldots , a_{2n})$, and suppose these are selected so that $a_1$ is distributed over $R$ somehow and then the other elements are fixed so that $a_1 = a_2 = a_3 = \cdots = a_{2n}$. Then all the elements are equal with probability 1. [Or we could put some other distribution on $S$] Could you be more specific? $\endgroup$ – Pat Devlin Dec 3 '16 at 19:49
  • $\begingroup$ Multiset $S$ is being created by choosing numbers from $R$, $2n$ times with replacement. So, $\sum_{\forall{i\in R}}{P_i}=1$. A number $i$ is either present in the multiset or not. Considering binomial distribution probability of having a number $i$, $k$ times in $S$ is $\binom{2n}{k}(P_i^k)(1-P_i)^{2n-k}$. This is my approach. $\endgroup$ – marcella Dec 3 '16 at 20:45
  • $\begingroup$ So each element $a_i$ is independent identically distributed over a set $R$. I would include that in the original post. $\endgroup$ – Pat Devlin Dec 3 '16 at 20:46
  • $\begingroup$ Yes, you are correct. I will include that right now. $\endgroup$ – marcella Dec 3 '16 at 20:47
2
$\begingroup$

You are selecting iid random variables $a_1, \ldots, a_{2n}$ from some distribution. And you want to estimate how often the most common value appears.

Let $p_{0}$ be the highest probability. If this is much larger than the rest of the values, then $p_{0} 2n$ is a good estimate (always a lower bound for what you want). If all the values are about equal, then perhaps about $p_{0} 2n \log(1/p_{0})$ or so.

$\endgroup$
  • $\begingroup$ Is there a proof? $\endgroup$ – marcella Dec 3 '16 at 20:57
  • $\begingroup$ Well $2n p_0$ is simply the expected number of symbols of type corresponding to $p_0$. The other calculation you could find in a lot of probability books. You want to assume say the thing is uniform over $R$ and see what the answer is (bound each tail probability by something like Chernoff and see what a union bound says). [could have a typo in that second bound; didn't think too hard] If you want tighter control, try a second moment calculation. If you want even tighter control, you have options. $\endgroup$ – Pat Devlin Dec 3 '16 at 21:01

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.