Suppose that I have $N$ distinct objects, each of which have $1/N$ chance of being drawn. What is the expected number of draws, $D$, to draw at least $x$ of each object (with replacement)? For example: there are 30 object. What is the expected number of draws I would need to get at least 1 of each object?

For the record, this isn't a homework question or anything, but just something I was thinking about randomly as I was playing a game. What kind of distribution is the above?

  • $\begingroup$ The expected number of draws to get at least once each object is $\frac1N+\frac1{N-1}+\cdots+\frac12+1$, as shown here. The distribution of the number of draws can be deduced from the same approach. $\endgroup$
    – Did
    Mar 14 '15 at 13:22
  • 1
    $\begingroup$ This is an example of the coupon collecting problem (assuming all coupons are equally likely). $\endgroup$
    – BruceET
    Mar 15 '15 at 23:53

Your Answer

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

Browse other questions tagged or ask your own question.