Ceci est une traduction automatique ; le texte original est en anglais. Consulter l'original
Vingt-trois personnes et la coïncidence à laquelle il faut s'attendre
Vingt-trois personnes forment 253 paires. Personne ne calcule jamais ces 253 paires, et c'est précisément la raison pour laquelle le résultat semble contredire l'intuition.
Mettez 23 personnes dans une pièce et la probabilité que deux d'entre elles partagent un anniversaire est de 50,7 %. Avec 70 personnes, elle est de 99,9 %.
Presque tout le monde estime un nombre bien trop élevé, et la raison en est qu'on se pose la mauvaise question. L'instinct est de penser à soi-même : quelle est la probabilité que quelqu'un ici partage mon anniversaire ? C'est un événement beaucoup plus rare, et il faudrait environ 253 personnes pour qu'elle dépasse une chance sur deux.
La question véritable porte sur n'importe quelle paire. Et les paires ne sont pas rares.
Compter les paires, pas les personnes
Vingt-trois personnes forment 23 × 22 ÷ 2 = 253 paires distinctes. Chaque paire a 1 chance sur 365 de concorder. Le nombre de paires croît comme le carré du nombre de personnes, de sorte que doubler la pièce quadruple les occasions de coïncidence.
Le calcul exact s'effectue dans l'autre sens — la probabilité qu'aucune paire ne concorde, soit 365/365 × 364/365 × 363/365 × … sur 23 termes, ce qui donne 0,493. Un moins ce résultat donne 0,507.
La règle générale à retenir
Pour N possibilités équiprobables, il faut environ √N tirages avant qu'une répétition devienne plus probable qu'improbable. Pour les anniversaires, √365 ≈ 19, et la constante s'établit à environ 1,18 × √N ≈ 22,5. Ce qui est suffisamment proche de 23.
La racine carrée, pas la moitié. C'est ce nombre que les gens évaluent mal, et l'erreur se fait dans le sens où l'on s'attend à ce que les coïncidences soient plus rares qu'elles ne le sont.
Là où ce n'est plus une curiosité de salon
Collisions de hachage. Une table de hachage de mille emplacements ne commence pas à subir des collisions lorsqu'elle approche des mille entrées. Elle commence à en subir aux alentours de trente. C'est pourquoi les implémentations de tables de hachage se préoccupent de la gestion des collisions dès la toute première insertion, et pourquoi la seule mesure du facteur de charge renseigne peu sur le nombre de sondages nécessaires à une recherche. L'outil Hash Table montre des collisions apparaissant bien plus tôt que prévu.
Cryptographie. C'est ici que la racine carrée fixe le paramètre de sécurité. Pour trouver deux documents différents ayant la même valeur de hachage de 64 bits, il ne faut pas 2⁶⁴ essais ; il en faut environ 2³² — soit à peu près quatre milliards, ce qui représente quelques minutes de travail. C'est ce qu'on appelle l'attaque des anniversaires, et c'est pourquoi une fonction de hachage destinée à offrir n bits de résistance aux collisions doit produire 2n bits de sortie. C'est la raison pour laquelle les hachés de 128 bits sont considérés comme n'offrant que 64 bits de résistance aux collisions et ne sont plus acceptables pour les signatures.
Interpréter les coïncidences. Tout ensemble de données suffisamment grand contient des coïncidences frappantes, et leur nombre évolue avec le nombre de paires, non avec celui des enregistrements. Deux personnes d'une même ville qui gagnent à la loterie, un foyer d'une maladie dans une rue, deux chansons qui se ressemblent : ces événements deviennent des quasi-certitudes à grande échelle, et traiter chacun d'eux comme individuellement improbable relève de la même erreur arithmétique que celle commise au sujet des personnes et des anniversaires.
La bonne question n'est jamais « quelle est l'improbabilité de cette coïncidence particulière ? ». C'est « combien y avait-il d'occasions pour qu'une coïncidence de ce genre se produise ? ». Ces deux nombres diffèrent d'un facteur qui croît de manière quadratique, ce qui est amplement suffisant pour transformer un sujet d'étonnement en une certitude attendue.
Deux objections qui méritent réponse
« Les anniversaires ne sont pas uniformes. » Ils ne le sont pas — on enregistre davantage de naissances à la fin de l'été dans l'hémisphère nord, moins le 25 décembre et le 29 février, et une baisse visible le week-end en raison des accouchements programmés. Mais la non-uniformité rend toujours les correspondances plus probables, jamais moins : le regroupement concentre les personnes sur un nombre plus restreint de jours effectifs. L'hypothèse d'uniformité est donc conservatrice, et 23 est tout au plus une légère surestimation.
« Les jumeaux et les personnes venues ensemble. » Les groupes réels ne constituent pas des échantillons aléatoires. Une pièce réunissant des frères et sœurs, ou une classe d'écoliers sélectionnée selon un seuil d'âge, présente des corrélations que le modèle n'intègre pas. Le calcul sert de référence pour des tirages indépendants, et lorsque les tirages ne sont pas indépendants, c'est l'indépendance qu'il convient de défendre, non l'arithmétique.
La formule à retenir
S'il y a N catégories équiprobables et que vous effectuez k tirages, le nombre espéré de paires en collision est d'environ k²/2N. En égalant cette valeur à un, on obtient k ≈ √(2N) — la même racine carrée, obtenue en comptant le nombre espéré de collisions plutôt que des probabilités, et plus facile à calculer de tête.
Pour mille emplacements de hachage : √2000 ≈ 45, attendez-vous donc à une première collision aux alentours de quarante. Pour une somme de contrôle de 32 bits : 2¹⁶ = 65 536 éléments, ce qu'un fichier journal atteint en une après-midi. Pour 365 jours : 27, suffisamment proche de 23 pour que l'estimation soit digne de confiance.
L'habitude consiste à recourir à la racine carrée dès que l'on entend « quelle est la probabilité d'un doublon », et à constater que la réponse survient bien plus tôt que la taille de l'ensemble ne le suggère. L'outil Birthday Paradox trace la courbe, et sa raideur entre 20 et 30 personnes est la partie qui ne survit pas à une description par les mots.