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.
 A: 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.
