Problema de cumpleaños - Birthday problem

La probabilidad calculada de que al menos dos personas compartan un cumpleaños frente al número de personas

En la teoría de la probabilidad , el problema del cumpleaños o la paradoja del cumpleaños se refieren a la probabilidad de que, en un conjunto de $n$ personas elegidas al azar , alguna pareja de ellos tenga el mismo cumpleaños . En un grupo de 23 personas, la probabilidad de un cumpleaños compartido supera el 50%, mientras que un grupo de 70 tiene un 99,9% de probabilidad de un cumpleaños compartido. (Según el principio del casillero , la probabilidad alcanza el 100% cuando el número de personas llega a 367, ya que solo hay 366 cumpleaños posibles, incluido el 29 de febrero ).

Estas conclusiones se basan en la suposición de que cada día del año es igualmente probable para un cumpleaños. Los registros de nacimiento reales muestran que diferentes números de personas nacen en diferentes días. En este caso, se puede demostrar que el número de personas necesarias para alcanzar el umbral del 50% es 23 o menos .

El problema del cumpleaños es una paradoja verídica : una proposición que al principio parece contradictoria, pero que 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 todos los pares posibles de individuos. Con 23 individuos, hay (23 × 22) / 2 = 253 pares a considerar, que es más de la mitad del número de días en un año (182,5 o 183).

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

La historia del problema es oscura. El resultado se ha atribuido a Harold Davenport ; sin embargo, Richard von Mises propuso anteriormente una versión de lo que hoy se considera el problema del cumpleaños .

Calculando la probabilidad

El problema es calcular una probabilidad aproximada de que en un grupo de $n$ personas al menos dos tengan el mismo cumpleaños. Para simplificar, las variaciones en la distribución, como los años bisiestos , los gemelos , las variaciones estacionales o de los días de la semana no se tienen en cuenta, y se supone que los 365 cumpleaños posibles son igualmente probables. (Las distribuciones de cumpleaños en la vida real no son uniformes, ya que no todas las fechas son igualmente probables, pero estas irregularidades tienen poco efecto en el análisis. En realidad, una distribución uniforme de las fechas de nacimiento es el peor de los casos).

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 el mismo cumpleaños. Entonces, debido a que $A$ y $A'$ son las únicas dos posibilidades y también son mutuamente excluyentes , $P (A) = 1 - P (A').$

En deferencia a las soluciones ampliamente publicadas que concluyen que 23 es el número mínimo de personas necesarias para tener una $P (A)$ superior al 50%, el siguiente cálculo de $P (A)$ utilizará a 23 personas como ejemplo. Si se numeran las 23 personas 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 tiene el mismo cumpleaños que la persona 1, y esa persona 3 no tiene el mismo cumpleaños que la persona 1. ya sea la persona 1 o la persona 2, y así sucesivamente, y finalmente esa persona 23 no tiene el mismo cumpleaños que ninguna de las personas 1 a 22. Dejemos que estos eventos se llamen respectivamente "Evento 2", "Evento 3", y así sucesivamente. También se puede agregar un "Evento 1", correspondiente al evento de cumpleaños de la persona 1, que ocurre con probabilidad 1. Esta conjunción de eventos se puede calcular usando probabilidad condicional : la probabilidad del Evento 2 es 364/365, como 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 el Evento 2 ocurrió es 363/365, ya que la persona 3 puede tener cualquiera de los cumpleaños que no hayan tomado las personas 1 y 2. 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:

{\ Displaystyle 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:

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

( 2 )

Evaluar la ecuació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 que al menos dos de las $n$ personas compartan un 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 casillero , $p (n)$ es cero cuando $n > 365$ . Cuando $n \leq 365$ :

{\ Displaystyle {\ begin {alineado} {\ 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 , $(365 n)$ es elcoeficiente binomialy $k P r$ denotapermutación.

La ecuación expresa el hecho de que la primera persona no tiene a nadie con quien compartir un 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, el $n$ º cumpleaños no puede ser el mismo que ninguno de los $n - 1$ cumpleaños anteriores.

El hecho 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 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 dos personas no compartan un cumpleaños en un grupo de

n

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

$norte$	$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,999 97 %
200	99,999 999 999 999 999 999 999 999 9998 %
300	(100 - 6 × 10 ⁻⁸⁰ )%
350	(100 - 3 × 10 ⁻¹²⁹ )%
365	(100 - 1,45 × 10 ⁻¹⁵⁵ )%
≥ 366	100%

Años bisiestos . Si sustituimos 365 por 366 en la fórmula para , un cálculo similar muestra que para los años bisiestos, el número de personas necesarias para que la probabilidad de una coincidencia sea superior al 50% también es 23; la probabilidad de coincidencia en este caso es del 50,6%. ${\ Displaystyle {\ bar {p}} (n)}$

Aproximaciones

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

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

1 - e - .mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} n 2 ⁄ 730

( rojo )

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

{\ 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 de $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 de $p (n)$ se puede aproximar como

{\ Displaystyle {\ begin {alineado} {\ bar {p}} (n) y \ approx 1 \ cdot e ^ {- 1/365} \ cdot e ^ {- 2/365} \ cdots e ^ {- ( n-1) / 365} \\ [6pt] & = e ^ {- \ left. {\ big (} 1 + 2 + \, \ cdots \, + (n-1) {\ big)} \ right / 365} \\ [6pt] & = e ^ {- (n (n-1) / 2) / 365} = e ^ {- n (n-1) / 730}. \ End {alineado}}}

Por lo tanto,

{\ Displaystyle p (n) = 1 - {\ bar {p}} (n) \ approx 1-e ^ {- n (n-1) / 730}.}

Una aproximación aún más burda viene dada por

{\ Displaystyle p (n) \ approx 1-e ^ {- 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 anterior obtenemos el resultado de que si $p (n, d)$ es la probabilidad de que al menos dos de $n$ personas comparten el mismo cumpleaños de un conjunto de $d$ días disponibles, luego:

{\ Displaystyle {\ begin {alineado} p (n, d) y \ approx 1-e ^ {- n (n-1) / (2d)} \\ [6pt] y \ approx 1-e ^ {- n ^ {2} / (2d)}. \ End {alineado}}}

Una simple exponenciación

La probabilidad de que dos personas no tengan el mismo cumpleaños es 364/365. En una habitación 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. En breve364/365se puede multiplicar por sí mismo $(n 2)$ tiempos, 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}}.}

Aproximación de Poisson

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% como descripciones anteriores. Esta aproximación es la misma que la anterior basada en la expansión de Taylor que usa . ${\ Displaystyle e ^ {x} \ approx 1 + x}$

Aproximación cuadrada

Una buena regla empírica 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

{\ Displaystyle n \ approx {\ sqrt {2m \ times p (n)}}}

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

Por ejemplo, para estimar el número de personas necesarias para un 1/2 posibilidad de un cumpleaños compartido, tenemos

{\ 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.

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 un1/2 posibilidad de coincidencia:

{\ Displaystyle n \ approx {\ tfrac {1} {2}} + {\ sqrt {{\ tfrac {1} {4}} + 2 \ times \ ln (2) \ times 365}} = 22,999943.}

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

Tabla de probabilidad

longitud de la cadena hexagonal	No. de bits ( $b$ )	tamaño del espacio hash ( $2 b$ )	Número de elementos hash tal que la probabilidad de al menos una colisión hash ≥ $p$
longitud de la cadena hexagonal	No. de bits ( $b$ )	tamaño del espacio hash ( $2 b$ )	$p$ =10 ⁻¹⁸	$p$ =10 ^-15	$p$ =10 ^-12	$p$ =10 ⁻⁹	$p$ =10 ⁻⁶	$p$ = 0,001	$p$ = 0,01	$p$ = 0,25	$p$ = 0,50	$p$ = 0,75
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 ⁷
dieciséis	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 del cumpleaños (1) y el ataque del cumpleaños (2):

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

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

Los campos más claros en esta tabla muestran el número de hashes necesarios para lograr la probabilidad de colisión dada (columna) dado un espacio hash de cierto tamaño en bits (fila). Utilizando 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 asemeja al "número requerido 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 hash y la probabilidad de error), o la probabilidad de colisión (para un número fijo de hash y probabilidad de error).

Para comparacion, 10 ⁻¹⁸ hasta10 ^-15 es la tasa de error no corregible 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 aproximadamenteDocumentos de 8,2 × 10 ¹¹ , aunque sus posibles salidas 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}} \derecho).}

Como en párrafos anteriores, el interés radica 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 - k / 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 ^ {- k / 365} \ right) = e ^ {- n (n-1) / 730}.}

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

{\ Displaystyle e ^ {- n (n-1) / 730} <{\ frac {1} {2}}}

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

{\ Displaystyle n ^ {2} -n> 730 \ ln 2.}

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 tanto, 23 personas son suficientes. Por cierto, al resolver $n 2 - 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 asegurar una coincidencia de cumpleaños con la misma probabilidad; deja abierta la posibilidad de que $n$ es 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 de cumpleaños generalizado pide el número mínimo $n (d)$ tal que, en un conjunto de $n$ personas elegidas al azar, la probabilidad de que coincida un cumpleaños es al menos del 50%. En otras palabras, $n (d)$ es el número 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 de cumpleaños corresponde, por tanto, a determinar $n (365)$ . Aquí se dan los primeros 99 valores de $n (d)$ (secuencia A033810 en la OEIS ):

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

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)$ . Para cualquier $d \geq 1$ , el número $n (d)$ satisface

{\ 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) - \sqrt 2 d ln 2 se$ acerca arbitrariamente a

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

mientras tiene

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

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

Los límites son lo suficientemente ajustados para dar el valor exacto de $n (d)$ en el 99% de todos los casos, por ejemplo, $n (365) = 23$ . 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 {o}} \ quad \ left \ lceil {\ sqrt {2d \ ln 2}} \, \ right \ rceil +1}

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

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

Se mantiene para el 73% de todos los números enteros $d$ . La formula

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

se cumple para casi todo $d$ , es decir, para un conjunto de números enteros $d$ con densidad asintótica 1.

La formula

{\ 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 mantiene para todo $d \leq 1018$ , pero se conjetura que hay infinitos contraejemplos de esta fórmula.

La formula

{\ 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 mantiene para todo $d \leq 1018$ , y se conjetura que esta fórmula es válida para todo $d$ .

Más de dos personas compartiendo un cumpleaños

Es posible ampliar el problema preguntando cuántas personas en un grupo son necesarias para que haya una probabilidad superior al 50% de que al menos 3/4/5 / etc. del grupo comparten 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 ).

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

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 de cumpleaños).

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

{\ Displaystyle {\ begin {alineado} 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 {alineado} }}

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 de cumpleaños en este sentido más genérico se aplica a las funciones hash : el número esperado de $N$ - bit hash que pueden generarse antes de conseguir una colisión no es $2 N$ , sino solamente $2 N / 2$ . Esto se aprovecha de los ataques de cumpleaños a las funciones hash criptográficas y es la razón por la que una pequeña cantidad de colisiones en una tabla hash son, a todos los efectos prácticos, inevitables.

Zoe Schnabel utilizó la teoría detrás del problema del cumpleaños 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

Gráfica de la probabilidad de al menos un cumpleaños compartido entre al menos un hombre y una mujer

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. En la extensión más simple, hay dos tipos de personas, digamos $m$ hombres y $n$ mujeres, y el problema pasa a ser 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} dk}

donde $d = 365$ y $S 2$ son números de Stirling del segundo tipo . 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 habitual de probabilidad 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, cuando las personas ingresan a una habitación de una en 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 20ª.

Mismo cumpleaños que tú

Comparando

p (n)

= probabilidad de un cumpleaños coincidente con

q (n)

= probabilidad de coincidir con su cumpleaños

En el problema del cumpleaños, ninguna de las dos personas es elegida de antemano. Por el contrario, la probabilidad $q (n) de$ que alguien en una habitación de $n$ otras 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$ , la sustitución de $n = 23$ da aproximadamente un 6,1%, que es menos de 1 probabilidad entre 16. Para una probabilidad superior al 50% de que una persona en una habitación llena de $n$ personas tenga el mismo cumpleaños que usted , $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 algunos partidos de cumpleaños entre las otras personas en la sala.

Número de personas con un cumpleaños compartido

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 nn \ left ({\ frac {d-1} {d}} \ right) ^ {n-1}}

(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 tres, cuatro, etc. otras personas.

Cerca de partidos

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.

{\ Displaystyle {\ begin {alineado} p (n, k, d) & = 1 - {\ frac {(d-nk-1)!} {d ^ {n-1} {\ bigl (} dn (k +1) {\ bigr)}!}} \ End {alineado}}}

El número de personas requerido para que la probabilidad de que alguna pareja cumpla años separados 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 al azar, es más probable que dos de ellos cumplan años con una semana de diferencia.

Número de días con una determinada cantidad de cumpleaños

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

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

{\ Displaystyle dd \ left ({\ frac {d-1} {d}} \ right) ^ {n}}

Esto se deriva del número esperado de días que no son el cumpleaños de nadie:

{\ Displaystyle d \ left ({\ 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 , que se suma fácilmente debido a la linealidad del valor esperado. ${\ Displaystyle ((d-1) / d) ^ {n}}$

Por ejemplo, con d = 365 , debería esperar alrededor de 21 cumpleaños diferentes cuando hay 22 personas, o 46 cumpleaños diferentes cuando hay 50 personas. Cuando haya 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 . Al multiplicar la probabilidad relevante por d, se obtendrá el número de días esperado. 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 dd \ left ({\ frac {d-1} {d}} \ right) ^ {n} -d \ cdot {\ binom {d} {1}} \ left ({\ frac {1} { d}} \ right) ^ {1} \ left ({\ frac {d-1} {d}} \ right) ^ {n-1} = dd \ left ({\ frac {d-1} {d} } \ right) ^ {n} -d \ left ({\ frac {d-1} {d}} \ right) ^ {n-1}}$

Número de personas que repiten un cumpleaños

La probabilidad de que el $k$ ésimo entero elegido al azar de $[1, d]$ repita al menos una opció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 $n$ tales enteros se eligen igual

{\ Displaystyle \ sum _ {k = 1} ^ {n} q (k-1; re) = norte-re + d \ izquierda ({\ frac {d-1} {d}} \ derecha) ^ {n }}

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

Número medio de personas que han compartido al menos un cumpleaños

En una formulación alternativa del problema del cumpleaños, se pregunta el número promedio de personas necesarias para encontrar un par con el mismo cumpleaños. Si consideramos la función de probabilidad Pr [ $n$ personas tienen al menos un cumpleaños compartido], este promedio está determinando 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 . Se puede demostrar que si se toman muestras de manera uniforme, 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!} {(Mk)! 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 medio de personas necesarias para encontrar una pareja con el mismo cumpleaños es $n = 1 + Q (M) \approx 24,61659$ , algo más de 23, el número necesario para un 50% de posibilidades. En el mejor de los casos, serán suficientes dos personas; 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 que utilice variables aleatorias de indicadores 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 la variable aleatoria del indicador X _ij , para , por ${\ Displaystyle 1 \ leq i \ leq j \ leq k}$

${\ displaystyle {\ begin {alignedat} {2} X_ {ij} & = I \ {{\ text {person}} i {\ text {y person}} j {\ text {tienen el mismo cumpleaños}} \} \\ & = {\ begin {cases} 1, & {\ text {if person}} i {\ text {y person}} j {\ text {tienen el mismo cumpleaños;}} \\ 0, & {\ text {de lo contrario.}} \ end {cases}} \ end {alignedat}}}$

${\ displaystyle {\ begin {alignedat} {2} E [X_ {ij}] & = \ Pr \ {{\ text {person}} i {\ text {y person}} j {\ text {tienen el mismo cumpleaños }} \} \\ & = 1 / n \ end {alineado}}}$

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

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

${\ Displaystyle {\ begin {alineado} {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 {alineado }}}$

Para $n = 365$ , si $k = 28$ , el número esperado de con el mismo cumpleaños es Por lo tanto, podemos esperar al menos un par coincidente con al menos 28 personas. ${\ Displaystyle (28 \ cdot 27) / (2 \ cdot 365) \ aproximadamente 1.0356.}$

Se puede hacer una demostración informal del problema a partir de la lista de Primeros Ministros de Australia , de los cuales había 29 a partir de 2017, en la que Paul Keating , el 24 ° primer ministro, y Edmund Barton , el primer primer ministro, comparten lo mismo. cumpleaños, 18 de enero.

En la Copa Mundial de la FIFA 2014 , cada una de las 32 plantillas tenía 23 jugadores. Un análisis de las listas de equipos oficiales 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, Holanda, Nigeria, Rusia, España y Estados Unidos cada uno con un par.

Voracek, Tran y Formann demostraron que la mayoría de las personas sobreestiman marcadamente el número de personas que es necesario para lograr una probabilidad determinada de que las personas tengan el mismo cumpleaños, y subestiman marcadamente la probabilidad de que las personas tengan el mismo cumpleaños cuando se da un tamaño de muestra específico. . Otros resultados fueron 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 $n$ mayor para el que la probabilidad $p (n)$ es menor que el $p$ dado , o el $n$ menor para el que la probabilidad $p (n)$ es mayor que el $p$ dado .

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

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

La siguiente tabla ofrece algunos cálculos de muestra.

$pag$	$norte$	$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,66805 √ 365 = 12,76302	12	0.16702	13	0.19441
0,3	0,84460 √ 365 = 16,13607	dieciséis	0.28360	17	0.31501
0,5	1,17741 √ 365 = 22,49439	22	0.47570	23	0.50730
0,7	1,55176 √ 365 = 29,64625	29	0,68097	30	0,70632
0,8	1.79412 √ 365 = 34.27666	34	0,79532	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 se encuentran 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. Algunos pesos 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 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 de modo que sea igualmente posible equilibrarlos que imposible?

A menudo, la intuición de las personas es que la respuesta está por encima 100 000 . La intuición de la mayoría de la gente es que es de miles o decenas de miles, mientras que otros sienten que al menos debería ser de 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 $1000000 N$ y el ancho $1000000 \sqrt N$ , de modo que cuando $2 N - 1$ es aproximadamente igual a $1000000 \sqrt N se$ produce la transición. 2^{23 - 1} es aproximadamente 4 millones, mientras que el ancho de la distribución es solo 5 millones.

En ficción

La novela de Arthur C. Clarke A Fall of Moondust , publicada en 1961, contiene una sección donde los personajes principales, atrapados bajo tierra por 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 tienes 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.

Notas

Referencias

Bibliografía

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 ed.).
Klamkin, M .; Newman, D. (1967). "Extensiones de la sorpresa de cumpleaños" . Revista de teoría combinatoria . 3 (3): 279–282. doi : 10.1016 / s0021-9800 (67) 80075-9 .
McKinney, EH (1966). "Problema de cumpleaños generalizado". American Mathematical Monthly . 73 (4): 385–387. doi : 10.2307 / 2315408 . JSTOR 2315408 .
Schneps, Leila ; Colmez, Coralie (2013). "Error matemático número 5. El caso de Diana Sylvester: análisis del golpe en frío". Matemáticas a prueba. Cómo se usan y abusan los números en la sala del tribunal . 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.

enlaces externos

La paradoja del cumpleaños contabilizando los cumpleaños de los años bisiestos
Weisstein, Eric W. "Problema de cumpleaños" . MathWorld .
Un artículo humorístico que explica la paradoja.
Experimento de cumpleaños de actividades SOCR EduMaterials
Comprender el problema del cumpleaños (mejor explicado)
Eurobirthdays 2012. Un problema de cumpleaños. Un ejemplo futbolístico práctico de la paradoja del cumpleaños.
Grime, James. "23: Probabilidad de cumpleaños" . Numberphile . Brady Haran . Archivado desde el original el 25 de febrero de 2017 . Consultado el 2 de abril de 2013 .
Calcular las probabilidades del problema de cumpleaños en WolframAlpha

Languages

In other projects