A jar has 50 balls 1 to 50 each one having distinct number written on it. Bob, owner of the jar,each day he takes out one ball out of the jar randomly ( with equal probability) and put it back.

Q1. How many days on average will it take until all 50 balls are taken out? (Note that the same ball can be picked on more than one days)

Q2. Assume that 3 months after Bob started this activity, how many distinct balls will have been taken out by Bob?

  • $\begingroup$ The answer to Q2 is not a number. What is your homework really asking? The expected number of distinct balls drawn by Bob in three months? And does three months mean 90 days or 91 days or 92 days? $\endgroup$ – Dilip Sarwate Jan 13 '14 at 13:02

Q1 is known on Wikipedia as the Coupon collector's problem

This is a Geometric distribution with variable rate. It can be considered as a sequence of independent processes with stepped rate, i.e. with the rate constant changing only after each 'unique' ball is drawn.

Q1. When K balls are known, the rate of discovery of "new" balls with replacement is rate=(N-K)/N and the expected time to a "new ball" event is 1/rate = N/(N-K).

We need to set N=50 and sum the expected times from K=0..(N-1)

Expected time to complete = 50/50 + 50/49 + 50/48 + ... + 50/1

In python this is: sum([50.0/(k+0.0) for k in range(1,51)])

I get ~ 224.96

As for Q2, I would suggest Monte Carlo simulation.


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.