Take the 2-minute tour ×
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.

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|improve this question
    
If you can see only by picking the elements, shouldn't the expected number be the carnality of the set? –  GYC 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? –  GYC 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. –  GYC Jan 24 '13 at 9:51

1 Answer 1

up vote 6 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|improve this answer
    
Thanks, this is exactly what I was looking for. –  user59475 Jan 24 '13 at 10:07

Your Answer

 
discard

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.