Problema de cumpleaños

La probabilidad de que dos personas no tengan el mismo cumpleaños es 364/365 . En una habitación con n personas, hay ( ^n² ₎ = n ( n - 1) / 2 pares de personas, es decir, (n²) eventos . ^La _probabilidad de que dos personas no compartan el mismo cumpleaños se puede aproximar asumiendo que estos eventos son independientes y, por lo tanto, multiplicando sus probabilidades. Ser independientes sería equivalente a elegir con reemplazo cualquier par de personas en el mundo, no solo en una habitación. En resumen, 364/365 se puede multiplicar por sí mismo ( n² ) ^veces _, lo que nos da

${\displaystyle {\bar {p}}(n)\approx \left({\frac {364}{365}}\right)^{\binom {n}{2}}.}$

Dado que esta es la probabilidad de que nadie tenga el mismo cumpleaños, entonces la probabilidad de que alguien comparta un cumpleaños es

${\displaystyle p(n)\approx 1-\left({\frac {364}{365}}\right)^{\binom {n}{2}}.}$

Y para el grupo de 23 personas, la probabilidad de compartir es

${\displaystyle p(23)\approx 1-\left({\frac {364}{365}}\right)^{\binom {23}{2}}=1-\left({\frac {364}{365}}\right)^{253}\approx 0.500477.}$

Aplicando la aproximación de Poisson para la distribución binomial al grupo de 23 personas,

${\displaystyle \operatorname {Poi} \left({\frac {\binom {23}{2}}{365}}\right)=\operatorname {Poi} \left({\frac {253}{365}}\right)\approx \operatorname {Poi} (0.6932)}$

entonces

${\displaystyle \Pr(X>0)=1-\Pr(X=0)\approx 1-e^{-0.6932}\approx 1-0.499998=0.500002.}$

El resultado es más del 50% como en las descripciones anteriores. Esta aproximación es la misma que la anterior basada en la expansión de Taylor que usa e ^x ≈ 1 + x .

Una buena regla general que se puede utilizar para el cálculo mental es la relación

${\displaystyle p(n,d)\approx {\frac {n^{2}}{2d}}}$

que también se puede escribir como

${\displaystyle n\approx {\sqrt {2d\times p(n)}}}$

lo cual funciona bien para probabilidades menores o iguales a 1/2 . En estas ecuaciones, d es el número de días en un año .

Por ejemplo, para estimar el número de personas necesarias para una probabilidad de 1/2 de compartir cumpleaños , obtenemos

${\displaystyle n\approx {\sqrt {2\times 365\times {\tfrac {1}{2}}}}={\sqrt {365}}\approx 19}$

Lo cual no está muy lejos de la respuesta correcta de 23.

Esto también se puede aproximar utilizando la siguiente fórmula para el número de personas necesarias para tener al menos una probabilidad de 1/2 de coincidir :

${\displaystyle n\geq {\tfrac {1}{2}}+{\sqrt {{\tfrac {1}{4}}+2\times \ln(2)\times 365}}=22.999943.}$

Esto es resultado de la buena aproximación de que un evento con una probabilidad de 1 / k tendrá una probabilidad de 1/2 de ocurrir al menos una vez si se repite k ln 2 veces. ^{[ 8 ]}

Las columnas más claras de esta tabla muestran la cantidad de hashes necesarios para alcanzar la probabilidad de colisión dada (columna), considerando un espacio de hash de un tamaño determinado en bits (fila). Siguiendo la analogía del cumpleaños: el "tamaño del espacio de hash" se asemeja a los "días disponibles", la "probabilidad de colisión" a la "probabilidad de compartir cumpleaños" y la "cantidad requerida de elementos hash" al "número requerido de personas en un grupo". Esta tabla también podría utilizarse para determinar el tamaño mínimo de hash requerido (dados los límites superiores de los hashes y la probabilidad de error), o la probabilidad de colisión (para una cantidad fija de hashes y una probabilidad de error determinada).

Para comparar,10 ⁻¹⁸ a10 ⁻¹⁵ es la tasa de error de bits no corregible de un disco duro típico. ^{[ 9 ]} En teoría, las funciones hash de 128 bits, como MD5 , deberían mantenerse dentro de ese rango hasta aproximadamente8,2 × 10¹¹ ^documentos , aunque sus posibles resultados sean muchos más.

Dado un año con d días, el problema generalizado del cumpleaños pide el número mínimo n ( d ) tal que, en un conjunto de n personas elegidas al azar, la probabilidad de una coincidencia de cumpleaños sea al menos del 50%. En otras palabras, n ( d ) es el entero mínimo n tal que

${\displaystyle 1-\left(1-{\frac {1}{d}}\right)\left(1-{\frac {2}{d}}\right)\cdots \left(1-{\frac {n-1}{d}}\right)\geq {\frac {1}{2}}.}$

El problema clásico del cumpleaños corresponde, por lo tanto, a determinar n (365) . Los primeros 99 valores de n ( d ) se dan aquí (secuencia A033810 en la OEIS ) :

Un cálculo similar muestra que n ( d ) = 23 cuando d está en el rango 341–372.

Se han publicado varios límites y fórmulas para n ( d ) . ^{[ 10 ]} Para cualquier d ≥ 1 , el número n ( d ) satisface ^{[ 11 ]}

${\displaystyle {\frac {3-2\ln 2}{6}}<n(d)-{\sqrt {2d\ln 2}}\leq 9-{\sqrt {86\ln 2}}.}$

Estos límites son óptimos en el sentido de que la secuencia n ( d ) − √ 2 d ln 2 se acerca arbitrariamente a

${\displaystyle {\frac {3-2\ln 2}{6}}\approx 0.27,}$

mientras que tiene

${\displaystyle 9-{\sqrt {86\ln 2}}\approx 1.28}$

como su máximo, tomado para d = 43 .

Los límites son suficientemente ajustados como para dar el valor exacto de n ( d ) en la mayoría de los casos. Por ejemplo, para d = 365, estos límites implican que 22,7633 < n (365) < 23,7736 y 23 es el único entero en ese rango. En general, de estos límites se deduce que n ( d ) siempre es igual a

${\displaystyle \left\lceil {\sqrt {2d\ln 2}}\,\right\rceil \quad {\text{or}}\quad \left\lceil {\sqrt {2d\ln 2}}\,\right\rceil +1}$

donde ⌈ · ⌉ denota la función techo . La fórmula

${\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}\,\right\rceil }$

Se cumple para el 73% de todos los enteros d . ^{[ 12 ]} La fórmula

${\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}\right\rceil }$

se cumple para casi todos los d , es decir, para un conjunto de enteros d con densidad asintótica 1. ^{[ 12 ]}

La fórmula

${\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}+{\frac {9-4(\ln 2)^{2}}{72{\sqrt {2d\ln 2}}}}\right\rceil }$

se cumple para todo d ≤10 ¹⁸ , pero se conjetura que existen infinitos contraejemplos a esta fórmula. ^{[ 13 ]}

La fórmula

${\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}+{\frac {9-4(\ln 2)^{2}}{72{\sqrt {2d\ln 2}}}}-{\frac {2(\ln 2)^{2}}{135d}}\right\rceil }$

se cumple para todo d ≤10 ¹⁸ , y se conjetura que esta fórmula se cumple para todo d . ^{[ 13 ]}

Es posible ampliar el problema para preguntar cuántas personas en un grupo son necesarias para que haya una probabilidad mayor al 50% de que al menos 3, 4, 5, etc., del grupo compartan el mismo cumpleaños.

Los primeros valores son los siguientes:

• >50% de probabilidad de que 3 personas compartan cumpleaños - 88 personas
• >50% de probabilidad de que 4 personas compartan cumpleaños: 187 personas (secuencia A014088 en el OEIS ) . ^{[ 14 ]}

El problema del cumpleaños fuerte pide el número de personas que deben reunirse para que haya un 50 % de probabilidad de que cada persona en la reunión comparta su cumpleaños con al menos otra persona. Para d = 365 días, la respuesta es 3064 personas. ^{[ 15 ] [ 16 ]}

El número de personas necesarias para un número arbitrario de días viene dado por (secuencia A380129 en el OEIS )

El problema del cumpleaños se puede generalizar de la siguiente manera:

Dados n enteros aleatorios extraídos de una distribución uniforme discreta con rango [1, d ] , ¿cuál es la probabilidad p ( n ; d ) de que al menos dos números sean iguales? ( d = 365 da el problema habitual del cumpleaños). ^{[ 17 ]}

Los resultados genéricos pueden obtenerse utilizando los mismos argumentos expuestos anteriormente.

${\displaystyle {\begin{aligned}p(n;d)&={\begin{cases}1-\displaystyle \prod _{k=1}^{n-1}\left(1-{\frac {k}{d}}\right)&n\leq d\\1&n>d\end{cases}}\\[8px]&\approx 1-e^{-{\frac {n(n-1)}{2d}}}\\&\approx 1-\left({\frac {d-1}{d}}\right)^{\frac {n(n-1)}{2}}\end{aligned}}}$

Por el contrario, si n ( p ; d ) denota el número de enteros aleatorios extraídos de [1, d ] para obtener una probabilidad p de que al menos dos números sean iguales, entonces

${\displaystyle n(p;d)\approx {\sqrt {2d\cdot \ln \left({\frac {1}{1-p}}\right)}}.}$

El problema del cumpleaños, en este sentido más genérico, se aplica a ^{las funciones} hash : el número esperado de hashes de N bits que se pueden generar antes de que se produzca una colisión no es 2ⁿ , sino solo 2ⁿ ^{/ 2} . Esto es aprovechado por los ataques de cumpleaños contra las funciones hash criptográficas y es la razón por la que, a efectos prácticos, un pequeño número de colisiones en una tabla hash es inevitable.

La teoría que subyace al problema del cumpleaños fue utilizada por Zoe Schnabel ^{[ 18 ]} bajo el nombre de estadística de captura-recaptura para estimar el tamaño de la población de peces en lagos. El problema del cumpleaños y sus generalizaciones también son herramientas útiles para modelar coincidencias. ^{[ 19 ]}

Generalización a múltiples tipos de personas

El problema básico considera que todos los ensayos son de un "tipo". El problema del cumpleaños se ha generalizado para considerar un número arbitrario de tipos. ^{[ 20 ]} En la extensión más simple hay dos tipos de personas, digamos m hombres y n mujeres, y el problema se convierte en caracterizar la probabilidad de que al menos un hombre y una mujer compartan su cumpleaños. (Los cumpleaños compartidos entre dos hombres o dos mujeres no cuentan). La probabilidad de que no haya cumpleaños compartidos aquí es

${\displaystyle p_{0}={\frac {1}{d^{m+n}}}\sum _{i=1}^{m}\sum _{j=1}^{n}S_{2}(m,i)S_{2}(n,j)\prod _{k=0}^{i+j-1}d-k}$

donde d = 365 y S ₂ son números de Stirling de segundo tipo . En consecuencia, la probabilidad deseada es 1 − p ₀ .

Esta variante del problema del cumpleaños es interesante porque no existe una solución única para el número total de personas m + n . Por ejemplo, el valor de probabilidad habitual del 50 % se cumple tanto para un grupo de 32 miembros (16 hombres y 16 mujeres) como para un grupo de 49 miembros (43 mujeres y 6 hombres).

Una pregunta relacionada es: a medida que las personas entran en una habitación de una en una, ¿quién tiene más probabilidades de ser la primera en tener el mismo cumpleaños que alguien que ya está en la habitación? Es decir, ¿para qué n es máximo p ( n ) - p ( n  -  1) ? La respuesta es 20; si hay un premio para el primer acierto, la mejor posición en la fila es la número 20.

En el problema del cumpleaños, ninguna de las dos personas es elegida de antemano. Por el contrario, la probabilidad q ( n ) de que al menos otra persona en una habitación con n personas tenga el mismo cumpleaños que una persona en particular (por ejemplo, usted) viene dada por

${\displaystyle q(n)=1-\left({\frac {365-1}{365}}\right)^{n}}$

y para general d por

${\displaystyle q(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}.}$

En el caso estándar de d = 365 , al sustituir n = 23 se obtiene aproximadamente un 6,1%, lo que representa menos de 1 posibilidad entre 16. Para que haya más de un 50% de probabilidad de que al menos otra persona en una habitación con n personas tenga el mismo cumpleaños que tú , n tendría que ser al menos 253. Este número es significativamente mayor que 365 / 2 = 182,5 : la razón es que es probable que haya algunas coincidencias de cumpleaños entre las demás personas en la habitación .

Para cualquier persona en un grupo de n personas, la probabilidad de que comparta su cumpleaños con otra persona es${\displaystyle q(n-1;d)}$, como se explicó anteriormente. El número esperado de personas con un cumpleaños compartido (no único) ahora se puede calcular fácilmente multiplicando esa probabilidad por el número de personas ( n ), por lo que queda:

${\displaystyle n\left(1-\left({\frac {d-1}{d}}\right)^{n-1}\right)}$

(Esta multiplicación se puede realizar de esta manera debido a la linealidad del valor esperado de las variables indicadoras). Esto implica que el número esperado de personas con un cumpleaños no compartido (único) es:

${\displaystyle n\left({\frac {d-1}{d}}\right)^{n-1}}$

Se pueden derivar fórmulas similares para el número esperado de personas que comparten con otras tres, cuatro, etc.

El número esperado de personas necesarias para que se cumpla cada cumpleaños se conoce como el problema del coleccionista de cupones . Se puede calcular mediante nH _n , donde H _n es el n -ésimo número armónico . Para 365 fechas posibles (el problema del cumpleaños), la respuesta es 2365.

Otra generalización consiste en preguntar por la probabilidad de encontrar al menos un par en un grupo de n personas cuyos cumpleaños estén separados por k días calendario, si hay d cumpleaños igualmente probables. ^{[ 21 ]}

${\displaystyle {\begin{aligned}p(n,k,d)&=1-{\frac {(d-nk-1)!}{d^{n-1}{\bigl (}d-n(k+1){\bigr )}!}}\end{aligned}}}$

El número de personas necesarias para que la probabilidad de que un par de personas tengan un cumpleaños separado por k días o menos sea superior al 50% se muestra en la siguiente tabla:

Así, en un grupo de tan solo siete personas elegidas al azar, es más probable que dos de ellas cumplan años con una semana de diferencia. ^{[ 21 ]}

La probabilidad de que el k -ésimo entero elegido al azar de [1, d ] repita al menos una elección anterior es igual a q ( k − 1; d ) arriba. El número total esperado de veces que una selección repetirá una selección anterior cuando se eligen n de esos enteros es igual a ^{[ 22 ].}

${\displaystyle \sum _{k=1}^{n}q(k-1;d)=n-d+d\left({\frac {d-1}{d}}\right)^{n}}$

Esto puede considerarse igual al número de personas menos el número esperado de cumpleaños diferentes.

La distribución de la variable aleatoria que informa el número k de enteros que deben elegirse para obtener exactamente c repeticiones (para una c constante ) converge a una variable aleatoria con distribución chi cuando${\displaystyle d\to \infty }$. ^{[ 23 ]}

En una formulación alternativa del problema del cumpleaños, se pregunta por el número promedio de personas necesarias para encontrar una pareja con el mismo cumpleaños. Si consideramos la función de probabilidad Pr[ n personas tienen al menos un cumpleaños en común], este promedio determina la media de la distribución, a diferencia de la formulación habitual, que pregunta por la mediana . El problema es relevante para varios algoritmos de hash analizados por Donald Knuth en su libro El arte de la programación informática . Se puede demostrar ^{[ 24 ] [ 25 ]} que si se muestrea uniformemente, con reemplazo, de una población de tamaño M , el número de ensayos requeridos para el primer muestreo repetido de algún individuo tiene un valor esperado n = 1 + Q ( M ) , donde

${\displaystyle Q(M)=\sum _{k=1}^{M}{\frac {M!}{(M-k)!M^{k}}}.}$

La función

${\displaystyle Q(M)=1+{\frac {M-1}{M}}+{\frac {(M-1)(M-2)}{M^{2}}}+\cdots +{\frac {(M-1)(M-2)\cdots 1}{M^{M-1}}}}$

Ha sido estudiado por Srinivasa Ramanujan y tiene una expansión asintótica :

${\displaystyle Q(M)\sim {\sqrt {\frac {\pi M}{2}}}-{\frac {1}{3}}+{\frac {1}{12}}{\sqrt {\frac {\pi }{2M}}}-{\frac {4}{135M}}+\cdots .}$

Con M = 365 días en un año, el número promedio de personas necesarias para encontrar una pareja con el mismo cumpleaños es n = 1 + Q ( M ) ≈ 24,61659 , algo más que 23, el número necesario para una probabilidad del 50%. En el mejor de los casos, dos personas serán suficientes; en el peor, se necesita el número máximo posible de M + 1 = 366 personas; pero en promedio, solo se requieren 25 personas.

Un análisis que utiliza variables aleatorias indicadoras puede proporcionar un análisis más simple pero aproximado de este problema. ^{[ 26 ]} Para cada par ( i , j ) de k personas en una habitación, definimos la variable aleatoria indicadora X _ij , para${\displaystyle 1\leq i\leq j\leq k}$, por

$${\displaystyle {\begin{alignedat}{2}X_{ij}&=I\{{\text{person }}i{\text{ and person }}j{\text{ have the same birthday}}\}\\[10pt]&={\begin{cases}1,&{\text{if person }}i{\text{ and person }}j{\text{ have the same birthday;}}\\0,&{\text{otherwise.}}\end{cases}}\end{alignedat}}}$$

$${\displaystyle {\begin{alignedat}{2}E[X_{ij}]&=\Pr\{{\text{person }}i{\text{ and person }}j{\text{ have the same birthday}}\}={\frac {1}{n}}.\end{alignedat}}}$$

Sea X una variable aleatoria que cuenta los pares de individuos con el mismo cumpleaños.

$${\displaystyle X=\sum _{i=1}^{k}\sum _{j=i+1}^{k}X_{ij}}$$

$${\displaystyle {\begin{alignedat}{3}E[X]&=\sum _{i=1}^{k}\sum _{j=i+1}^{k}E[X_{ij}]\\[8pt]&={\binom {k}{2}}{\frac {1}{n}}\\[8pt]&={\frac {k(k-1)}{2n}}\end{alignedat}}}$$

Para n = 365 , si k = 28 , el número esperado de pares de individuos con el mismo cumpleaños es ⁠ 28 × 27 / 2 × 365 ⁠ ≈ 1,0356. Por lo tanto, podemos esperar al menos un par coincidente con al menos 28 personas.  

En la Copa Mundial de la FIFA 2014 , cada una de las 32 selecciones contaba con 23 jugadores. Un análisis de las listas oficiales de las selecciones sugirió que 16 selecciones tenían parejas de jugadores que compartían cumpleaños, y de estas, 5 selecciones tenían dos parejas: Argentina, Francia, Irán, Corea del Sur y Suiza tenían dos parejas cada una, y Australia, Bosnia y Herzegovina, Brasil, Camerún, Colombia, Honduras, Países Bajos, Nigeria, Rusia, España y Estados Unidos tenían una pareja cada una. ^{[ 27 ]}

Voracek, Tran y Formann demostraron que la mayoría de las personas sobreestiman notablemente el número de personas necesarias para lograr una probabilidad dada de que las personas tengan el mismo cumpleaños, y subestiman notablemente la probabilidad de que las personas tengan el mismo cumpleaños cuando se da un tamaño de muestra específico. ^{[ 28 ]} Otros resultados mostraron que los estudiantes de psicología y las mujeres obtuvieron mejores resultados en la tarea que los visitantes/empleados de casinos o los hombres, pero tenían menos confianza en sus estimaciones.