6
$\begingroup$

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.

$\endgroup$

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
7
$\begingroup$

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

$\endgroup$
  • $\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.