Problema de cumpleaños

En teoría de la probabilidad , el problema del cumpleaños plantea la probabilidad de que, en un conjunto de n personas elegidas al azar , al menos dos compartan cumpleaños . La paradoja del cumpleaños se refiere al hecho contraintuitivo de que solo se necesitan 23 personas para que esa probabilidad supere el 50%.

La paradoja del cumpleaños es una paradoja verídica : parece errónea a primera vista, pero, de hecho, es cierta. Si bien puede parecer sorprendente que solo se requieran 23 individuos para alcanzar una probabilidad del 50% de un cumpleaños compartido, este resultado se vuelve más intuitivo al considerar que las comparaciones de cumpleaños se realizarán entre cada par posible de individuos. Con 23 individuos, hay ⁠23 × 22/2⁠  = 253 pares a considerar, mucho más de la mitad del número de días de un año.

Las aplicaciones en el mundo real del problema del cumpleaños incluyen un ataque criptográfico llamado ataque de cumpleaños , que utiliza este modelo probabilístico para reducir la complejidad de encontrar una colisión para una función hash , así como para calcular el riesgo aproximado de que exista una colisión hash dentro de los hashes de un tamaño determinado de población.

El problema se atribuye generalmente a Harold Davenport en 1927 aproximadamente, aunque no lo publicó en ese momento. Davenport no afirmó ser su descubridor "porque no podía creer que no se hubiera planteado antes". ^{[1] [2]} La primera publicación de una versión del problema del cumpleaños fue obra de Richard von Mises en 1939. ^[3]

Desde una perspectiva de permutaciones , sea el evento A la probabilidad de encontrar un grupo de 23 personas sin ningún cumpleaños repetido. Donde el evento B es la probabilidad de encontrar un grupo de 23 personas con al menos dos personas compartiendo el mismo cumpleaños, P ( B ) = 1 − P ( A ) . P ( A ) es la razón del número total de cumpleaños, , sin repeticiones y el orden importa (por ejemplo, para un grupo de 2 personas, formato de cumpleaños mm/dd, un resultado posible es ) dividido por el número total de cumpleaños con repetición y el orden importa, , ya que es el espacio total de resultados del experimento (por ejemplo, 2 personas, un resultado posible es ). Por lo tanto y son permutaciones . $Estilo de visualización V_{nr}$${\displaystyle \left\{\left\{01/02,05/20\right\},\left\{05/20,01/02\right\},\left\{10/02,08/04\right\},...\right\}}$$Estilo de visualización Vt$${\displaystyle \left\{\left\{01/02,01/02\right\},\left\{10/02,08/04\right\},...\right\}}$$Estilo de visualización V_{nr}$$Estilo de visualización Vt$

${\displaystyle {\begin{aligned}V_{nr}&={\frac {n!}{(nk)!}}={\frac {365!}{(365-23)!}}\\[8pt]V_{t}&=n^{k}=365^{23}\\[8pt]P(A)&={\frac {V_{nr}}{V_{t}}}\aproximadamente 0,492703\\[8pt]P(B)&=1-P(A)\aproximadamente 1-0,492703\aproximadamente 0,507297\cuadrado (50,7297\%)\end{aligned}}}$

Otra forma de resolver el problema del cumpleaños es preguntando por la probabilidad aproximada de que en un grupo de n personas al menos dos tengan el mismo cumpleaños. Para simplificar, generalmente se descartan los años bisiestos , los gemelos , el sesgo de selección y las variaciones estacionales y semanales en las tasas de natalidad ^[4] y, en su lugar, se supone que hay 365 cumpleaños posibles y que el cumpleaños de cada persona tiene la misma probabilidad de ser cualquiera de estos días, independientemente de las otras personas del grupo.

En el caso de cumpleaños independientes, una distribución uniforme de cumpleaños minimiza la probabilidad de que dos personas de un grupo tengan el mismo cumpleaños. Cualquier desigualdad aumenta la probabilidad de que dos personas compartan cumpleaños. ^{[5] [6]} Sin embargo, los cumpleaños del mundo real no son lo suficientemente desiguales como para generar grandes cambios: el tamaño del grupo del mundo real necesario para tener una probabilidad mayor del 50 % de un cumpleaños compartido es 23, como en la distribución uniforme teórica. ^[7]

El objetivo es calcular P ( B ) , la probabilidad de que al menos dos personas en la sala tengan el mismo cumpleaños. Sin embargo, es más sencillo calcular P ( A ′) , la probabilidad de que no haya dos personas en la sala que tengan el mismo cumpleaños. Entonces, como B y A ′ son las únicas dos posibilidades y también son mutuamente excluyentes , P ( B ) = 1 − P ( A ′).

Aquí está el cálculo de P ( B ) para 23 personas. Sean las 23 personas numeradas del 1 al 23. El evento de que las 23 personas tengan diferentes cumpleaños es el mismo que el evento de que la persona 2 no tenga el mismo cumpleaños que la persona 1, y que la persona 3 no tenga el mismo cumpleaños que la persona 1 o la persona 2, y así sucesivamente, y finalmente que la persona 23 no tenga el mismo cumpleaños que ninguna de las personas 1 a 22. Sean estos eventos llamados Evento 2, Evento 3, y así sucesivamente. El Evento 1 es el evento de que la persona 1 tenga un cumpleaños, lo que ocurre con probabilidad 1. Esta conjunción de eventos puede calcularse utilizando probabilidad condicional : la probabilidad del Evento 2 es ⁠364/365⁠ , ya que la persona 2 puede tener cualquier cumpleaños que no sea el cumpleaños de la persona 1. De manera similar, la probabilidad del Evento 3 dado que ocurrió el Evento 2 es ⁠363/365⁠ , ya que la persona 3 puede tener cualquiera de los cumpleaños que no hayan tenido ya las personas 1 y 2. Esto continúa hasta que finalmente la probabilidad del Evento 23 dado que ocurrieron todos los eventos anteriores es ⁠343/365⁠ . Finalmente, el principio de probabilidad condicional implica que P ( A ′) es igual al producto de estas probabilidades individuales:

Los términos de la ecuación ( 1 ) se pueden reunir para llegar a:

Evaluando la ecuación ( 2 ) se obtiene P ( A ′) ≈ 0,492703

Por lo tanto, P ( B ) ≈ 1 − 0,492703 = 0,507297  (50,7297%).

Este proceso se puede generalizar a un grupo de n personas, donde p ( n ) es la probabilidad de que al menos dos de las n personas compartan cumpleaños. Es más fácil calcular primero la probabilidad p ( n ) de que todos los n cumpleaños sean diferentes . Según el principio del palomar , p ( n ) es cero cuando n > 365. Cuando n  ≤ 365 :

${\displaystyle {\begin{aligned}{\bar {p}}(n)&=1\times \left(1-{\frac {1}{365}}\right)\times \left(1-{\frac {2}{365}}\right)\times \cdots \times \left(1-{\frac {n-1}{365}}\right)\\[6pt]&={\frac {365\times 364\times \cdots \times (365-n+1)}{365^{n}}}\\[6pt]&={\frac {365!}{365^{n}(365-n)!}}={\frac {n!\cdot {\binom {365}{n}}}{365^{n}}}={\frac {_{365}P_{n}}{365^{n}}}\end{alineado}}}$

donde ! es el operador factorial , (³⁶⁵
_n) es el coeficiente binomial y _k P _r denota permutación .

La ecuación expresa el hecho de que la primera persona no tiene con quién compartir cumpleaños, la segunda persona no puede tener el mismo cumpleaños que la primera ( ⁠364/365⁠ ) ​​, el tercero no puede tener el mismo cumpleaños que ninguno de los dos primeros ( ⁠363/365⁠ ) ​​y, en general, eln-ésimo cumpleaños no puede ser el mismo que ninguno de los n − 1cumpleaños anteriores.

El evento de que al menos dos de las n personas tengan el mismo cumpleaños es complementario a que todos los n cumpleaños sean diferentes. Por lo tanto, su probabilidad p ( n ) es

${\displaystyle p(n)=1-{\bar {p}}(n).}$

La siguiente tabla muestra la probabilidad de algunos otros valores de n (para esta tabla, se ignora la existencia de años bisiestos y se supone que cada cumpleaños es igualmente probable):

La expansión en serie de Taylor de la función exponencial (la constante e ≈2.718 281 828 )

${\displaystyle e^{x}=1+x+{\frac {x^{2}}{2!}}+\cdots }$

proporciona una aproximación de primer orden para e ^x para : ${\displaystyle |x|\ll 1}$

${\displaystyle e^{x}\approx 1+x.}$

Para aplicar esta aproximación a la primera expresión derivada para p ( n ) , establezca x = − ⁠a/365⁠ . Por lo tanto,

${\displaystyle e^{-a/365}\approx 1-{\frac {a}{365}}.}$

Luego, reemplace a con números enteros no negativos para cada término en la fórmula de p ( n ) hasta que a = n − 1 , por ejemplo, cuando a = 1 ,

${\displaystyle e^{-1/365}\approx 1-{\frac {1}{365}}.}$

La primera expresión derivada para p ( n ) se puede aproximar como

${\displaystyle {\begin{aligned}{\bar {p}}(n)&\approx 1\cdot e^{-1/365}\cdot e^{-2/365}\cdots e^{-(n-1)/365}\\[6pt]&=e^{-{\big (}1+2+\,\cdots \,+(n-1){\big )}/365}\\[6pt]&=e^{-{\frac {n(n-1)/2}{365}}}=e^{-{\frac {n(n-1)}{730}}}.\end{aligned}}}$

Por lo tanto,

${\displaystyle p(n)=1-{\bar {p}}(n)\approx 1-e^{-{\frac {n(n-1)}{730}}}.}$

Una aproximación aún más burda se da mediante

${\displaystyle p(n)\approx 1-e^{-{\frac {n^{2}}{730}}},}$

lo cual, como ilustra el gráfico, sigue siendo bastante exacto.

Según la aproximación, el mismo enfoque se puede aplicar a cualquier número de "personas" y "días". Si en lugar de 365 días hay d , si hay n personas, y si n ≪ d , entonces utilizando el mismo enfoque que antes obtenemos el resultado de que si p ( n , d ) es la probabilidad de que al menos dos de n personas compartan el mismo cumpleaños de un conjunto de d días disponibles, entonces:

${\displaystyle {\begin{aligned}p(n,d)&\approx 1-e^{-{\frac {n(n-1)}{2d}}}\\[6pt]&\approx 1-e^{-{\frac {n^{2}}{2d}}}.\end{aligned}}}$

La probabilidad de que dos personas no tengan el mismo cumpleaños es364/365En una habitación que contiene n personas, hay (^número
₂) = ⁠n ( n - 1)/2⁠ pares de personas, es decir (^número
₂) eventos. La probabilidad de que no haya dos personas que compartan el mismo cumpleaños se puede aproximar suponiendo que estos eventos son independientes y, por lo tanto, multiplicando su probabilidad entre sí. Ser independiente equivaldría a elegir con reemplazo cualquier par de personas en el mundo, no solo en una habitación. En resumen364/365⁠ se puede multiplicar por sí mismo (^número
₂) 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 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 el binomio en el 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 superior al 50% de las descripciones anteriores. Esta aproximación es la misma que la anterior basada en la expansión de Taylor que utiliza 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)}}}$

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

Por ejemplo, para estimar el número de personas necesarias para un ⁠1/2⁠ posibilidad de un cumpleaños compartido, 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 un ⁠1/2⁠ probabilidad de coincidencia:

${\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 que tiene un evento con ⁠1/a⁠ La probabilidad tendrá una ⁠1/2⁠ probabilidad de que ocurra al menos una vez si se repite k ln 2 veces. ^[8]

Los campos más claros de esta tabla muestran la cantidad de hashes necesarios para lograr la probabilidad de colisión dada (columna) dado un espacio hash de un tamaño determinado en bits (fila). Usando la analogía del cumpleaños: el "tamaño del espacio hash" se asemeja a los "días disponibles", la "probabilidad de colisión" se asemeja a la "probabilidad de cumpleaños compartido" y la "cantidad requerida de elementos hash" se asemeja a la "cantidad requerida de personas en un grupo". También se podría usar este gráfico 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 la probabilidad de error).

A modo de comparación,10 ⁻¹⁸ a10 ⁻¹⁵ es la tasa de error de bits incorregible de un disco duro típico. ^[9] En teoría, las funciones hash de 128 bits, como MD5 , deberían permanecer dentro de ese rango hasta aproximadamente8,2 × 10 ¹¹ documentos, aunque sus posibles salidas son muchas más.

El argumento que sigue es una adaptación de un argumento de Paul Halmos . ^{[nb 1]}

Como se indicó anteriormente, la probabilidad de que no coincidan dos cumpleaños es

${\displaystyle 1-p(n)={\bar {p}}(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}}\right).}$

Como en los párrafos anteriores, el interés reside en el n más pequeño tal que p ( n ) > ⁠1/2⁠ ; o equivalentemente, el n más pequeño tal que p ( n ) < ⁠1/2⁠ .

Usando la desigualdad 1 − x < e ^{− x} en la expresión anterior reemplazamos 1 − ⁠a/365⁠ con e ^{− k ⁄ 365} . Esto produce

${\displaystyle {\bar {p}}(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}}\right)<\prod _{k=1}^{n-1}\left(e^{-{\frac {k}{365}}}\right)=e^{-{\frac {n(n-1)}{730}}}.}$

Por lo tanto, la expresión anterior no es sólo una aproximación, sino también un límite superior de p ( n ) . La desigualdad

${\displaystyle e^{-{\frac {n(n-1)}{730}}}<{\frac {1}{2}}}$

implica p ( n ) < ⁠1/2⁠ . Resolviendo para n obtenemos

${\displaystyle n^{2}-n>730\ln 2.}$

Ahora bien, 730 ln 2 es aproximadamente 505,997, que es apenas inferior a 506, el valor de n ² − n obtenido cuando n = 23. Por lo tanto, bastan 23 personas. Por cierto, al resolver n ² − n = 730 ln 2 para n se obtiene la fórmula aproximada de Frank H. Mathis citada anteriormente.

Esta derivación solo muestra que se necesitan como máximo 23 personas para garantizar que las posibilidades de una coincidencia de cumpleaños sean al menos iguales; deja abierta la posibilidad de que n sea 22 o menos, lo que también podría funcionar.

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 entonces a la determinación de 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 lo suficientemente estrictos 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 números 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 números 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 todos los d ≤10 ¹⁸ , pero se conjetura que hay infinitos contraejemplos de 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 todos los d ≤10 ¹⁸ , y se conjetura que esta fórmula es válida para todo d . ^[13]

Es posible ampliar el problema para preguntar cuántas personas de un grupo son necesarias para que haya una probabilidad mayor del 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 un cumpleaños: 88 personas; >50% de probabilidad de que 4 personas compartan un cumpleaños: 187 personas (secuencia A014088 en la OEIS ). ^[14]

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

Dados n números 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 de cumpleaños habitual). ^[15]

Los resultados genéricos se pueden derivar utilizando los mismos argumentos dados 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 números 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 obtener una colisión no es 2 ^N , sino solo 2 ^{N ⁄ 2.} Esto es explotado por ataques de cumpleaños en funciones hash criptográficas y es la razón por la que una pequeña cantidad de colisiones en una tabla hash son, para todos los fines prácticos, inevitables.

La teoría detrás del problema del cumpleaños fue utilizada por Zoe Schnabel ^[16] bajo el nombre de estadísticas de captura-recaptura para estimar el tamaño de la población de peces en los lagos.

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. ^[17] En la extensión más simple hay dos tipos de personas, digamos m hombres y n mujeres, y el problema pasa a caracterizar la probabilidad de un cumpleaños compartido entre al menos un hombre y una mujer. (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 segunda especie . En consecuencia, la probabilidad deseada es 1 − p ₀ .

Esta variación 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 de 16 hombres y 16 mujeres como para un grupo de 49 miembros de 43 mujeres y 6 hombres.

Una pregunta relacionada es, cuando las personas entran en una habitación de a una, ¿cuál es más probable que sea el primero en tener el mismo cumpleaños que alguien que ya está en la habitación? Es decir, ¿para qué n es p ( n ) − p ( n  − 1) máximo? La respuesta es 20: si hay un premio para el primer partido, la mejor posición en la fila es la vigésima. ^{[ cita requerida ]}

En el problema del cumpleaños, ninguna de las dos personas se elige de antemano. Por el contrario, la probabilidad q ( n ) de que al menos otra persona en una sala con n personas tenga el mismo cumpleaños que una persona en particular (por ejemplo, usted) está 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 6,1%, lo que es menos de 1 probabilidad en 16. Para una probabilidad mayor del 50% de que al menos otra persona en una sala llena de 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 otras personas en la sala.

Para cualquier persona de un grupo de n personas, la probabilidad de que comparta su cumpleaños con otra persona es , 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 es: ${\displaystyle q(n-1;d)}$

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

(Esta multiplicación se puede hacer 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. personas.

El número esperado de personas necesarias hasta que se cumpla cada cumpleaños se denomina 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 es preguntar por la probabilidad de encontrar al menos un par en un grupo de n personas con cumpleaños dentro de k días calendario entre sí, si hay d cumpleaños igualmente probables. ^[18]

${\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 alguna pareja tenga un cumpleaños separado por k días o menos sea mayor del 50% se da en la siguiente tabla:

Por lo tanto, en un grupo de sólo siete personas elegidas al azar, es más probable que dos de ellas tengan su cumpleaños con una semana de diferencia. ^[18]

El número esperado de cumpleaños diferentes, es decir, el número de días en los que al menos una persona cumple años, es:

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

Esto se desprende del número esperado de días en los que no hay cumpleaños de nadie:

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

lo que se deduce de la probabilidad de que un día determinado no sea el cumpleaños de nadie, ( ⁠re -1/d⁠ )^norte
 , fácilmente resumible debido a la linealidad del valor esperado.

Por ejemplo, con d = 365 , debería esperar aproximadamente 21 cumpleaños diferentes cuando hay 22 personas, o 46 cumpleaños diferentes cuando hay 50 personas. Cuando hay 1000 personas, habrá alrededor de 341 cumpleaños diferentes (24 cumpleaños no reclamados).

Lo anterior se puede generalizar a partir de la distribución del número de personas que cumplen años en un día determinado, que es una distribución binomial con probabilidad ⁠1/d⁠ . Al multiplicar la probabilidad relevante por d se obtendrá el número esperado de días. Por ejemplo, el número esperado de días que se comparten, es decir, que son los cumpleaños de al menos dos personas (es decir, ni cero ni una) es:

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

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

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

Se puede ver que esto es igual al número de personas menos el número esperado de cumpleaños diferentes.

En una formulación alternativa del problema del cumpleaños, se pregunta 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 compartido], este promedio determina la media de la distribución, a diferencia de la formulación habitual, que pide la mediana . El problema es relevante para varios algoritmos de hash analizados por Donald Knuth en su libro The Art of Computer Programming . Se puede demostrar ^{[20] [21]} que si se realiza un muestreo uniforme, con reemplazo, de una población de tamaño M , el número de ensayos necesarios 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 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, bastarán dos personas; en el peor, se necesita el máximo número posible de M + 1 = 366 personas; pero en promedio, solo se requieren 25 personas.

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

$${\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 es28 × 27/2 × 365⁠  ≈ 1.0356. Por lo tanto, podemos esperar al menos una pareja coincidente con al menos 28 personas.

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

Voracek, Tran y Formann demostraron que la mayoría de las personas sobreestiman notablemente la cantidad 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. ^[24] Otros resultados mostraron que los estudiantes de psicología y las mujeres obtuvieron mejores resultados en la tarea que los visitantes/personal del casino o los hombres, pero estaban menos seguros de sus estimaciones.

El problema inverso es encontrar, para una probabilidad fija p , el n mayor para el cual la probabilidad p ( n ) es menor que la p dada , o el n menor para el cual la probabilidad p ( n ) es mayor que la p dada . ^{[ cita requerida ]}

Tomando la fórmula anterior para d  = 365 , se tiene

${\displaystyle n(p;365)\approx {\sqrt {730\ln \left({\frac {1}{1-p}}\right)}}.}$

La siguiente tabla ofrece algunos ejemplos de cálculos.

Algunos valores que quedan fuera de los límites se han coloreado para mostrar que la aproximación no siempre es exacta.

Un problema relacionado es el problema de la partición , una variante del problema de la mochila de la investigación de operaciones . Se colocan algunas pesas en una balanza ; cada pesa es un número entero de gramos elegidos al azar entre un gramo y un millón de gramos (una tonelada ). La pregunta es si uno puede generalmente (es decir, con una probabilidad cercana a 1) transferir las pesas entre los brazos izquierdo y derecho para equilibrar la balanza. (En caso de que la suma de todas las pesas sea un número impar de gramos, se permite una discrepancia de un gramo). Si solo hay dos o tres pesas, la respuesta es claramente no; aunque hay algunas combinaciones que funcionan, la mayoría de las combinaciones seleccionadas aleatoriamente de tres pesas no lo hacen. Si hay muchas pesas, la respuesta es claramente sí. La pregunta es, ¿cuántas son suficientes? Es decir, ¿cuál es el número de pesas tal que es igualmente probable que sea posible equilibrarlas como que sea imposible?

A menudo, la intuición de la gente es que la respuesta está arriba.100 000. La intuición de la mayoría de las personas es que se trata de miles o decenas de miles, mientras que otros creen que debería ser al menos de cientos. La respuesta correcta es 23. ^{[ cita requerida ]}

La razón es que la comparación correcta es con el número de particiones de los pesos en izquierda y derecha. Hay 2 ^{N − 1} particiones diferentes para N pesos, y la suma izquierda menos la suma derecha se puede considerar como una nueva cantidad aleatoria para cada partición. La distribución de la suma de pesos es aproximadamente gaussiana , con un pico en500 000 N y ancho1 000 000 √ N , de modo que cuando 2 ^{N − 1} es aproximadamente igual a1 000 000 √ N se produce la transición. 2 ^{23 − 1} es aproximadamente 4 millones, mientras que el ancho de la distribución es de solo 5 millones. ^[25]

La novela de Arthur C. Clarke de 1961, A Fall of Moondust, contiene una sección en la que los personajes principales, atrapados bajo tierra durante un tiempo indefinido, celebran un cumpleaños y se encuentran discutiendo la validez del problema del cumpleaños. Como afirma un pasajero físico: "Si tienes un grupo de más de veinticuatro personas, las probabilidades son mejores que incluso de que dos de ellas tengan el mismo cumpleaños". Finalmente, de los 22 presentes, se revela que dos personajes comparten el mismo cumpleaños, el 23 de mayo.

• Abramson, M.; Moser, WOJ (1970). "Más sorpresas de cumpleaños". American Mathematical Monthly . 77 (8): 856–858. doi :10.2307/2317022. JSTOR  2317022.
• Bloom, D. (1973). "Un problema de cumpleaños". American Mathematical Monthly . 80 (10): 1141–1142. doi :10.2307/2318556. JSTOR  2318556.
• Kemeny, John G.; Snell, J. Laurie; Thompson, Gerald (1957). Introducción a las matemáticas finitas (Primera edición).
• McKinney, EH (1966). "Problema de cumpleaños generalizado". American Mathematical Monthly . 73 (5): 385–387. doi :10.2307/2315408. JSTOR  2315408.
• Mosteller, F. (1962). "Entendiendo el problema del cumpleaños". The Mathematics Teacher . 55 (5): 322–325. doi :10.5951/MT.55.5.0322. JSTOR  27956609.Reimpreso en Mosteller, Frederick (2006). "Entender el problema del cumpleaños". Artículos seleccionados de Frederick Mosteller . Springer Series in Statistics. págs. 349–353. doi :10.1007/978-0-387-44956-2_21. ISBN 978-0-387-20271-6.
• Schneps, Leila ; Colmez, Coralie (2013). "Error matemático número 5. El caso de Diana Sylvester: análisis de impacto en frío". Matemáticas en juicio. Cómo se usan y abusan los números en los tribunales . Libros básicos. ISBN 978-0-465-03292-1.
• Sy M. Blinder (2013). Guía de matemáticas esenciales: una revisión para estudiantes de física, química e ingeniería. Elsevier. págs. 5-6. ISBN 978-0-12-407163-6.

• La paradoja del cumpleaños que explica los cumpleaños en años bisiestos
• Weisstein, Eric W. "Problema de cumpleaños". MundoMatemático .
• Un artículo humorístico que explica la paradoja.
• Actividades de SOCR EduMaterials experimento de cumpleaños
• Entendiendo el problema del cumpleaños (mejor explicado)
• Cumpleaños de la Eurocopa 2012. Un problema de cumpleaños. Un ejemplo práctico de la paradoja del cumpleaños en el fútbol.
• Grime, James. «23: Birthday Probability». Numberphile . Brady Haran . Archivado desde el original el 25 de febrero de 2017. Consultado el 2 de abril de 2013 .
• Cálculo de las probabilidades del problema del cumpleaños en WolframAlpha