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.
Answer
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.$$
No comments:
Post a Comment