# I am trying to prove the distribution function for the 'birthday problem' can anyone help?

Let $Y_1, Y_2, . . .$ be i.i.d. and uniformly distributed on the set ${1, 2, . . . , n}$.

Define $X^{(n)} = \min \{k : Y_k = Y_j \,\,for \,\,some \,\,j < k\}$, the first time that we see a repetition in the sequence $Y_i$. (Interpret the case n = 365).

Prove that $X^{(n)}/\sqrt{n}$ converges in distribution to a limit with distribution function $F(x) = 1 − \exp(−x^2/2)$ for $x > 0$.

[Hint: Observe that $\mathbb{P}(X^{(n)}>m)= (1−1/n)(1−2/n)...(1− (m-1)/n )$. You may find it useful to use bounds such as $−h − h^2 < log(1 − h) < −h$ for sufficiently ￼￼￼small positive h. ]

So far I have tried write the expression for $\mathbb{P} \left( \displaystyle\frac{X^{(n)}}{\sqrt(n)} > m \right)$ but I have not been able to use the hint to arrive at the stated formula.

• It would be easier to read what you have written if you used LaTeX/MathJax. It would also help if you told us what you have tried so far to solve the problem Commented Jun 22, 2016 at 14:03

$- \frac{1}{n} \sum_{k=1}^{x\sqrt(n)} k - \frac{1}{n^2}\sum_{k=1}^{x\sqrt(n)-1} k^2 < \ln(\mathbb{P}(X^{(n)} < x\sqrt{n})) < - \frac{1}{n} \sum_{k=1}^{x\sqrt(n)} k$
Evaluating the sum and taking $n \to \infty$. We get,
$-x^2/2 - 0 < \ln(\mathbb{P}(X^{(n)} < x\sqrt{n})) < -x^2/2$
$\mathbb{P}(X^{(n)}/ \sqrt{n} < x) = exp(-x^2/2)$. Taking the complement gives the answer.