Probabilidad de dobles coincidencias

Question

Ayer resolví este problema de teoría de la probabilidad: Dos barajas similares de $N$ Las cartas distintas se enfrentan a un mazo objetivo similar. Hallar la probabilidad de que exactamente $m \leq N$ partidos.

Procedí de la siguiente manera. Sea $A_i$ denota el suceso de que $i^{\text{th}}$ (de ambos mazos) contra el mazo objetivo. Por lo tanto $$P(\text{E = exactly $ m $ match occurs})(N,m)$$ (no te preocupes por la mala notación, por favor) entonces

$$P(N,m) = S_m - \binom{m+1}{m}S_{m+1} + \binom{m+2}{m}S_{m+2} + \ldots + \binom{N}{m} S_{N}$$

donde $S_1 = \sum_{1\leq i \leq N} P(A_i)$ , $S_2 = \sum_{1\leq i \lt j \leq N} P(A_i \cap A_j) \ldots$

Claramente, tenemos $$S_{m+k} = \binom{N}{m+k} \frac{(N-m-k)!^2}{N!^2}$$ Por lo tanto, \begin{align*} P(N,m) &= \sum_{k=0}^{N-m} (-1)^k \binom{m+k}{m} \binom{N}{m+k} \frac{(N-m-k)!^2}{N!^2} \\ &= \frac{1}{m!} \frac{1}{N!} \sum_{k=0}^{N-m} (-1)^k \frac{(N-m-k)!}{k!} \end{align*}

Tras obtener la expresión anterior, pensé si existe alguna fórmula cerrada bonita para la serie Así que la introduje en W|A pero no devuelve ninguna (en términos de funciones elementales).

A continuación, empecé a preguntarme, ¿cómo se comporta esta función de probabilidad como $N \rightarrow \infty$ . Porque este límite podría ser la traducción real de algunos fenómenos del mundo real (aunque eso es algo sobre lo que habrá que reflexionar más adelante).

Así que, primero intenté comprobar $m=0$

\begin{align*} \lim_{N \rightarrow \infty} P(N,0) &= \lim_{N \rightarrow \infty} \frac{1}{N!} \sum_{k=0}^{N} (-1)^k \frac{(N-k)!}{k!} \\ &= \lim_{N \rightarrow \infty} \left(1 - \frac{1}{N} + \frac{1}{2!}\frac{1}{N(N-1)} - \ldots \right) \end{align*}

No me llama la atención cómo resolver este límite, ya que no puedo evaluar el límite puntualmente puesto que es una suma infinita. Así que he pensado en establecer una recurrencia (que puede ayudar?). Esto es lo que he encontrado:

$$P(N+2,0) = P(N+1,0) + \frac{P(N,0)}{(N+1)(N+2)} + \frac{(-1)^{N}}{(N+2)!^2}$$

Pero, de nuevo, seguía sin entender gran cosa. Incluso he expresado esto como una integral (sólo porque a veces, ayuda) y luego trató de hacer algunas manipulaciones, pero todavía ni idea

$$P(N,0) = (N+1) \int_0^1 \sum_{k=0}^N\frac{ t^k(1-t)^{N-k}}{k!^2} \mathrm{d}t$$

Estas son las preguntas para las que intento encontrar una solución:

1. ¿Existe alguna forma cerrada agradable para la expresión?

2. ¿Cómo se comporta la función de probabilidad, que he derivado, cuando $N \rightarrow \infty$ para un $m$ ?

3. ¿Qué ocurre cuando $N \rightarrow \infty$ y $m \rightarrow \infty$ ?

Agradecería cualquier ayuda.

Edición 1 : Me di cuenta de que $P(N,0) \rightarrow 1$ como $n \rightarrow \infty$ con algunos cálculos, pero supongo que aún requiere una prueba rigurosa.

Answer 1

Sea $X_k = \mathbf{1}_{A_k}$ , $k=1,\dots,N$ sea la variable que indica una coincidencia (doble) en la variable $k$ th tarjeta para que $X = X_1+\dots + X_N$ es el número de coincidencias. Por linealidad, $$ \mathbb{E}[X] = \sum_{k=1}^N \mathbb{E}[X_k] = N\cdot \frac{1}{N^2} = \frac{1}{N}. $$ Por la desigualdad de Markov, $\mathbb{P}(X\ge 1) \le \mathbb{E}[X] \to 0$ , $N\to\infty$ . Por lo tanto, $P(N,0)\to 1$ , $N\to\infty$ .

Answer 2

No veo cómo conseguir una forma más bonita de la expresión, pero intentaré responder a las preguntas 2 y 3. Así que tenemos esto: $$P(N,m)=\frac{1}{m!} \frac{1}{N!} \sum_{k=0}^{N-m} (-1)^k \frac{(N-m-k)!}{k!}$$ Obsérvese que el valor absoluto del término de la suma disminuye con el crecimiento de $k$ . Pero si tenemos una suma de la forma $$A_n=a_0-a_1+a_2-a_3+\dots+(-1)^na_n$$ con $$a_0>a_1>\dots>a_n>0$$ entonces esta suma se encuentra claramente entre $a_0-a_1$ y $a_0$ . Para demostrarlo, basta con observar que $A_{i+2}$ se encuentra entre $A_i$ y $A_{i+1}$ y utilizar la inducción para demostrar que $A_i$ se encuentra entre $A_0=a_0$ y $A_1=a_0-a_1$ entonces.

Para $m=0$ tenemos $A_1=1-1/N\le P(N,m)\le1=A_0$ lo que significa que el límite es $1$ . Todos los límites para $m>0$ entonces son ceros, porque estamos trabajando con probabilidades de sucesos disjuntos. Sin embargo, es fácil verlo explícitamente, porque en estos casos $A_0\le 1/N$ . El mismo argumento se aplica si ambos $N\to\infty$ y $m\to\infty$ : en realidad no importa, porque tan pronto como $m>0$ obtenemos $P(N,m)\le 1/N$ Así pues $P(N,m)\to 0$

Answer 3

Como ha señalado correctamente, el límite

$$\lim_{ N \rightarrow \infty} P(N,m )= \lim_{ N \rightarrow \infty} \frac{1}{m!} \frac{1}{N!} \sum_{k=0}^{N-m} (-1)^k \frac{(N-m-k)!}{k!}$$

para $m=0 \,$ se reduce a

$$ \lim_{N \rightarrow \infty} \frac{1}{N!} \sum_{k=0}^{N} (-1)^k \frac{(N-k)!}{k!} =\lim_{N \rightarrow \infty} \left( 1 - \frac{1}{N} + \frac{1}{2!}\frac{1}{N(N-1)}- \frac{1}{3!}\frac{1}{N(N-1)(N-2)} ... \right)$$

Obsérvese que esta suma de $N+1\,$ términos tiende a $1$ como $N \rightarrow \infty \,\,$ . Esto puede demostrarse de varias maneras. Por ejemplo, si agrupamos todos los términos empezando por el que ocupa la tercera posición en $\lfloor (N-1)/2 \rfloor \,\,$ pares consecutivos (podemos despreciar el último término si $N -1\,$ es impar) , éstas dan una suma (positiva) $S $ de la forma

$$ S= \frac {3!(N-2) -2!) (N-3)!}{2!3! N!} + \frac {5!(N-5) -4!) (N-5)!}{4!5! N!} ... $$

que satisface

$$S= \sum_{\substack {k=3 \\ k \text {odd}}}^{N} \frac {\left( k!(N-k+1) -(k-1)! \right) (N-k)!}{(k-1)!k! N!} \\ < \sum_{\substack {k=3 \\ k \text {odd}}}^{N} \frac{(N-k+1)(N-k)!}{(k-1)! N!} \\ = \sum_{\substack {k=3 \\ k \text {odd}}}^{N} \frac{(N-k+1)!}{(k-1)! N!} \\ < \frac{ \lfloor (N-2 )/2 \rfloor }{2!N(N-1)} $$

donde el último paso tiene en cuenta que los términos de la suma en la penúltima expresión disminuyen progresivamente (y entonces todos los términos después del primero son más pequeños que él). La última expresión tiende claramente a cero para $N \rightarrow \infty \,\,$ lo que implica que $S $ converge a $0$ también. Por tanto, el límite inicial se reduce a

$$ \lim_{N \rightarrow \infty} \left ( 1 - \frac{1}{N} \right)=1 $$

Consideremos ahora el caso $m>0\,$ . Para $m=1\,\,$ el límite de la suma se reduce a

$$= \lim_{N \rightarrow \infty} P(N,1) = \\ \lim_{N \rightarrow \infty} \frac{1}{N!} \sum_{k=0}^{N-1} (-1)^k \frac{(N-1-k)!}{k!} \\ = \lim_{N \rightarrow \infty} \left(\frac {(N-1)!}{N}- \frac{(N-2)!}{N!} + \frac{(N-3)!}{2! N!} - \frac{(N-4)!}{3! N!}\ldots \right)$$

Para $m=2\,\,$ el límite de la suma se reduce a

$$= \lim_{N \rightarrow \infty} P(N,2) = \\ \lim_{N \rightarrow \infty} \frac {1}{2!} \frac{1}{N!} \sum_{k=0}^{N-2} (-1)^k \frac{(N-2-k)!}{k!} \\ = \lim_{N \rightarrow \infty} \frac {1}{2!} \left(\frac {(N-2)!}{N}- \frac{(N-3)!}{N!} + \frac{(N-4)!}{2! N!} - \frac{(N-5)!}{3! N!}\ldots \right)$$

etc. En el caso general obtenemos

$$= \lim_{N \rightarrow \infty} P(N,m) = \lim_{N \rightarrow \infty} \frac{1}{m!} \frac{1}{N!} \sum_{k=0}^{N-m} (-1)^k \frac{(N-m-k)!}{k!} \\ = \lim_{N \rightarrow \infty} \frac {1!}{m!} \left(\frac {(N-m)!}{N!}- \frac{(N-m-1)!}{N!} + \frac{(N-m-2)!}{2!N!}-\frac{(N-m-3)!}{3!N!} + \ldots \right)$$

Para estudiar este límite, podemos proceder de nuevo como antes, agrupando los términos, a partir del tercero, en $\lfloor (N-m-2) /2 \rfloor $ pares consecutivos. Obtenemos una suma positiva $S'$ de la forma

$$ S'= \frac {3!(N-m-2) -2!) (N-m-3)!}{2!3! N!} + \frac {5!(N-m-4) -4!) (N-m-5)!}{4!5! N!} ... $$

que satisface

$$S'= \small{ \sum_{\substack {k=3 \\ k \text {odd}}}^{N-m} \frac {\left( k!(N-m-k+1) -(k-1)! \right) (N-m-k)!}{(k-1)!k! N!} \\ < \sum_{\substack {k=3 \\ k \text {odd}}}^{N-m} \frac{(N-m-k+1)(N-m-k)!}{(k-1)! N!} \\ = \sum_{\substack {k=3 \\ k \text {odd}}}^{N-m} \frac{(N-m-k+1)!}{(k-1)! N!} \\ < \frac{ \lfloor (N-m-2)/2 \rfloor (N-m-2)! }{2!N!} } $$

donde de nuevo el último paso tiene en cuenta que, en la suma mostrada en el penúltimo paso, todos los términos posteriores al primero (es decir, el correspondiente a $k=3$ ) son menores que ella. Como en el caso anterior, la última expresión tiende claramente a cero para $N \rightarrow \infty \,\,$ y esto implica que $S' $ converge a $0$ también. Así, el límite inicial para el caso general se reduce a

$$ \lim_{N \rightarrow \infty} \frac {1!}{m!} \left(\frac {(N-m)!}{N!}- \frac{(N-m-1)!}{N!} \right) $$

que, para $m \geq 1 \,\,$ converge a $0$ .

Por lo tanto, podemos concluir que

$$\lim_{N \rightarrow \infty} P (N,m) = \begin{cases} 1 \,\,\,\, \text{if $m=0$} \\ 0 \,\,\,\, \text{if $1 \leq m \leq N$} \end{cases}$$

Esto puede interpretarse de la siguiente manera: para $N \rightarrow \infty\,\, $ la probabilidad de obtener cualquier número de coincidencias de nuestros dos mazos tiende a cero, por lo que tenemos la probabilidad $1$ para no obtener ninguna coincidencia. Un cálculo por WA para el caso $m=0\,\,$ que se realiza fijando $N=1000\,\,$ se muestra aquí . Cálculos similares para los casos $m=1$ y $m=2$ se muestran aquí y aquí . Los valores proporcionados por WA confirman los resultados obtenidos anteriormente (desafortunadamente, WA parece tener algún problema para calcular las sumas para valores de $N>1000$ ).

Por último, en cuanto a la primera pregunta, en mi opinión no hay razones particulares para pensar que exista necesariamente una forma cerrada.