Take the 2-minute tour ×
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.

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|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
add comment

1 Answer

up vote 2 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|improve this answer
add comment

Your Answer

 
discard

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.