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]

Improve this question
$\endgroup$
4
  • $\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
    Commented Dec 3, 2016 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
    Commented Dec 3, 2016 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
    Commented Dec 3, 2016 at 20:46
  • $\begingroup$ Yes, you are correct. I will include that right now. $\endgroup$
    – marcella
    Commented Dec 3, 2016 at 20:47

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is there a proof? $\endgroup$
    – marcella
    Commented Dec 3, 2016 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
    Commented Dec 3, 2016 at 21:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .