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 ?N
(Cette question plus compacte remplace celle mal formulée. )
probability
birthday-paradox
Paul Uszak
la source
la source
Réponses:
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
Son logarithme peut être sommé asymptotiquement à condition que soit beaucoup plus petit que :k N
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 donne100−100α% N N∗ (1) log(1−α) α N k (1) −k2/(2N)
impliquant
pour les petits .α
Par exemple, avec comme dans la question et (une valeur conventionnelle correspondant à une confiance de ), donne .k=106−1 α=0.05 95% (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×1012 N p(106−1,9.74786×1012)=95.0000…% 95% N 95% N 100−95=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=6 5.6% k=7 N 360 490 366 k α
la source