Here is the problem I have:
Say that each box of cereal contains a prize. There are $n$ different prizes in all.
What is the probability that more than $t$ boxes are needed to find all $n$ gifts?
This is what I have worked out so far:
I know this is a variation on the coupon collector problem. I let $X$ be a random variable which is the number of boxes bought before all $n$ gifts are found. Finding $\Bbb E[X]$ is simple enough:
Let$$X=X_1+X_2+...+X_n$$
$$\text{Every $X_i$ is distributed geometrically, with probability of success $\frac{n-i}{n}$}$$ Now because each $X_i$ is independent we use the linearity of expectation: $$\Bbb E[X]=\Bbb E[X_1]+\Bbb E[X_2]+...+\Bbb E[X_n]$$ $$=1+\frac{n}{n-1}+\frac{n}{n-2}+...+n$$ $$=n(1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n})$$ $$=n\sum_{i=1}^n \frac{1}{i} $$ Now, how do I apply this to the question above to obtain $\Bbb P[X\geq t]?$ Apologies if this seems obvious. Edit: Seemingly the expected value will not help to obtain the answer I'm looking for. I suppose what I need is the CDF of the random variable $X$. Any ideas?
Using the principle of inclusion exclusion, \begin{align} P(\text{more than $t$ boxes are needed}) &=P\left(\bigcup_{i=1}^n\{\text{prize # $i$ is missing}\}\right ) \\&=\sum_{k=1}^n(-1)^{k+1}\hspace{-.7cm}\sum_{i(1)\le i(2)\le \dots\le i(k)}\hspace{-.7cm}P\Big(\text{prizes $i(1),i(2),\dots,i(k)$ are missing}\Big) \\&=\boxed{\sum_{k=1}^n(-1)^{k+1}\binom{n}k\left(1-\frac{k}n\right)^t.} \end{align}