# Probability convergence in distribution

$Y_1, Y_2,..., Y_n$ are i.i.d and uniformly distributed on the set $\{1, 2,..., n\}$. Define $X_n = \min\{k: Y_k = Y_j\; \text {for some}\; j < k\}$, and prove that $\frac {X_n}{\sqrt n}$ converges in distribution to a limit with distribution function $F(x) = 1 - \exp\{-(x^2)/2\}$ for $x>0$.

My working:

$$P\left (\frac {X_n}{\sqrt n} \le x\right) = P\left (X_n \le x\sqrt n\right) = 1 - P\left(X_n > x\sqrt n\right)$$ $$= 1 - (1 - 1/n)\cdot(1 - 2/n)\cdot...\cdot(1 - \lfloor {x\sqrt n}\rfloor/n)$$ where $\lfloor\; \rfloor$ is the floor function

so I basically want to show $1 - (1 - 1/n)\cdot(1 - 2/n)\cdot...\cdot(1 - \lfloor {x\sqrt n}\rfloor/n)$ converges to $\exp\{-(x^2)/2\}$ but i have no idea how to do this.

For every $u\leqslant\frac12$, $\mathrm e^{-u-u^2}\leqslant1-u\leqslant\mathrm e^{-u}$ (can you prove this?). Thus, for every $n\geqslant2k$, $$\exp\left(-\frac{a_k}{n}-\frac{b_k}{n^2}\right)\leqslant\prod_{i=1}^k\left(1-\frac{i}n\right)\leqslant\exp\left(-\frac{a_k}n\right),$$ where $$a_k=\sum_{i=1}^ki=\frac{k(k+1)}{2},\qquad b_k=\sum_{i=1}^ki^2\leqslant k^3.$$ Let $x\gt0$. If $k=\lfloor x\sqrt{n}\rfloor$, then $n\geqslant2k$ for every $n$ large enough and $k\to\infty$ when $n\to\infty$ hence $a_k\sim\frac12k^2\sim\frac12x^2n$ and $b_k=o( n^2)$, thus the lower and upper bounds of the product both converge to $\mathrm e^{-x^2/2}$.
This shows (and I am rewriting this part of your post because there is a misprint in it) that $$P[X_n\gt x\sqrt{n}]\to\mathrm e^{-x^2/2},\qquad P[X_n\leqslant x\sqrt{n}]\to1-\mathrm e^{-x^2/2},$$ hence $X_n/\sqrt{n}\to X$ in distribution, where the density of $X$ is the function $f_X$ defined by $$f_X(x)=x\mathrm e^{-x^2/2}\mathbf 1_{x\geqslant0}.$$ Alternatively, $X_n^2/(2n)$ converges in distribution to a standard exponential random variable.