Un problema de cumpleaños inverso: ningún par de 1 millón de extranjeros comparte un cumpleaños; ¿Cuál es su duración de año?

11

Supongamos un planeta con un año muy muy largo de días. Hay 1 millón de alienígenas en una fiesta en una habitación, y nadie comparte un cumpleaños. ¿Qué se puede inferir sobre el tamaño de N ?NN

(Esta pregunta más compacta reemplaza a esta mal formulada ) .

Paul Uszak
fuente
El problema de cumpleaños te dice el valor de N donde la probabilidad de al menos una coincidencia es mayor que un valor especificado. Cuando p = 1/2 es sorprendente intuir que esto da n = 23 .. Esto supone que cada cumpleaños tiene la misma probabilidad uniforme (1/365). La no uniformidad solo hace n más pequeño. Ahora en su problema parece que N reemplaza 365 y supongo que se mantiene la suposición de uniformidad.
Michael R. Chernick
Si N <= 1,000,000, entonces al menos 1 coincidencia tiene probabilidad = 1 y entonces 0 coincidencias tienen probabilidad = 0.
Michael R. Chernick
Entonces, cuando N> 1,000,000 la probabilidad de al menos 1 coincidencia tiene una probabilidad <1 y, por lo tanto, la probabilidad de cero coincidencias comienza a aumentar.
Michael R. Chernick
55
@ Michael Reserve comentarios para solicitudes de aclaración y otras discusiones incidentales, e intente publicar solo uno a la vez: hay una buena razón para el límite de caracteres. Si te encuentras discutiendo algo sustancial que requiere múltiples comentarios, probablemente estés tratando de responder la pregunta, por lo que también podrías publicar una respuesta.
whuber

Respuestas:

13

Asumiendo que todos los cumpleaños son igualmente probables y los cumpleaños son independientes, la posibilidad de que extraterrestres no compartan un cumpleaños esk+1

p(k;N)=1(11N)(12N)(1kN).

Su logaritmo se puede sumar asintóticamente siempre que sea ​​mucho más pequeño que N :kN

(1)log(p(k;N))=k(k+1)2Nk+3k2+2k312N2O(k4N3).

Para ser seguros de que N no menos que algún valor es N * , necesitamos ( 1 ) sea mayor que log ( 1 - α ) . Los pequeños α aseguran que N es mucho más grande que k , de donde podemos aproximar ( 1 ) con precisión como - k 2 / ( 2 N ) . Esto produce100100α%NN(1)log(1α)αNk(1)k2/(2N)

k22N>log(1α),

Insinuando

(2)N>k22log(1α)k22α=N

α

k=1061α=0.0595%(2)N>1013

(2)N=9.74786×1012Np(1061,9.74786×1012)=95.0000%95%N95%N10095=5%N

4%k=65.6%k=7N360490366kα

whuber
fuente
No estaba preparado para dar una respuesta como esta. Con los números, estas aproximaciones grandes podrían ser más fáciles de calcular. Wikipedia da el problema de cumpleaños generalizado que muestra aproximaciones y límites en N con k personas (extranjeros). Tenía la misma fórmula que tu primera ecuación.
Michael R. Chernick
Mi pregunta sería qué tan grande debe ser N para alcanzar el 100% de confianza. Creo que es algo así como 10 ^ 18.
Michael R. Chernick
1
@MichaelChernick Para un 100% de confianza, N va al infinito. Para cualquier año finito y para cualquier grupo con 2 o más extraterrestres, la probabilidad de dos extraterrestres con el mismo cumpleaños siempre es mayor que 0.
Pere
1
@Pere Sí, gracias por ver eso. Lo arreglaré de inmediato. No hizo ninguna diferencia para el resto de la publicación.
whuber
2
@Paul Uszak Creo que tu comentario sobre la respuesta de Pere (ahora eliminado) fue demasiado duro. Creo que su respuesta fue dada de buena fe. Intentaba ser útil para usted brindándole aproximaciones útiles. Más tarde vio la respuesta de Whuber y decidió que era más completa y acordó eliminar su respuesta. Su comentario sobre no esperar una respuesta detallada no se refería a la forma en que lo interpretó. Este es un problema dificil. Incluso tuvo que volver a escribir la publicación para que sea comprensible. Estoy seguro de que no toma la resolución de un problema como este como una broma.
Michael R. Chernick