This question already has an answer here:

If repeatedly picking a random element from a set, what is the expected number of times I'd have to pick before seeing all the elements of the set?

Edit: when picking an element, it is simply counted and not removed from the set, so it can be picked again.


marked as duplicate by joriki, Shailesh, Daniel W. Farlow, Claude Leibovici, M. Vinay Jun 18 '16 at 4:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ If you can see only by picking the elements, shouldn't the expected number be the carnality of the set? $\endgroup$ – user123454321 Jan 24 '13 at 9:33
  • $\begingroup$ (Assuming you meant cardinality). No, I forgot to mention that the elements are not removed from the set when picked, they are only counted. $\endgroup$ – user59475 Jan 24 '13 at 9:41
  • $\begingroup$ Yeah that was a typo. Is the set finite? $\endgroup$ – user123454321 Jan 24 '13 at 9:50
  • $\begingroup$ I assume that you are talking about finite sets, right? Is there a particular distribution to how "random" works? $\endgroup$ – Asaf Karagila Jan 24 '13 at 9:50
  • $\begingroup$ I guess for infinite sets the answer is trivial unless you don't distinguish infinite cardinalities. $\endgroup$ – user123454321 Jan 24 '13 at 9:51

This is the coupon collector's problem. The expected number of picks required to choose all the elements of the set is $$nH_n = n\sum_{i=1}^n\frac1i.$$

  • $\begingroup$ Thanks, this is exactly what I was looking for. $\endgroup$ – user59475 Jan 24 '13 at 10:07

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