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.
 A: 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$.
A: 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)}} $.
