Given $n$ bins, at each step we choose uniformly two of them (distinct) and insert a ball to both. After $k$ steps, what is the probability that all of the bins are non-empty?
Probability of non-empty bins after randomly inserting balls by pairs
4
$\begingroup$
probability
combinatorics
-
0What did you try? What similar problems do you know and how do you attack those? – 2012-01-18
1 Answers
3
This is the coupon-collector's problem with the twist that instead of acquiring one distinct coupon at a time we're acquiring two. The analysis is almost the same as for the standard coupon-collector's problem. In fact, the general case for acquiring $r$ distinct coupons at a time is of equal difficulty, so let's do that.
The probability that none of $i$ specific bins has a ball in it after $k$ steps when placing balls into $r$ distinct bins at a time is $\frac{\dbinom{n-i}{r}^k}{\dbinom{n}{r}^k}.$ By inclusion-exclusion, then, the probability that each of the $n$ bins has at least one ball in it after $k$ steps is $\sum_{i=0}^n \frac{(-1)^i \dbinom{n}{i} \dbinom{n-i}{r}^k }{\dbinom{n}{r}^k}.$
Of course, you want the case $r=2$.