Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

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

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

share|cite|improve this answer
Thanks, this is exactly what I was looking for. – user59475 Jan 24 '13 at 10:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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