# Coupon Collector's Problem

Let $\displaystyle (X_k)_{k\geq 1}$ be a sequence of random variables uniformly distributed on $\displaystyle \{1,...,n\}$. Let $$\displaystyle\tau_{n}=\inf\{m\geq 1:\{X_1,...,X_m\}=\{1,...,n\}\}$$ be the first time for which all values have been observed.

Let $\displaystyle\tau_{n}^{(k)}=\inf\{m\geq 1:|\{X_1,...,X_m\}|=k\}$. Prove that the random variables $$\displaystyle \left(\tau_{n}^{(k)}-\tau_{n}^{(k-1)}\right)_{2\leq k\leq n}$$ are independent and calculate their repective distributions.

So I think these random variables are distributed Geometrically, is this correct? How can I show this? How do I show they are independent?

Also,

Deduce that: $$\frac{\tau_n}{n\log n}\rightarrow 1$$ in probability as $n\rightarrow \infty$, i.e. for any $\epsilon >0$,

$$\mathbb P\left(\left|\frac{\tau_n}{n\log n}-1\right|>\epsilon\right)\rightarrow 0$$

This looks similar to the Chebyshev inequality, but I'm not sure about it either.

Put $T_k=\tau_n^{(k)}$ ; thus $T_1=1$. If $t_2\geq 1$ is any value, then $T_2=t_2$ if and only if, the $t_2-1$ successive values $X_2,X_3, \ldots, X_{t_2}$ are all equal to $X_1$ (thus we have no choice for their value), but $X_{t_2+1}$ is not (so we have $n-1$ choices for its value). We deduce

$$P(T_2=t_2)=\frac{n-1}{n^{t_2+1}}$$

Now let $t_3 \geq 1$ be another value. If $T_2=t_2$, then we have $T_3=t_3$ if and only if, the $t_3-1$ successive values $X_{t_2+2},X_{t_2+3}, \ldots, X_{t_2+t_3}$ are all in $\lbrace X_1,X_{t_2+1} \rbrace$ (thus we have two choices for their value), but $X_{t_2+t_3+1}$ is not (so we have $n-2$ choices for its value). We deduce

$$P(T_2=t_2,T_3=t_3)=\big(\frac{2}{n}\big)^{t_3-1}\frac{n-2}{n}P(T_2=t_2)$$ In particular, $T_3$ is independent of $T_2$.

Similarly, if $t_4$ is any other value we have

$$P(T_2=t_2,T_3=t_3,T_4=t_4)=\big(\frac{3}{n}\big)^{t_4-1}\frac{n-3}{n}P(T_2=t_2,T_3=t_3)$$ In particular, $T_4$ is independent of $T_2$ and $T_3$.

It is now clear by induction on $k$ that for any values $t_2,t_3, \ldots ,t_k \geq 1$,

$$P(T_2=t_2,T_3=t_3, \ldots ,T_k=t_k)=p_2p_3 \ldots p_k \ \text{with} \ p_j=\big(\frac{j-1}{n}\big)^{t_j-1}\frac{n-(j-1)}{n} \ (\text{for} \ 2 \leq j \leq k)$$

So the $T_j$ are independent and $P(T_j=t_j)=p_j$ for $2 \leq j \leq k$. So the law of $T_j$ is exponential as you expected :

$$P(T_j=t)=\big(\frac{j-1}{n}\big)^{t-1}\frac{n-(j-1)}{n} (\text{for} \ t \geq 2)$$

When $j=n$ we deduce

$$P(\tau_n =t)=\big(\frac{n-1}{n}\big)^{t-1}\frac{1}{n} (\text{for} \ t \geq 2)$$

And hence

$$\begin{array}{lcl} P(\tau_n \geq t)&=& \sum_{s\geq t}P(\tau_n=s) =\frac{1}{n} \sum_{s\geq t}\big(\frac{n-1}{n}\big)^{s-1} =\frac{1}{n}\big(\frac{n-1}{n}\big)^{t-1} \frac{1}{1-\frac{n-1}{n}}= \big(\frac{n-1}{n}\big)^{t-1} \end{array}$$

for integers $t$.

If $t$ is not an integer, we have $\lfloor t \rfloor \leq t \leq \lceil t \rceil$, $P(\tau_n \geq t)=P(\tau_n \geq \lceil t \rceil)$ and hence

$$\big(\frac{n-1}{n}\big)^{t+1} \leq P(\tau_n \geq t) \leq \big(\frac{n-1}{n}\big)^{t}$$

So if we put $a_n=n\log(n)(1+\varepsilon)$ we have

$$\begin{array}{lcl} P\left( \tau_n \geq a_n \right)&\leq & \big(\frac{n-1}{n}\big)^{a_n} \\ &=& \exp(n\log(n)\log(1-\frac{1}{n})(1+\varepsilon)) \\ &\leq& \exp(n\log(n)(-\frac{1}{n})(1+\varepsilon))=\frac{1}{{(1+\varepsilon)}^{n}} \end{array}$$ ,

so $P(\tau_n \geq n\log(n)(1+\varepsilon)) \to 0$ when $n\to \infty$. Similarly, $P(\tau_n \leq n\log(n)(1-\varepsilon)) \to 0$ when $n\to \infty$.

Show that the event $\{ \tau_n^{(k)} - \tau_n^{(k-1)} = j \}$ only involves random variables that are independent with $X_1,...,X_{\tau_n^{(k-1)}}$.