0
$\begingroup$

There are n balls in a pool. Pick up one ball each time and then put it back to the pool. Do it k times, where k > n. What’s the probability that all balls have been picked up?

$\endgroup$
7
  • $\begingroup$ Do you have some thoughts on how to tackle this problem? $\endgroup$
    – hardmath
    Jan 10, 2016 at 14:36
  • 2
    $\begingroup$ This is often referred to as the coupon collector's problem. $\endgroup$
    – Marcus M
    Jan 10, 2016 at 14:37
  • $\begingroup$ @MarcusM Cool, thx! Is there any book collecting most popular problems on probability theory? $\endgroup$
    – lu yuan
    Jan 10, 2016 at 14:54
  • $\begingroup$ @hardmath thx, I will check it $\endgroup$
    – lu yuan
    Jan 10, 2016 at 14:55
  • $\begingroup$ Sorry, I've changed my mind. The other problem is sampling without replacement, while your problem is sampling with replacement. $\endgroup$
    – hardmath
    Jan 10, 2016 at 15:01

1 Answer 1

2
$\begingroup$

This is an occupancy problem.

You can find an expression by inclusion-exclusion, but a simpler expression comes from Stirling numbers of the second kind, and the probability is $$\dfrac{S_2(k,n) \,n!}{n^k}$$ where the numeration is the number of equally probable draw patterns where each ball is picked at least once while the denominator is the total possible number of equally probable draw patterns.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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