# Probability of non-empty bins after randomly inserting balls by pairs

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?

-
What did you try? What similar problems do you know and how do you attack those? – Did Jan 18 '12 at 16:49

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