# Generalization of the birthday problem with convergence in distribution.

I have independent identically distributed random variables $Y_1, Y_2, ...$ that are uniformly distributed on the set $\lbrace1,2,...,n\rbrace$. I define $X^{(n)}=min\lbrace k:Y_k=Y_j$ for some $j <k\rbrace$. I'd like to show that $X^{(n)}/\sqrt{n}$ converges in distribution (and to find the distribution function of the limit).

Here is what I've done:

Letting $F_n(x)$ be the distribution function of $X^{(n)}/\sqrt{n}$, we have that

$$F_n(x)=\mathbb{P}(X^{(n)}/\sqrt{n}\leq x)=1-\mathbb{P}(X^{(n)}>\lfloor \sqrt{n}x\rfloor)=1-\prod_{k=1}^{\lfloor \sqrt{n}x\rfloor-1}(1-\frac{k}{n}).$$

But I'm stuck with the limit...

Can you help me please, I feel like I've done it wrong!?

Consider $$R_n=\prod_{k=1}^{\lfloor \sqrt{n}x\rfloor-1}\left(1-\frac{k}{n}\right),$$ and note that, for every $t$ in $(0,\frac12)$, $\mathrm e^{-t-t^2}\leqslant1-t\leqslant\mathrm e^{-t}$, hence, for every $n\geqslant4x^2$, $$\mathrm e^{-S_n-T_n}\leqslant R_n\leqslant\mathrm e^{-S_n},$$ where $$S_n=\frac1n\sum_{k=1}^{\lfloor \sqrt{n}x\rfloor-1}k,\qquad T_n=\frac1{n^2}\sum_{k=1}^{\lfloor \sqrt{n}x\rfloor-1}k^2.$$ Standard estimates are that, when $n\to\infty$, $$S_n\sim\frac1n\frac{(\sqrt{n}x)^2}2=\frac{x^2}2,\qquad T_n\sim\frac1{n^2}\frac{(\sqrt{n}x)^3}3\to0,$$ hence $$R_n\to\mathrm e^{-x^2/2}.$$
• Shouldn't there be an additional factor of $2$ in $T_n$? – Number 34 Jan 10 '17 at 22:04