Thursday, December 29, 2016

probability - How many random samples needed to pick all elements of set?





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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...