Explorateur du paradoxe des anniversaires

Combien de personnes doivent se trouver dans une pièce pour qu'un anniversaire en commun soit plus probable qu'improbable ? Dérivez le résultat, puis expliquez pourquoi 23 semble bien trop petit.

1. Calculez l'opposé. « Au moins un en commun » est complexe car le partage peut se produire de nombreuses façons à la fois ; « tous différents » constitue une seule suite propre de choix.

   $$P(\text{all different})=\prod _{k=0}^{n-1}\frac{365-k}{365}$$

2. Chaque nouvelle personne doit éviter tous les anniversaires déjà pris, de sorte que les jours disponibles diminuent d'un à chaque fois. Multipliez les fractions.

   $$n=23:\frac{365}{365}\cdot \frac{364}{365}\cdots \frac{343}{365}=0.4927$$

3. Soustrayez de un. L'explorateur ci-dessus affiche exactement cela, et 23 est le premier n pour lequel le résultat dépasse une moitié.

   $$P(\text{shared})=1-0.4927=0.5073=50.7\%$$

4. Vous ne vous comparez pas à 22 autres personnes : chaque paire compte, et le nombre de paires croît comme le carré de l’effectif du groupe.

   $$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{23\times 22}{2}=253\text{pairs}$$

5. Cette croissance au carré est visible dans l'approximation : la probabilité dépend de n² sur 730, le point de croisement évolue donc comme une racine carrée, et non comme une fraction de 365.

   $$P\approx 1-e^{-n^2/730}:n=\sqrt{730\ln 2}=22.5$$

Vingt-trois personnes, 50,7 %. Le nombre que tout le monde retient est 23, et c'est la partie la moins utile du résultat : il appartient à une année de 365 jours et à rien d'autre. Trouvez la règle en dessous, celle qui tient encore quand le calendrier est une fonction de hachage.

1. La réponse exacte est un produit : la deuxième personne évite la première, la troisième les évite toutes deux, et ainsi de suite dans la pièce. C'est ce produit que le panneau évalue.

   $$Q(n)=\prod _{k=0}^{n-1}\frac{365-k}{365},P=1-Q(23)=0.507$$

2. On raisonne mal sur les produits : passez aux logarithmes — et tant que k reste petit devant 365, chaque logarithme vaut presque son propre argument. Il reste la somme des n−1 premiers entiers.

   $$\ln Q=\sum _{k=0}^{n-1}\ln \left(1-\frac{k}{365}\right)\approx -\sum _{k=0}^{n-1}\frac{k}{365}=-\frac{n(n-1)}{730}$$

3. Posez la probabilité à un demi et résolvez. Le terme en n² domine le n, la réponse est donc une racine carrée, et elle tombe à une demi-personne des 23 du panneau.

   $$P=\frac{1}{2}⟹\frac{n(n-1)}{730}=\ln 2⟹n^2\approx 730\ln 2=506.0⟹n\approx 22.5$$

4. Écrivez-la maintenant sans aucun 365. L'année n'a jamais été spéciale : pour N cases équiprobables, le point de bascule est vers 1,1774√N.

   $$n\approx \sqrt{2N\ln 2}=1.1774\sqrt{N}:N=365⟹22.49$$

5. Appliquez cela là où ça mord. Un hachage 32 bits a 2³² cases, ce qui paraît énorme — mais la racine carrée d'un nombre énorme ne l'est pas.

   $$N=2^{32}:n\approx 1.1774\sqrt{2^{32}}=1.1774\times 65536=77162$$

6. Mesurez ce résultat à la taille de l'espace dont il est tiré.

   $$\frac{77162}{2^{32}}=1.8\times 10^{-5}=0.0018\%$$