Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
What did you try? What similar problems do you know and how do you attack those? – Did Jan 18 '12 at 16:49
up vote 3 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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