Le paradoxe des anniversaires

Le paradoxe

Demandez combien d’invités il faut à une fête pour que deux d’entre eux aient probablement le même anniversaire : la plupart des gens répondront environ 180, la moitié de 365. La vraie réponse est 23 : la probabilité est alors de 50,7 %. Avec 57 invités, elle atteint 99 %. On parle de paradoxe non pas parce que c’est contradictoire, mais parce que cela va si fortement à l’encontre de notre intuition.

Pourquoi l’intuition se trompe

Dans une pièce, nous raisonnons inconsciemment à partir de nous-mêmes : quelle est la probabilité que quelqu’un ait le même anniversaire que moi ? Avec 365 jours, cette probabilité est faible. Mais le paradoxe porte sur toutes les paires possibles de la pièce, et non sur une coïncidence avec une personne en particulier : A et B, B et C, A et C, et ainsi de suite. Avec 23 personnes, on peut former 253 paires différentes, et chacune d’elles pourrait avoir le même anniversaire.

Les paires croissent comme le carré

n personnes forment n × (n − 1) / 2 paires : 10 personnes forment 45 paires, 23 en forment 253, 57 en forment 1 596 et 100 en forment 4 950. Chaque paire partage un anniversaire avec une probabilité de 1/365, donc 253 paires donnent en moyenne 253/365 ≈ 0,69 paire avec un anniversaire commun. Doubler le groupe multiplie à peu près par quatre le nombre de paires, et c’est pourquoi la probabilité d’un anniversaire commun grimpe en flèche.

Le calcul étape par étape

Le plus simple est de calculer la probabilité que personne ne partage son anniversaire avec un autre, puis de la soustraire de 100 %. La première personne prend n’importe quel jour. La deuxième a une probabilité de 364/365 de ne pas avoir le même anniversaire. La troisième a une probabilité de 363/365 de se distinguer des deux premières, et ainsi de suite. Pour 23 personnes :

365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49,3 %

Comme la probabilité que tout le monde ait un anniversaire différent est de 49,3 %, l’événement contraire, au moins un anniversaire commun, a une probabilité de 100 % − 49,3 % = 50,7 %.

Quelqu’un qui a le même anniversaire que vous

La probabilité que quelqu’un ait le même anniversaire que vous est une autre question. Chacune des n − 1 autres personnes manque votre anniversaire avec une probabilité de 364/365, donc la probabilité que quelqu’un l’ait est de 1 − (364/365)ⁿ⁻¹. Avec 23 personnes, ce n’est que 5,9 %, et il vous faut 253 autres personnes pour dépasser 50 %. Seules 22 des 253 paires d’un groupe de 23 vous incluent.

La règle de la racine carrée et les attaques des anniversaires

Pour N valeurs équiprobables, une répétition devient probable après environ 1,2 × √N tirages : √365 ≈ 19, et 1,2 × 19 ≈ 23. Cela compte beaucoup en sécurité informatique. Les attaquants utilisent les attaques des anniversaires pour trouver deux entrées ayant la même empreinte cryptographique, une collision, par exemple pour falsifier une signature numérique. Grâce au paradoxe des anniversaires, il leur faut bien moins d’essais que l’intuition ne le laisse penser : environ 2⁶⁴ pour une empreinte de 128 bits au lieu de 2¹²⁸. C’est pourquoi les fonctions de hachage modernes comme SHA-256 produisent des empreintes longues.

L’explorer dans PictorX

Ouvrez le paradoxe des anniversaires : un groupe de 23 personnes se forme sur un cercle, une personne à la fois. Chaque nouvel arrivant ajoute une ligne vers chaque personne déjà présente, et la légende compte les paires. Leurs anniversaires tombent sur un calendrier, et un jour qui en compte deux ou plus s’allume. En dessous, le calcul pour la taille du groupe figure à côté de la proportion de groupes testés qui avaient un anniversaire commun, et le graphique montre la probabilité pour chaque taille de groupe, pour deux personnes quelconques et pour quelqu’un qui a le même anniversaire que vous. Ajoutez des personnes une par une, choisissez de 2 à 366 personnes, testez jusqu’à 100 000 groupes, jusqu’à 10 000 par seconde, ou testez toutes les tailles de groupe et regardez les points tracer la courbe.