46. Probabilidades de Coincidencias

Problema del libro de Mosteller

Bajo las condiciones del problema de coincidencias anterior, ¿cuál es la probabilidad de obtener exactamente \( r \) coincidencias?

Solución para las Probabilidades de Coincidencias

Este problema se parece al primer problema de la distribución de Poisson que discutimos antes (Problema 28). Donde anteriormente asumimos que tenemos probabilidades iguales e independientes para una moneda defectuosa (o un 1) en cada posición, en el problema actual, las posibilidades de una coincidencia no son independientes para cada par. Por ejemplo, si tenemos \( n - 1 \) pares de cartas coincidiendo, el par \( n \) debe coincidir también, por lo que no tenemos independencia. No obstante, para valores grandes de \( n \), el grado de dependencia no es grande, y deberíamos anticipar que la probabilidad de \( r \) coincidencias en este problema puede estar bastante cerca de la de la Poisson para eventos de pequeña probabilidad de ocurrir. Al final queremos comparar la respuesta del problema actual con la de la Poisson con media igual a 1.

Para empezar a obtener tales problemas, me gusta usar resultados para pequeños valores de \( n \), porque a menudo son muy sugestivos. Para \( n = 1 \), una coincidencia es segura. Para \( n = 2 \), la probabilidad es \(\frac{1}{2}\) de 0 coincidencias y \(\frac{1}{2}\) de 2 coincidencias. Para \( n = 3 \), permutemos las cartas 1, 2 y 3 y coloquémoslas en una tabla de combinaciones posibles con la baraja de coincidencias debajo de la baraja objetivo, que podría estar también en orden serial.

Resumiendo los resultados de la lista nos da

Se observa que la probabilidad de n coincidencias es 1/n!

Nota también que la media de cada distribución es 1, como se anunció en el problema anterior, esto da una verificación parcial del cálculo.

Podemos volver a introducir esta relación en el problema. Sea \( P(r|n) \) la probabilidad de exactamente \( r \) coincidencias en una disposición de \( n \) cosas. Podríamos obtener exactamente \( r \) coincidencias teniendo una coincidencia específica y teniendo el resto no coincidente. Por ejemplo, la probabilidad de que la primera \( r \) coincida y el resto no es

\[ \frac{1}{n(n - 1) \ldots (n - r + 1)} P(0|n - r). \]

Pero hay \( \binom{n}{r} \) opciones mutuamente excluyentes de \( r \) posiciones en las que tener exactamente \( r \) coincidencias. Por lo tanto

\[ P(r|n) = \binom{n}{r} \frac{1}{n(n - 1) \ldots (n - r + 1)} P(0|n - r) = \frac{1}{r!} P(0|n - r). \]

Entonces

\[ P(r|n) = \frac{1}{r!} P(0|n - r), \quad r = 0, 1, \ldots, n - 1. \]

Siendo \( P(0|n) = \frac{n!}{n^n} \), y así podemos extender nuestra notación suponiendo \( P(0|0) = 1 \), si lo deseamos, sin hacer violencia a la otra notación.

Verifiquemos la relación (1) para \( n = 4, r = 2 \). Para \( n = 4, r = 2 \), dice

\[ P(2|4) = \frac{1}{2!} P(0|2). \]

\(\frac{6}{24} = \frac{1}{2} \frac{1}{2}\) lo cual verifica la expresión (1) para este ejemplo.

Dado que tratamos con distribuciones de probabilidad, la suma de las probabilidades sobre todos los posibles números de coincidencias para un valor dado de \( n \) es 1, o en símbolos,

\[ P(0|n) + P(1|n) + \ldots + P(n - 1|n) + P(n|n) = 1. \]

Podemos reescribir esta ecuación, usando la relación (1), como

\[ \frac{1}{0!} P(0|n) + \frac{1}{1!} P(0|n - 1) + \frac{1}{2!} P(0|n - 2) + \ldots + \frac{1}{n!} P(0|0) = 1. \]

Dado que sabemos \( P(0|n) = \frac{n!}{n^n} \), podríamos resolver sucesivamente las ecuaciones para \( P(0|n) \) para valores más altos de \( n \). Por ejemplo, para \( n = 1 \) obtenemos

\[ P(0|1) + \frac{1}{1} = 1 \]

o

\[ P(0|1) = 0. \]

Para \( n = 2 \)

\[ P(0|2) + \frac{1}{1} P(0|1) + \frac{1}{2} = 1 \]

o

\[ P(0|2) = \frac{1}{2}. \]

Para \( n = 3 \)

\[ P(0|3) + \frac{1}{1} P(0|2) + \frac{1}{2} P(0|1) + \frac{1}{6} = 1 \]

o

\[ P(0|3) = \frac{1}{3}. \]

Los ejemplos anteriores muestran que, en principio, podemos obtener \( P(0|n) \) para cualquier \( n \), pero no sugieren todavía una fórmula general para \( P(0|n) \). A veces tomando...

Las diferencias ayudan. Veamos \( P(0|n) - P(0|n-1) \) para los valores de \( n \) hasta 4 (dado en la Tabla Resumen):

\[ P(0|1) - P(0|0) = 0 - 1 = -1 = -\frac{1}{1!}, \]

\[ P(0|2) - P(0|1) = \frac{1}{2} - 0 = + \frac{1}{2} = + \frac{1}{2!}, \]

\[ P(0|3) - P(0|2) = \frac{2}{6} - \frac{1}{2} = -\frac{1}{6} = -\frac{1}{3!}, \]

\[ P(0|4) - P(0|3) = \frac{9}{24} - \frac{2}{6} = + \frac{1}{24} = + \frac{1}{4!}. \]

Estos resultados sugieren que las diferencias tienen la forma \((-1)^r / r!\). Es decir,

\[ P(0|n - r) - P(0|n - r - 1) = (-1)^{n-r}/(n-r)!. \]

Cuando sumamos las diferencias, obtenemos en el lado izquierdo

\[ P(0|n - r) - P(0|0) = - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^{n-r}}{(n-r)!}. \]

Escribiendo \( P(0|0) \) en la forma \( 1 / 0! \) y transponiéndolo, obtenemos, si las diferencias tienen la forma conjeturada,

\[ P(0|n - r) = \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^{n-r}}{(n-r)!}. \]

Todo lo que necesitamos hacer ahora es verificar que esta conjetura funciona. Obtenemos

\[ 1 + \frac{1}{1!} \sum_{i=0}^{n-1} \frac{(-1)^i}{i!} + \frac{1}{2!} \sum_{i=0}^{n-2} \frac{(-1)^i}{i!} + \cdots + \frac{1}{(n-1)!} \sum_{i=0}^{1} \frac{(-1)^i}{i!} + \frac{1}{n!} 0 \sum_{i=0}^{0} \frac{(-1)^i}{i!}. \]

¡Valor, hermano! Esto parece un lío, pero solo necesita un poco de atención. La suma en la expresión (4) está compuesta por términos de la forma

\[ \frac{(-1)^j}{j! \cdot i!}, \]

donde los \( j \) provienen de los multiplicadores delante de los signos de suma y los \( i \) de los términos detrás. Agrupemos los términos de modo que \( i + j \) sea una constante. Por ejemplo, cuando \( i + j = 3 \) (suponiendo \( n \geq 3 \)), obtenemos solo los términos

\[ \frac{(-1)^3}{0! \cdot 3!} + \frac{(-1)^2}{1! \cdot 2!} + \frac{(-1)^1}{2! \cdot 1!} + \frac{(-1)^0}{3! \cdot 0!}. \]

Si multiplicamos esto por 3!, se convierte en la más familiar

\[ \frac{3!}{0! \cdot 3!} + \frac{3!}{1! \cdot 2!} + \frac{3!}{2! \cdot 1!} + \frac{3!}{3! \cdot 0!}, \]

que puede escribirse en notación de coeficiente binomial:

\[ - \binom{3}{0} + \binom{3}{1} - \binom{3}{2} + \binom{3}{3}. \]

Y esta última es solo una expansión de \((x + y)^3\) cuando \( x = -1 \) y \( y = 1 \), otra manera de decir que la suma es cero porque \((-1 + 1)^3 = 0^3 = 0\).

Este truco de expansión binomial puede aplicarse para cada \( i + j = r \) para \( r = 1, 2, \ldots, n \), y para cada \( r \) obtenemos una suma de cero. Para \( r = 0 \), obtenemos solo un término \((-1)^0 (0! 0!) = 1\). En consecuencia, hemos verificado que la solución conjeturada (3) satisface la ecuación (2).

¿Podrían otras soluciones satisfacer la ecuación (2)? No. Nuestra técnica fue solo una manera fácil de verificar la ecuación (2). Podríamos, con un poco más de esfuerzo, haber resuelto \( P(0|n) \) después de establecer nuestra conjetura para \( P(0|1), \ldots, P(0|n-1) \), logrando así una prueba de inducción formal más rigurosa.

Finalmente, sustituyendo el resultado (3) en el resultado (1), podemos escribir

\[ P(r|n) = \frac{1}{r!} \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^{n-r}}{(n-r)!} \right). \]

Cuando \( n - r \) es grande, los paréntesis contienen muchos términos en la expansión de \( e^{-1} \), y por lo tanto

\[ P(r|n) \approx \frac{1}{r!} e^{-1}, \]

para \( n - r \) grande.

Previmos inicialmente una relación cercana entre la probabilidad de \( r \) coincidencias en el problema de coincidencias y la de un recuento de \( r \) en el problema de Poisson con media igual a 1. Para un acuerdo más cercano, hemos encontrado que \( n - r \) necesita ser grande, no solo \( n \) como originalmente conjeturamos.

La probabilidad de 0 coincidencias es entonces aproximadamente \( e^{-1} \approx 0.368 \) para \( n \) grande.

Créditos
Traducción del problema 46 del libro Fifty Challenging Problems in Probability with Solutions,  F.  Mosteller,  Dover, New York, 1965 , MOSTELLER

Vídeo introducción con http://www.lumen5.com