Pregunta de probabilidad.

Question

Consideremos un proceso aleatorio en el que los enteros se muestrean uniformemente con reemplazo de $\{1,\ldots,n\}$ . Sea $X$ sea una variable aleatoria que represente el número de muestras hasta que se encuentre un duplicado. Así, si las muestras fueran $1,6,3,2, 5,1$ entonces $X=6$ . Sea $Y$ sea una variable aleatoria que represente el número de muestras antes de que los dos valores $1$ y $2$ se han encontrado. Así, en nuestro ejemplo $Y=4$ .

¿Cómo se puede encontrar lo siguiente?

• La probabilidad $P(X<Y)$ o en otras palabras $P(Y-X > 0)$ .
• La probabilidad condicional $P(X \geq x \,\mid \, X<Y)$ .

Answer 1

$$\lim_{n\to\infty}n\,\mathbb P(X\gt Y)=2.$$

Para demostrarlo, hay que tener en cuenta que, para cada $x\geqslant2$ El evento $[Y\leqslant x,X=x+1]$ corresponde a una muestra de tamaño $x$ sin duplicar e incluyendo $1$ y $2$ y a un duplicado que aparece en el momento $x+1$ . Cada muestra de tamaño $x$ sin duplicar e incluyendo $1$ y $2$ corresponde bijetivamente a una muestra de tamaño $x-2$ sin duplicado y sin $1$ y $2$ y a la elección de una posición en esta muestra de tamaño $x-1$ para colocar $1$ y finalmente a la elección de una posición en esta muestra aumentada para colocar $2$ . Y hay $x$ opciones para el duplicado en el momento $x+1$ .

Por lo tanto, el número de muestras correspondientes al evento $[Y\leqslant x,X=x+1]$ es $$ (n-2)_{x-2}\cdot(x-1)\cdot x\cdot x. $$ El número total de muestras de longitud $x+1$ es $n^{x+1}$ por lo que $$ \mathbb P(Y\lt X)=\sum_{x=2}^n\mathbb P(Y\leqslant x,X=x+1)=t_n, $$ con $$ t_n=\sum_{x=2}^n\frac{(x-1)x^2(n-2)_{x-2}}{n^{x+1}}=\frac{(n-2)!}{n^{n+1}}\sum_{y=0}^{n-2}\frac{(n-y-1)(n-y)^2n^y}{y!}, $$ donde se utiliza el cambio de variable $y=n-x$ . Sea $N_n$ denotan una variable aleatoria de Poisson con parámetro $n$ entonces $$ t_n=\frac{(n-2)!}{n^{n+1}}\mathrm e^n\mathbb E((n-N_n-1)(n-N_n)^2:n-N_n\geqslant2). $$ El teorema del límite central indica que $n-N_n=\sqrt{n}Z_n$ donde $Z_n\to Z$ en la distribución, con $Z$ normal estándar, por lo que $$ t_n\sim\frac{(n-2)!}{n^{n+1}}\mathrm e^nn^{3/2}\mathbb E(Z^3:Z\geqslant0). $$ La fórmula de Stirling y el valor $\mathbb E(Z^3:Z\geqslant0)=2/\sqrt{2\pi}$ produce el resultado indicado al principio de esta respuesta.

---

Asimismo, para cada $x\geqslant2$ , $$ \mathbb P(X\geqslant x\mid X\lt Y)=\frac{\mathbb P(X\geqslant x,X\lt Y)}{\mathbb P(X\lt Y)}=\frac{\mathbb P(X\geqslant x)-\mathbb P(X\geqslant x,X\gt Y)}{\mathbb P(X\lt Y)}. $$ El denominador es $1-\mathbb P(X\gt Y)=1-t_n$ . El numerador implica $\mathbb P(X\geqslant x)$ cuyo valor es conocido, y $$ \mathbb P(X\geqslant x,X\gt Y)=\sum_{y=x-1}^{n}\mathbb P(Y\leqslant y,X=y+1), $$ y uno sabe por la primera parte de este post que $$ \mathbb P(Y\leqslant y,X=y+1)=\frac{(y-1)y^2(n-2)_{y-2}}{n^{y+1}}, $$ por lo que el valor de $\mathbb P(X\geqslant x\mid X\lt Y)$ sigue.

Answer 2

Sea A(i) el caso de que se hayan muestreado i números distintos, ninguno de ellos 1 o 2. Sea B(i) el caso de que se hayan muestreado i+1 números distintos, siendo exactamente uno de ellos 1 o 2. (Ambos son para $0 \leq i \leq n-2$ .) Denotemos también que el evento de obtener un duplicado es D, y el evento de obtener 1 y 2 es M. Cuando se alcanza M o D, el proceso se detiene, y esto debe ocurrir después de un máximo de n pasos. Lo que queremos para la primera pregunta, "¿qué es $P(X<Y)$ ?" es la probabilidad de que el proceso termine en M.

El proceso comienza en A(0) y las probabilidades de ir entre estos eventos son $$P(A(i) \to A(i+1)) = (n-i-2)/n$$ $$P(A(i) \to B(i)) = 2/n$$ $$P(A(i) \to D) = i/n$$

$$P(B(i) \to B(i+1)) = (n-i-2)/n$$ $$P(B(i) \to D) = (i+1)/n$$ $$P(B(i) \to M) = (n-i-2)/n$$

Nótese que el proceso sólo llega a M a través de un B(i) y que proviene de B (i-1) o de A(i). Hay j caminos, cada uno de ellos de longitud j+1, desde A(0) hasta M: $$A(0) \to B(0) \dots B(j-1) \to M$$ $$A(0) \to A(1) \to B(1) \dots B(j-1) \to M$$ $$\dots$$ $$A(0) \to A(1) \dots A(j-1) \to B(j-1) \to M$$

Cada uno de estos caminos tiene la misma probabilidad, es decir $$2(n-2)(n-3) \dots (n-j) / n^{j+1}$$ así que $$P(X=j+1 | X < Y) = 2j(n-2)(n-3) \dots (n-j) / n^{j+1}$$ y $$P(X<Y) = 2 \sum_{i=1}^{n-1} \frac{i(n-2)!}{(n-1-i)!n^{i+1}}$$