Problema de cumpleaños

ImprimirCitar

Problema matemático

La probabilidad computarizada de al menos dos personas compartiendo un cumpleaños versus el número de personas

En la teoría de la probabilidad, el problema del cumpleaños pregunta por la probabilidad de que, en un conjunto de $n$ personas elegidas al azar, al menos dos compartirán cumpleaños. La paradoja del cumpleaños se refiere al hecho contrario a la intuición 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 incorrecta a primera vista pero, de hecho, es cierta. Si bien puede parecer sorprendente que solo se requieran 23 personas para alcanzar una probabilidad del 50 % de un cumpleaños compartido, este resultado se hace más intuitivo al considerar que las comparaciones de cumpleaños se realizarán entre cada posible par de personas. Con 23 personas, hay 23 × 22/ 2 = 253 pares a considerar, mucho más de la mitad de la cantidad de días en un año.

Las aplicaciones del mundo real para el 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, además de calcular el riesgo aproximado de una colisión hash existente. dentro de los hashes de un tamaño dado de población.

El problema generalmente se atribuye a Harold Davenport alrededor de 1927, aunque no lo publicó en ese momento. Davenport no afirmó ser su descubridor 'porque no podía creer que no se hubiera dicho antes'. La primera publicación de una versión del problema del cumpleaños fue de Richard von Mises en 1939.

Calcular la probabilidad

Desde una perspectiva de permutaciones, deja que el evento $A$ ser 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 relación del número total de cumpleaños, ${displaystyle V_{nr}}$ , sin repeticiones y asuntos de orden (por ejemplo, para un grupo de 2 personas, formato de cumpleaños mm/dd, un posible resultado es ${displaystyle left{left{01/02,05/20right},left{05/20,01/02right},left{10/02,08/04right},...right}}$ dividido por el número total de cumpleaños con repeticiones y asuntos de orden, $V_{t}$ , ya que es el espacio total de resultados del experimento (por ejemplo, 2 personas, un resultado posible es ${displaystyle left{left{01/02,01/02right},left{10/02,08/04right},...right}}$ . Por lo tanto ${displaystyle V_{nr}}$ y $V_{t}$ son permutaciones.

{displaystyle {begin{aligned}V_{nr}&={frac {n!}{(n-k)!}}={frac {365!}{(365-23)!}}\V_{t}&=n^{k}=365^{23}\P(A)&={frac {V_{nr}}{V_{t}}}approx 0.492703\P(B)&=1-P(A)approx 1-0.492703approx 0.507297(50.7297%)end{aligned}}}

Otra forma de resolver el problema del cumpleaños es preguntando por una probabilidad aproximada de que en un grupo de $n$ personas al menos dos tienen el mismo cumpleaños. Para simplificar, los años bisiestos, los gemelos, el sesgo de selección y las variaciones estacionales y semanales en las tasas de natalidad generalmente se descartan y, en cambio, se supone que hay 365 cumpleaños posibles y que es igualmente probable que el cumpleaños de cada persona sea cualquiera. de estos días, independiente de las demás personas del grupo. Para cumpleaños independientes, la distribución uniforme de cumpleaños es la distribución que minimiza la probabilidad de que dos personas tengan el mismo cumpleaños; cualquier desnivel aumenta esta probabilidad. Murray Klamkin abordó por primera vez el problema de un número no uniforme de nacimientos durante cada día del año en 1967. Da la casualidad de que la distribución del mundo real produce un tamaño crítico de 23 para alcanzar el 50%.

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

Este es el cálculo de $P (A)$ para 23 personas. Deje que las 23 personas se enumeren 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 cualquiera persona 1 o persona 2, y así sucesivamente, y finalmente esa persona 23 no tiene el mismo cumpleaños que ninguna de las personas 1 a 22. Deje que estos eventos se llamen Evento 2, Evento 3, y así sucesivamente. El evento 1 es el evento de que la persona 1 cumpla años, lo que ocurre con probabilidad 1. Esta conjunción de eventos se puede calcular usando 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 las personas 1 y 2 aún no hayan celebrado. Esto continúa hasta que finalmente la probabilidad del Evento 23 dado que todos los eventos anteriores ocurrieron es 343/365. Finalmente, el principio de probabilidad condicional implica que $P (A')$ es igual al producto de estas probabilidades individuales:

P(A')={frac {365}{365}}times {frac {364}{365}}times {frac {363}{365}}times {frac {362}{365}}times cdots times {frac {343}{365}}

()1)

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

P(A')=left({frac {1}{365}}right)^{23}times (365times 364times 363times cdots times 343)

()2)

La ecuación de evaluación (2) da $P (A') \approx 0,492703$

Por lo tanto, $P (A) \approx 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 al menos dos de los $n$ personas que comparten un cumpleaños. Es más fácil calcular primero la probabilidad $p (n)$ que todos los $n$ cumpleaños son diferentes. Según el principio del casillero, $p (n)$ es cero cuando $n > 365$ . Cuando $n \leq 365$ :

{displaystyle {begin{aligned}{bar {p}}(n)&=1times 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 {365times 364times 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{aligned}}}

donde $!$ es el operador factorial, $(365 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 el 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 como cualquiera de los dos primeros (363/365), y en general el $n$ th cumpleaños no puede ser igual que cualquiera de los $n - 1$ cumpleaños anteriores.

El evento de que al menos dos de las $n$ personas tengan el mismo cumpleaños es complementario a todas las $n$ los cumpleaños son 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 probabilidad de que no dos personas compartan un cumpleaños en un grupo

n

gente. Tenga en cuenta que la escala vertical es logarítmica (cada paso hacia abajo es 10²⁰ veces menos probable).

$n$	$p () n)$
1	00,0%
5	02,7%
10	11,7%
20	41.1%
23	50,7%
30	70,6%
40	89,1%
50	97,0%
60	99,4%
70	99,9%
75	99,97%
100	99.99997%
200	99.9999999999999999999999999998%
300	(100 − 6×10⁻⁸⁰)
350	(100 − 3×10⁻¹²⁹)
365	(100 − 1.45×10^−15-5)
≥ 366	100%

Aproximaciones

Gráficos mostrando las probabilidades aproximadas de al menos dos personas compartiendo un cumpleaños (rojo) y su evento complementario (azul)

Un gráfico que muestra la precisión de la aproximación

1 - e - n 2 . 730

()rojo)

La expansión de la serie de Taylor de la función exponencial (la constante $e \approx 2.718 281828)$

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

proporciona una aproximación de primer orden para $e x$ para $|x|ll 1$ :

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

Para aplicar esta aproximación a la primera expresión derivada de $p (n)$ , establezca $x = - a / 365$ . De este modo,

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

Luego, reemplaza $a$ con enteros no negativos para cada término en la fórmula de $p (n)$ hasta $a = n - 1$ , por ejemplo, cuando $a = 1$ ,

{displaystyle e^{-{frac {1}{365}}}approx 1-{frac {1}{365}}.}

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

{displaystyle {begin{aligned}{bar {p}}(n)&approx 1cdot e^{-{frac {1}{365}}}cdot e^{-{frac {2}{365}}}cdots e^{-{frac {n-1}{365}}}\[6pt]&=e^{-{frac {1+2+,cdots ,+(n-1)}{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 gruesa está dada por

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

que, como ilustra el gráfico, sigue siendo bastante preciso.

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 usando el mismo enfoque que el anterior obtenemos el resultado de que si $p (n, d)$ es la probabilidad de que en menos dos de $n$ personas comparten el mismo cumpleaños de un conjunto de $d$ días disponibles, luego:

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

Exponenciación simple

La probabilidad de que dos personas cualesquiera no tengan el mismo cumpleaños es 364/365. En una sala que contiene n personas, hay $(n 2) = n (n - 1) / 2$ pares de personas, es decir, $(n 2)$ eventos. La probabilidad de que no haya dos personas que compartan el mismo cumpleaños se puede aproximar asumiendo que estos eventos son independientes y, por lo tanto, multiplicando su probabilidad. Ser independiente equivaldría a escoger con reposición, a cualquier par de personas del mundo, no solo en una habitación. En resumen 364/365 se puede multiplicar por sí mismo $(n 2)$ 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.}

Aproximación de Poisson

Aplicando la aproximación de Poisson para el binomio sobre 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

0)=1-Pr(X=0)approx 1-e^{-0.6932}approx 1-0.499998=0.500002.}" xmlns="http://www.w3.org/1998/Math/MathML">Pr()X■0)=1− − Pr()X=0).. 1− − e− − 0,692.. 1− − 0.499998=0.500002.{displaystyle Pr(X confía0)=1-Pr(X=0)approx 1-e^{-0.6932}approx 1-0.499998=0.500002.}0)=1-Pr(X=0)approx 1-e^{-0.6932}approx 1-0.499998=0.500002." aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b88a049729c8a4efa29920a4287831452ff80f26" style="vertical-align: -0.838ex; width:70.868ex; height:3.176ex;"/>

El resultado es más del 50% como descripciones anteriores. Esta aproximación es la misma que la anterior basada en la expansión de Taylor que utiliza $x$ .

Aproximación al cuadrado

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

{displaystyle p(n)approx {frac {n^{2}}{2m}}}

que también se puede escribir como

napprox {sqrt {2mtimes p(n)}}

que funciona bien para probabilidades menores o iguales a 1 //span>2. En estas ecuaciones, $m$ es la cantidad de días en un año.

Por ejemplo, para estimar la cantidad de personas necesarias para una 1/2 probabilidad de un cumpleaños compartido, obtenemos

{displaystyle napprox {sqrt {2times 365times {tfrac {1}{2}}}}={sqrt {365}}approx 19}

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

Aproximación del número de personas

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

{displaystyle ngeq {tfrac {1}{2}}+{sqrt {{tfrac {1}{4}}+2times ln(2)times 365}}=22.999943.}

Este es el resultado de la buena aproximación que un evento con $1 / k$ probabilidad tendrá un 1/2 posibilidad de que ocurra al menos una vez si se repite $k ln 2$ veces.

Tabla de probabilidades

longitud Hex string	No. bits () $b$ )	espacio tamaño () $2 b$ )	Número de elementos de hashed tales que probabilidad de al menos una colisión de hachís ≥ $p$
longitud Hex string	No. bits () $b$ )	espacio tamaño () $2 b$ )	$p$ = 10⁻¹⁸	$p$ = 10⁻¹⁵	$p$ = 10⁻¹²	$p$ = 10⁻⁹	$p$ = 10⁻⁶	$p$ = 0,001	$p$ = 0,01	$p$ = 0,25 dólares	$p$ = 0,50	$p$ = 0,75 dólares
8	32	4.3×10⁹	2	2	2	2.9	93	2.9×10³	9.3×10³	5.0×10⁴	7.7×10⁴	1.1×10⁵
(10)	(40)	()1.1×10¹²)	2	2	2	47	1,5×10³	4.7×10⁴	1,5×10⁵	8.0×10⁵	1.2×10⁶	1.7×10⁶
(12)	(48)	()2.8×10¹⁴)	2	2	24	7.5×10²	2.4×10⁴	7.5×10⁵	2.4×10⁶	1.3×10⁷	2.0×10⁷	2.8×10⁷
16	64	1.8×10¹⁹	6.1	1.9×10²	6.1×10³	1.9×10⁵	6.1×10⁶	1.9×10⁸	6.1×10⁸	3.3×10⁹	5.1×10⁹	7.2×10⁹
(24)	(96)	()7.9×10²⁸)	4.0×10⁵	1.3×10⁷	4.0×10⁸	1.3×10¹⁰	4.0×10¹¹	1.3×10¹³	4.0×10¹³	2.1×10¹⁴	3.3×10¹⁴	4.7×10¹⁴
32	128	3.4×10³⁸	2.6×10¹⁰	8.2×10¹¹	2.6×10¹³	8.2×10¹⁴	2.6×10¹⁶	8.3×10¹⁷	2.6×10¹⁸	1.4×10¹⁹	2.2×10¹⁹	3.1×10¹⁹
(48)	(192)	()6.3×10⁵⁷)	1.1×10²⁰	3.5×10²¹	1.1×10²³	3.5×10²⁴	1.1×10²⁶	3.5×10²⁷	1.1×10²⁸	6.0×10²⁸	9.3×10²⁸	1.3×10²⁹
64	256	1.2×10⁷⁷	4.8×10²⁹	1,5×10³¹	4.8×10³²	1,5×10³⁴	4.8×10³⁵	1,5×10³⁷	4.8×10³⁷	2.6×10³⁸	4.0×10³⁸	5.7×10³⁸
(96)	(384)	()3.9×10¹¹⁵)	8.9×10⁴⁸	2.8×10⁵⁰	8.9×10⁵¹	2.8×10⁵³	8.9×10⁵⁴	2.8×10⁵⁶	8.9×10⁵⁶	4.8×10⁵⁷	7.4×10⁵⁷	1.0×10⁵⁸
128	512	1.3×10¹⁵⁴	1.6×10⁶⁸	5.2×10⁶⁹	1.6×10⁷¹	5.2×10⁷²	1.6×10⁷⁴	5.2×10⁷⁵	1.6×10⁷⁶	8.8×10⁷⁶	1.4×10⁷⁷	1.9×10⁷⁷

Comparación del problema de cumpleaños (1) y ataque de cumpleaños (2):

En (1), las colisiones se encuentran dentro de un set, en este caso, 3 de 276 pares de los 24 astronautas lunares.

En (2), las colisiones se encuentran entre dos conjuntos, en este caso, 1 de 256 emparejamientos de sólo los primeros bytes de SHA-256 hashes de 16 variantes cada uno de contratos benignos y dañinos.

Los campos más claros en esta tabla muestran la cantidad de hash necesarios para lograr la probabilidad de colisión dada (columna) dado un espacio de hash de cierto tamaño 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 el "número requerido de elementos hash" se parece al "número requerido de personas en un grupo". También se podría usar este gráfico para determinar el tamaño de hash mínimo requerido (dados los límites superiores de los hash y la probabilidad de error), o la probabilidad de colisión (para un número fijo de hash y probabilidad de error).

Para comparar, 10⁻¹⁸ a 10⁻¹⁵ es la tasa de error de bit incorregible de un disco duro típico. En teoría, las funciones hash de 128 bits, como MD5, deberían permanecer dentro de ese rango hasta aproximadamente 8.2×10¹¹ documentos, incluso si sus salidas posibles son muchas más.

Un límite superior en la probabilidad y un límite inferior en el número de personas

El siguiente argumento está adaptado de un argumento de Paul Halmos.

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 párrafos anteriores, el interés radica en el $n$ más pequeño tal que $p (n) > 1 / 2$ ; o de manera equivalente, 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 - k / 365$ con $e - k ⁄ 365$ . Esto produce

<math alttext="{displaystyle {bar {p}}(n)=prod _{k=1}^{n-1}left(1-{frac {k}{365}}right)p̄ ̄ ()n)=∏ ∏ k=1n− − 1()1− − k365).∏ ∏ k=1n− − 1()e− − k365)=e− − n()n− − 1)730.{displaystyle {bar}(n)=prod ¿Por qué? {fnK}}derecha)=e^{fn1} {fn1} {fn1}}derecha)=e^{-{frac {n-1)}}}}}<img alt="{displaystyle {bar {p}}(n)=prod _{k=1}^{n-1}left(1-{frac {k}{365}}right)

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

<math alttext="{displaystyle e^{-{frac {n(n-1)}{730}}}e− − n()n− − 1)730.12{displaystyle e^{-{frac {n-1}{730} {frac}} {1}{2}}}<img alt="{displaystyle e^{-{frac {n(n-1)}{730}}}

implica $p (n) < 1 / 2$ . Resolviendo para $n$ da

730ln 2.}" xmlns="http://www.w3.org/1998/Math/MathML">n2− − n■730In⁡ ⁡ 2.{displaystyle No. 2.}730ln 2.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f993e1a7d3f9f66b55169f0b5f9d714f4ca05b99" style="vertical-align: -0.505ex; width:17.793ex; height:2.843ex;"/>

Ahora, $730 ln 2$ es aproximadamente 505,997, que está apenas por debajo de 506, el valor de $n 2 - n$ obtenido cuando $n = 23$ . Por lo tanto, 23 personas son suficientes. Por cierto, resolviendo $n 2 - n = 730 ln 2$ para n da la fórmula aproximada de Frank H. Mathis citada anteriormente.

Esta derivación solo muestra que como máximo se necesitan 23 personas para asegurar una coincidencia de cumpleaños con igualdad de oportunidades; deja abierta la posibilidad de que $n$ sea 22 o menos también podría funcionar.

Generalizaciones

Número arbitrario de días

Dado un año con $d$ días, el problema generalizado de 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 es de al menos el 50%. En otras palabras, $n (d)$ es el número entero mínimo $n$ tal que

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 a determinar $n (365)$ . Los primeros 99 valores de $n (d)$ se dan aquí (secuencia A033810 en el OEIS):

$d$	1–2	3 a 5	6 a 9	10 a 16	17 a 23	24 a 32	33–42	43 a 54	55 a 68	69 a 82	83 a 99
$n () d)$	2	3	4	5	6	7	8	9	10	11	12

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

Se han publicado varios límites y fórmulas para $n (d)$ . Para cualquier $d \geq 1$ , el número $n (d)$ satisface

<math alttext="{displaystyle {frac {3-2ln 2}{6}}3− − 2In⁡ ⁡ 26.n()d)− − 2dIn⁡ ⁡ 2≤ ≤ 9− − 86In⁡ ⁡ 2.{displaystyle {frac {3-2ln 2}{6}cantado(d)-{sqrt {2dln 2}leq 9-{sqrt {86ln 2}}}}<img alt="{frac {3-2ln 2}{6}}

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

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

mientras tiene

9-{sqrt {86ln 2}}approx 1.28

como máximo, tomado por $d = 43$ .

Los límites son lo suficientemente estrechos 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 número entero en ese rango. En general, se sigue de estos límites que $n (d)$ siempre es igual a

{displaystyle leftlceil {sqrt {2dln 2}},rightrceil quad {text{or}}quad leftlceil {sqrt {2dln 2}},rightrceil +1}

donde $⌈ \cdot ⌉$ indica la función techo. La formula

{displaystyle n(d)=leftlceil {sqrt {2dln 2}},rightrceil }

es válido para el 73 % de todos los números enteros $d$ . La formula

n(d)=leftlceil {sqrt {2dln 2}}+{frac {3-2ln 2}{6}}rightrceil

es válido para casi todas las $d$ , es decir, para un conjunto de enteros $d$ con densidad asintótica 1.

La fórmula

{displaystyle n(d)=leftlceil {sqrt {2dln 2}}+{frac {3-2ln 2}{6}}+{frac {9-4(ln 2)^{2}}{72{sqrt {2dln 2}}}}rightrceil }

se mantiene para todos los $d \leq 1018$ , pero se conjetura que hay infinitos contraejemplos para esta fórmula.

La fórmula

{displaystyle n(d)=leftlceil {sqrt {2dln 2}}+{frac {3-2ln 2}{6}}+{frac {9-4(ln 2)^{2}}{72{sqrt {2dln 2}}}}-{frac {2(ln 2)^{2}}{135d}}rightrceil }

se mantiene para todos los $d \leq 1018$ , y se conjetura que esta fórmula es válida para todos los $d$ .

Más de dos personas compartiendo un cumpleaños

Es posible extender 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 un cumpleaños: 88 personas; >50 % de probabilidad de que 4 personas compartan cumpleaños: 187 personas (secuencia A014088 en el OEIS).

Probabilidad de un cumpleaños compartido (colisión)

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

Dado

n

enteros extraídos de una distribución uniforme discreta con rango

[1,1] d]

, cuál es la probabilidad

p () n; d)

¿Que al menos dos números son iguales? ()

d = 365

da el problema de cumpleaños habitual.)

Los resultados genéricos se pueden derivar utilizando los mismos argumentos dados anteriormente.

dend{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}}}" xmlns="http://www.w3.org/1998/Math/MathML">p()n;d)={}1− − ∏ ∏ k=1n− − 1()1− − kd)n≤ ≤ d1n■d.. 1− − e− − n()n− − 1)2d.. 1− − ()d− − 1d)n()n− − 1)2{displaystyle {begin{aligned}p(n;d) sensible={begin{cases}1-displaystyle prod _{k=1}^{n-1}left(1-{frac {k} {d}right) ################################################################################################################################################################################################################################################################ {d-1}{d}right)} {fn1}end{aligned}}}dend{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}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85e10a5ef850209f4f2010865e273fc0ce51d35b" style="vertical-align: -11.671ex; width:38.275ex; height:24.509ex;"/>

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

{displaystyle n(p;d)approx {sqrt {2dcdot 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 $N$ bits hash que se pueden generar antes de obtener un la colisión no es $2 N$ , sino solo $2 N ⁄ 2$ . Esto es aprovechado por los ataques de cumpleaños en las funciones hash criptográficas y es la razón por la que un pequeño número de colisiones en una tabla hash son, a todos los efectos prácticos, inevitables.

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

Generalización a múltiples tipos de personas

Parcela de la probabilidad de al menos un cumpleaños compartido entre al menos un hombre y una mujer

El problema básico considera que todas las pruebas son de un "tipo". El problema del cumpleaños se ha generalizado para considerar un número arbitrario de tipos. En la extensión más simple hay dos tipos de personas, digamos $m$ men y $n$ mujeres, y el problema se convierte en 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

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 2$ son números de Stirling de segunda clase. En consecuencia, la probabilidad deseada es $1 - p 0$ .

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 realiza 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.$

Otros problemas de cumpleaños

Primer partido

Una pregunta relacionada es, a medida que las personas ingresan a una habitación de una en una, ¿cuál es más probable que sea la primera en tener el mismo cumpleaños que alguien que ya está en la habitación? Es decir, por lo que $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.

El mismo cumpleaños que tú

Comparación

p () n)

= probabilidad de un partido de cumpleaños con

q () n)

= probabilidad de emparejar tu Cumpleaños

En el problema del cumpleaños, ninguna de las dos personas se elige de antemano. Por el contrario, la probabilidad $q (n)$ de que alguien en una habitación de estilo $n$ otras personas tienen el mismo cumpleaños que una persona particular (por ejemplo, usted) está dada por

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

y para general $d$ por

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

En el caso estándar de $d = 365$ , sustituyendo $n = 23$ da alrededor del 6,1 %, que es menos de 1 posibilidad entre 16. Para una probabilidad superior al 50 % de que una persona en una habitación llena de $n$ personas tienen el mismo cumpleaños que tú, $n$ tendría que estar en 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 habitación.

Número de personas con un cumpleaños compartido

Para cualquier persona en un grupo n la probabilidad de que él o ella compartan 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), así que es:

{displaystyle nleft(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 nleft({frac {d-1}{d}}right)^{n-1}}

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

Número de personas hasta cumplir cada cumpleaños

La cantidad esperada de personas necesarias hasta que se cumpla cada cumpleaños se llama 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.

Coincidencias cercanas

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 naturales entre sí, si hay $d$ cumpleaños igualmente probables.

{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 necesario para que la probabilidad de que alguna pareja cumpla años separadas por $k$ días o menos sea superior al 50% se da en la siguiente tabla:

$k$	$n$ para $d = 365$
0	23
1	14
2	11
3	9
4	8
5	8
6	7
7	7

Por lo tanto, en un grupo de solo siete personas aleatorias, lo más probable es que dos de ellas cumplan años con una semana de diferencia.

Número de días con un cierto número de cumpleaños

Número de días con al menos un cumpleaños

La cantidad esperada de cumpleaños diferentes, es decir, la cantidad de días que son el cumpleaños de al menos una persona, es:

{displaystyle d-dleft({frac {d-1}{d}}right)^{n}}

Esto se deriva de la cantidad esperada de días que no son el cumpleaños de nadie:

{displaystyle dleft({frac {d-1}{d}}right)^{n}}

que se deriva de la probabilidad de que un día en particular no sea el cumpleaños de nadie, $(d - 1 / d) n$ , se suma fácilmente debido a la linealidad del valor esperado.

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

Número de días con al menos dos cumpleaños

Lo anterior se puede generalizar a partir de la distribución del número de personas que cumplen años en un día en particular, que es una distribución Binomial con probabilidad $1 / d$ . Multiplicando la probabilidad relevante por $d$ obtendrá el número esperado de días. Por ejemplo, el número esperado de días que se comparten; es decir, que son al menos dos (es decir, no cero ni uno) el cumpleaños de las personas es:

{displaystyle d-dleft({frac {d-1}{d}}right)^{n}-dcdot {binom {n}{1}}left({frac {1}{d}}right)^{1}left({frac {d-1}{d}}right)^{n-1}=d-dleft({frac {d-1}{d}}right)^{n}-nleft({frac {d-1}{d}}right)^{n-1}}

Número de personas que repiten cumpleaños

La probabilidad de que el $k$ ésimo entero elegido al azar de $[1, d]$ repetirá al menos una opción anterior igual a $q (k - 1; d)$ arriba. El número total esperado de veces que una selección repetirá una selección anterior como $n$ tales enteros se eligen como iguales

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

Se puede ver que esto es igual a la cantidad de personas menos la cantidad esperada de cumpleaños diferentes.

Número promedio de personas que tienen al menos un cumpleaños compartido

En una formulación alternativa del problema del cumpleaños, se pregunta el 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 es determinar la media de la distribución, a diferencia de la formulación habitual, que pide la mediana. El problema es relevante para varios algoritmos hash analizados por Donald Knuth en su libro The Art of Computer Programming. Puede demostrarse que si se muestrea uniformemente, con reemplazo, de una población de tamaño $M$ , el número de intentos necesarios para el primer muestreo repetido de algún individuo tiene un valor esperado $n = 1 + Q (M)$ , donde

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

La función

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:

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, la cantidad promedio de personas requeridas para encontrar una pareja con el mismo cumpleaños es n = 1 + Q(M) ≈ 24,61659, algo más de 23, el número necesario para un 50% de probabilidad. En el mejor de los casos, dos personas serán suficientes; en el peor de los casos, se necesita el número máximo posible de $M + 1 = 366$ personas; pero en promedio, solo se requieren 25 personas

Un análisis usando variables aleatorias indicador puede proporcionar un análisis más simple pero aproximado de este problema. Para cada par (i, j) para k personas en una habitación, definimos el indicador variable aleatoria X_ij, para ${displaystyle 1leq ileq jleq k}$ , por

{displaystyle {begin{alignedat}{2}X_{ij}&=I{{text{person }}i{text{ and person }}j{text{ have the same birthday}}}\&={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}]\&={binom {k}{2}}{frac {1}{n}}\&={frac {k(k-1)}{2n}}\end{alignedat}}}

Para $n = 365$ , si $k = 28$ , la cantidad esperada de personas con el mismo cumpleaños es 28 × 27 //span>2 × 365 ≈ 1,0356. Por lo tanto, podemos esperar al menos una pareja coincidente con al menos 28 personas.

Se puede hacer una demostración informal del problema a partir de la lista de primeros ministros de Australia, de la que ha habido 29 a partir de 2017, en la que Paul Keating, el vigésimo cuarto primer ministro, y Edmund Barton, el primer primer ministro, comparten el mismo cumpleaños, 18 de enero.

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

Voracek, Tran y Formann demostraron que la mayoría de las personas sobrestiman considerablemente el número de personas necesario para lograr una probabilidad dada de que las personas tengan el mismo cumpleaños, y subestiman considerablemente la probabilidad de que las personas tengan el mismo cumpleaños cuando se analiza una muestra específica. se da el tamaño. 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 tenían menos confianza en sus estimaciones.

Problema inverso

El problema inverso es encontrar, para una probabilidad fija $p$ , el mayor $n$ para el cual la probabilidad $p (n)$ es menor que el $p$ dado, o el $n$ para la cual la probabilidad $p (n)$ es mayor que la $p$ dada.

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

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

La siguiente tabla proporciona algunos ejemplos de cálculos.

$p$	$n$	$n ↓$	$p () n ↓$	$n ↑$	$p () n ↑$
0,01	0.14178√365 = 2.70864	2	0,00274	3	0,00820
0,05	0.32029√365 = 6.11916	6	0,04046	7	0,05624
0.1	0.45904√365 = 8.77002	8	0,07434	9	0,09462
0.2	0,6805√365 = 12.76302	12	0.16702	13	0.19441
0.3	0.84460√365 = 16.13607	16	0,2860	17	0.31501
0.5	1.17741√365 = 22.49439	22	0.47570	23	0,5730
0.7	1.55176√365 = 29.64625	29	0.68097	30	0,7632
0,8	1.79412√365 = 34.27666	34	0,7532	35	0.81438
0.9	2.14597√365 = 40.99862	40	0.89123	41	0.90315
0.95	2.44775√365 = 46.76414	46	0.94825	47	0.95477
0.99	3.03485√365 = 57.98081	57	0.99012	58	0.99166

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

Problema de partición

Un problema relacionado es el problema de la partición, una variante del problema de la mochila de la investigación de operaciones. Algunas pesas se colocan en una balanza; cada peso 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 normalmente (es decir, con una probabilidad cercana a 1) transferir los pesos entre los brazos izquierdo y derecho para equilibrar la balanza. (En caso de que la suma de todos los pesos sea un número impar de gramos, se permite una discrepancia de un gramo). Si solo hay dos o tres pesos, la respuesta es muy claramente no; aunque hay algunas combinaciones que funcionan, la mayoría de las combinaciones de tres pesos seleccionadas al azar no lo hacen. Si hay muchos pesos, la respuesta es claramente sí. La pregunta es, ¿cuántos son suficientes? Es decir, ¿cuál es el número de pesos tal que es igualmente probable que sea posible equilibrarlos que imposible?

A menudo, la intuición de las personas es que la respuesta está por encima de 100000. La intuición de la mayoría de las personas es que son miles o decenas de miles, mientras que otros sienten que al menos deberían ser cientos. La respuesta correcta es 23.

La razón es que la comparación correcta es el número de particiones de los pesos en izquierda y derecha. Hay $2 N - 1$ particiones diferentes para $N$ pesos, y la suma de la izquierda menos la suma de la 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 en $500000 N$ y ancho $1000000 \sqrt N$ , de modo que cuando $2 N - 1$ es aproximadamente igual a $1000000 \sqrt N$ ocurre la transición. 2^{23 − 1} es alrededor de 4 millones, mientras que el ancho de la distribución es de solo 5 millones.

En la ficción

La novela A Fall of Moondust de Arthur C. Clarke, publicada en 1961, 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 dijo un pasajero físico: "Si tiene un grupo de más de veinticuatro personas, las probabilidades son mejores que incluso que dos de ellos tengan el mismo cumpleaños." Finalmente, de los 22 presentes, se revela que dos personajes comparten el mismo cumpleaños, el 23 de mayo.

Contenido relacionado

Más resultados...