The following [coupons collector problem][1]
[1]: https://en.wikipedia.org/wiki/Coupon_collector%27s_problem is well-known problem.
My question is about this problem. Let $X$, as described in the problem, be the random variable which counts the number of cereal boxes that have been collected untill all different types of coupons (n different types) have been collected for the first time.
Assume $c>0$ a real positive number. I am trying to prove the following inequallity:
$$ \mathbb{P}\left(X>\left\lceil cn+n\log n\right\rceil \right)\leq e^{-c} $$
Here's what I have tried:
First thing I tried was to use Markov inequality, but Markov gave me too big upper bound so that didnt really get me anywhere.
Second thing I tried, was to denote by $A_j$ the event where coupon number $j$ was not found in the first $ \left\lceil cn+n\log n\right\rceil $ boxes of cereal.
Now, one can notice that $ \mathbb{P}\left(X>\left\lceil cn+n\log n\right\rceil \right)=\mathbb{P}\left(A_{1}\cup…\cup A_{n}\right)$,
since $X>\left\lceil cn+n\log n\right\rceil $ if and only if there exists at least one type of coupon that we havent collected yet in the first $ \left\lceil cn+n\log n\right\rceil $ boxes.
Now, I tried to use Bool's inequallity to deduce:
$ \mathbb{P}\left(X>\left\lceil cn+n\log n\right\rceil \right)=\mathbb{P}\left(A_{1}\cup…\cup A_{n}\right)\leq\sum_{i=1}^{n}\mathbb{P}\left(A_{i}\right) $
And I proved that $ \mathbb{P}\left(A_{i}\right)=\left(\frac{n-1}{n}\right)^{\left\lceil cn+n\log n\right\rceil }\leq e^{-c}$, but I could not prove that $ \mathbb{P}\left(A_{i}\right)=\left(\frac{n-1}{n}\right)^{\left\lceil cn+n\log n\right\rceil }\leq ne^{-c} $ which is what I need to prove the inequality (also it is not true for any $c$ as I checked in graphing calculator).
Any help would be appreciated. Thanks in advance.
Best Answer
Your approach seems very close. You should have $$ \mathbb{P}(A_i) \leq \left( 1 - \frac{1}{n} \right)^{cn + n \log n} \leq e^{-(cn + n \log n)/n} = \frac{1}{n} e^{-c} , $$ using the inequality $1 - x \leq e^{-x}$ for all $x$. Combining with your union bound leads to your desired result.