4
$\begingroup$

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?

  • 0
    What did you try? What similar problems do you know and how do you attack those?2012-01-18

1 Answers 1

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$.