0
$\begingroup$

Let $Y_1, Y_2,...$ be i.i.d uniformly distribution random variables on set {1, 2,..., n}. If we define $X^{n} = \min(k: Y_k = Y_j$ for some $j<k$) for the first time there's a repetition in the sequence $Y_i$.

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

Right now, I'm stuck with the following:

$$F_{(X^n)/\sqrt{n}}(x) = P({(X^n)/\sqrt{n}} \le x) \\ =1- [(1-1/n)(1-2/n)...(1-({x/\sqrt{n}}-1)/n)]$$

But don't know how to proceed from there!

$\endgroup$
0
$\begingroup$

Let's consider the survival probability distribution of $X_n$ (I'm going to use subscripts to avoid confusion with exponentiation). We observe that if $X_n > x$, then $Y_1, Y_2, \ldots, Y_x$ are all distinct. Possibly more are distinct, but we only care that at least the first $x$ draws of $Y$ are distinct. Since these are drawn from a discrete uniform distribution on $\{1, \ldots, n\}$, we see that the desired survival probability is $$S_{X_n}(x) = \Pr[X_n > x] = \prod_{k=0}^{x-1} \frac{n-k}{n} = \frac{n!}{(n-x)! n^x}, \quad x = 1, \ldots, n.$$ Now let $n = m^2$ and define $W_m = X_{m^2}/m$. Then $$\Pr[W_m > w] = \Pr[X_{m^2}/m > w] = \Pr[X_{m^2} > mw] = \frac{(m^2)!}{(m^2-mw)! m^{2mw}}.$$ Using Stirling's approximation $$n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n,$$ we obtain $$\Pr[W_m > w] \approx e^{-m w} \left(1 - \frac{w}{m}\right)^{-m^2 + mw - 1/2}.$$ I leave it as an exercise to show that as $m \to \infty$ this expression tends to $e^{-w^2/2}$.

$\endgroup$

Your Answer

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