Probability not to get a coupon : Coupon Collector's Problem

536 Views Asked by At

We buy coupons for $m$ rounds (no matter if we have already collected them all or not and we buy one coupon each round). What is the probability that we will not get the coupon number 1 in any of the $m$ rounds?

Assume we have the Coupon Collector's Problem with $1 \dots n$ Coupons.

Assume the event $X_1 = \text{"We don't get the first coupon"}$ so i think $X_1 \sim Bernoulli(1 - \frac{1}{n})$. And after $m$ rounds we have the probability of $(1 - \frac{1}{n})^m$ to get not the first coupon - right ? And with the bernoulli's inequality we get $(1 - \frac{1}{n})^m \geq 1 - \frac{m}{n} $.

How can I calculate the expected value of the number of coupons that have not yet been collected after $m = n \cdot ln(n) + t$ round ( with m is an integer) ? Is it $ E \geq m \cdot (1 - \frac{m}{n})$?

1

There are 1 best solutions below

0
On

It is correct that $\mathbb E[\text{# coupons not collected}]\ge n(1-m/n)$, but you can get a more precise estimate if you do not use Bernoulli's inequality.

The expected number of coupons not collected is $$ \mathbb E[\text{# coupons not collected}]=n\cdot P(X_1)=n\cdot (1-\tfrac1n)^{n\log n + t} $$ To get a good approximation for this, take $\log$s. $$ \log\Big(\mathbb E[\text{# coupons not collected}]\Big)=\log n+(n\log n+ t)\log(1-\tfrac1n) $$ Note that $\log(1-\frac1n)=-\frac1n+O(n^{-2})$. Therefore, this is $$ \log n + (n\log n +t)(-\tfrac1n+O(n^{-2}))=-t/n+O(\log n/n) $$ so the expected number of uncollected coupons is $$ \mathbb E[\text{# coupons not collected}]=e^{-t/n}\cdot e^{O(\log n/n)}=e^{-t/n}(1+O(\log n/n)). $$ In the last step, we use the fact that $e^x=1+O(x)$, as $x\to 0$.