The coupon collector is a famous problem in probability theorem.
It is explain well here (Wikipedia): Cupon collector's roblem
The estimated number of coupons for catching them all is $nlog(n)$.
My question is what is the probability to fail?
If I draw $nlog(n)$ coupons, what is the probability I didn't get them all?
In more general, for a certain $m$ what is the probability not to get all $n$ coupons (on uniform distribution)?
I am curious specifically on $nlog^2n$ tries, but a general calculation is always the best.
Thansk all!
When you draw $k$ coupons the chance you are missing a specific one is $(1-\frac 1n)^k\approx e^{-k/n}$. The approximation is based on $(1-\frac 1n)^n \approx e$, which is valid when $n$ is reasonably large. If $e^{-k/n}$ is well smaller than $1$ the chance you are missing two is smaller yet. The chance that you are missing any one is then about $ne^{-k/n}$. If $e^{-k/n}$ is not so small, you need to use inclusion-exclusion because you could be missing two or three.