Monday, 19 March 2018

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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...