Un problème d'anniversaire inversé: aucune paire sur 1 million d'étrangers ne partage un anniversaire; quelle est leur longueur d'année?

11

Supposons une planète avec une très très longue année de jours. Il y a 1 million d'étrangers lors d'une fête dans une pièce, et personne ne partage un anniversaire. Que peut-on déduire de la taille de ?NNN

(Cette question plus compacte remplace celle mal formulée. )

Paul Uszak
la source
Le problème d'anniversaire vous indique la valeur de N où la probabilité d'au moins une correspondance est supérieure à une valeur spécifiée. Lorsque p = 1/2, il est surprenant à l'intuition que cela donne n = 23 .. Cela suppose que chaque anniversaire a la même probabilité uniforme (1/365). La non uniformité ne fait que n plus petit. Maintenant, dans votre problème, il semble que N remplace 365 et je suppose que l'hypothèse d'uniformité est maintenue.
Michael R. Chernick
Si N <= 1 000 000, alors au moins 1 correspondance a une probabilité = 1 et donc 0 correspond à une probabilité = 0.
Michael R. Chernick
Ainsi, lorsque N> 1 000 000, la probabilité d'au moins 1 correspondance a une probabilité <1 et donc la probabilité de zéro correspond commence à augmenter.
Michael R. Chernick
5
@Michael Veuillez réserver vos commentaires pour les demandes d'éclaircissements et autres discussions fortuites, et essayez de poster un seul à la fois: il y a une bonne raison pour la limite de caractères. Si vous vous retrouvez à discuter de quelque chose de substantiel qui nécessite plusieurs commentaires, vous essayez probablement de répondre à la question, vous pouvez donc aussi poster une réponse.
whuber

Réponses:

13

En supposant que tous les anniversaires sont également probables et que les anniversaires sont indépendants, la probabilité que étrangers ne partagent pas d'anniversaire estk+1

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

Son logarithme peut être sommé asymptotiquement à condition que soit beaucoup plus petit que :kN

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

Pour être que n'est pas inférieur à une valeur , nous devons être supérieur à . Les petits garantissent que est beaucoup plus grand que , d'où nous pouvons approximer avec précision comme . Cela donne100100α%NN(1)log(1α)αNk(1)k2/(2N)

k22N>log(1α),

impliquant

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

pour les petits .α

Par exemple, avec comme dans la question et (une valeur conventionnelle correspondant à une confiance de ), donne . k=1061α=0.0595%(2)N>1013

Voici une interprétation plus large de ce résultat. Sans se rapprocher de la formule , on obtient . Pour ce le risque de non collision dans un million d'anniversaires est (calculé sans approximation), essentiellement égal à notre seuil de . Ainsi, pour tout grand ou plus grand, il est de ou plus probable qu'il n'y aura pas de collisions, ce qui est cohérent avec ce que nous savons, mais pour tout plus petit, le risque de collision dépasse , ce qui commence à nous faire peur , nous aurions peut - être sous - estimé .N = 9,74786 × 10 12 N p ( 10 6 - 1 , 9,74786 × 10 12 ) = 95,0000 % 95 % N 95 % N 100 - 95 = 5 % N(2)N=9.74786×1012Np(1061,9.74786×1012)=95.0000%95%N95%N10095=5%N

Comme autre exemple, dans le problème d'anniversaire traditionnel, il y a chance de non collision chez personnes et chance de non collision chez personnes. Ces chiffres suggèrent que devrait dépasser et , respectivement, dans la plage de la valeur correcte de . Cela montre à quel point ces résultats asymptotiques approximatifs peuvent être précis même pour de très petits (à condition de s'en tenir à small ).k = 6 5,6 % k = 7 N 360 490 366 k α4%k=65.6%k=7N360490366kα

whuber
la source
Je n'étais pas prêt à donner une réponse comme celle-ci. Avec des nombres, ces grosses approximations pourraient être plus faciles à calculer. Wikipedia donne le problème d'anniversaire généralisé montrant les approximations et les limites de N avec k personnes (extraterrestres). J'avais la même formule que votre première équation.
Michael R. Chernick
Ma question serait de savoir quelle taille N doit avoir pour atteindre une confiance de 100%. Je pense que c'est quelque chose comme 10 ^ 18.
Michael R. Chernick
1
@MichaelChernick Pour une confiance de 100%, N passe à l'infini. Pour toute année finie et pour toute fête avec 2 étrangers ou plus, la probabilité de deux étrangers avec le même anniversaire est toujours supérieure à 0.
Pere
1
@Pere Oui, merci d'avoir vu ça. Je vais le réparer tout de suite. Cela n'a fait aucune différence pour le reste du message.
whuber
2
@Paul Uszak Je pense que votre commentaire sur la réponse de Pere (maintenant supprimé) était beaucoup trop sévère. Je pense que sa réponse a été donnée de bonne foi. Il essayait de vous être utile en fournissant des approximations utiles. Il a ensuite vu la réponse de whuber et a décidé qu'elle était plus complète et a accepté de supprimer sa réponse. Son commentaire sur le fait de ne pas s'attendre à une réponse détaillée ne visait pas la façon dont vous l'interprétiez. C'est un problème difficile. Vous avez même dû réécrire le message pour le rendre compréhensible. Je suis sûr qu'il ne considère pas la résolution d'un problème comme celui-ci comme une blague.
Michael R. Chernick