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?


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.