Tiempo de primera copia de un duplicado

Question

Considere la posibilidad de un proceso aleatorio que las muestras de manera uniforme con la sustitución de [n]. El tiempo de espera para encontrar un duplicado es un factor constante de veces $\sqrt{n}$. Esta es una versión del famoso Problema del Cumpleaños. ¿Cómo se puede encontrar el tiempo de espera para encontrar el primer ejemplar de la primera duplicado? Obviamente, esto va a ocurrir algún tiempo antes. También, ¿cuál es la distribución de este tiempo?

Si usted fijar la posición de la posterior copia del duplicado, a continuación, la copia anterior parece ocurrir de manera uniforme antes de ella, pero no estoy seguro de lo útil que es para contestar las preguntas.

Por el momento simplemente me refiero a que cada muestra tiene una unidad de tiempo por lo que el tiempo es el número de muestras en ese punto. Esta no es una pregunta acerca de los algoritmos de cálculo.

Answer 1

Llame a $2\leqslant D_n\leqslant n+1$ el tiempo de la primera duplicado y $1\leqslant C_n\leqslant D_n-1$ el tiempo de la primera copia de la primera duplicado.

Como usted señaló, para cada una de las $2\leqslant k\leqslant n+1$, condicionalmente en el evento $[D_n=k]$, $C_n$ se distribuye uniformemente en $\{1,2,\ldots,k-1\}$ por lo tanto $\mathbb E(C_n\mid D_n=k)=\frac12k$. Por lo tanto, $\mathbb E(C_n)=\frac12\mathbb E(D_n)$ y cada asymptotics en $\mathbb E(D_n)$ al $n\to\infty$ se traduce en un asymptotics en $\mathbb E(C_n)$.

Asimismo, para cada $1\leqslant i\leqslant n$, descomponiendo el caso de $[C_n=i]$ en sus intersecciones con los eventos de $[D_n=k]$$i+1\leqslant k\leqslant n+1$, se obtiene $$ \mathbb P(C_n=i)=\sum_{k=i+1}^{n+1}\frac{\mathbb P(D_n=k)}{k-1}. $$ Recordar por último que, para cada $2\leqslant k\leqslant n+1$, $$ \mathbb P(D_n\geqslant k)=\prod_{\ell=1}^{k-2}\frac{n-\ell}n, $$ por lo tanto, para cada $1\leqslant i\leqslant n$, $$ \mathbb P(C_n=i)=\frac1n\sum_{k=i}^{n}\prod_{\ell=1}^{k-1}\frac{n-\ell}n=\frac{n!}{n^{n+1}}\sum_{k=0}^{n-i}\frac{n^k}{k!}. $$ Edit: Vamos a $N_n$ denotar una variable aleatoria de Poisson con parámetro de $n$, luego $$ \mathbb P(C_n=i)=\frac{n!\mathrm e^n}{n^{n+1}}\mathbb P(N_n\leqslant n-i). $$ Asymptotics seguir a partir de esta identidad, ya que el prefactor $n!\mathrm e^n/n^{n+1}$ es equivalente a $\sqrt{2\pi/n}$ al $n\to\infty$, e $(N_n-n)/\sqrt{n}$ converge en distribución a una variable aleatoria normal estándar. Por lo tanto, si $i_n/\sqrt{n}\to x$, $$ \mathbb P(C_n=i_n)\sim\sqrt{\frac{2\pi}n}\Phi (x)=\frac1{\sqrt{n}}\int_x^{+\infty}\mathrm e^{-s^2/2}\mathrm ds. $$ Sumando los rendimientos $$ \mathbb P(C_n\geqslant i_n)\sim\int_x^{+\infty}(s-x)\mathrm e^{-s^2/2}\mathrm ds=\int_0^{+\infty}\mathrm e^{-(s+x)^2/2}\mathrm ds. $$ En otras palabras, $C_n/\sqrt{n}$ converge en distribución a una variable aleatoria $C$ cuya función de densidad de probabilidad $f_C$ se define, para cada $x\geqslant0$, por $$ f_C(x)=\int_x^{+\infty}\mathrm e^{-s^2/2}\mathrm ds. $$