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

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.