Le paradoxe des anniversaires : pourquoi 23 personnes suffisent

Lors de la Coupe du monde 2014, des journalistes ont passé au crible les 32 sélections. Chaque équipe comptait exactement 23 joueurs, et dans 16 des 32, soit la moitié, au moins deux joueurs partageaient le même anniversaire. Personne n'avait rien arrangé. C'est simplement ce que fait le nombre 23.

Voilà le paradoxe des anniversaires : dans une salle de 23 personnes, un anniversaire partagé est plus probable que le contraire. Il y a 365 anniversaires possibles et seulement 23 personnes, donc l'affirmation semble absurde, et cette réaction est presque universelle. Mais le résultat n'est pas un tour de passe-passe, pas une illusion statistique, et il ne dépend d'aucune clause cachée. C'est un court argument de dénombrement, et une fois qu'on voit quel décompte l'intuition effectue à la place du bon, le paradoxe se dissout en quelque chose de presque évident.

L'affirmation, énoncée avec soin

Prends 23 personnes dont les anniversaires sont indépendants et équiprobables sur chacun des 365 jours, en ignorant pour l'instant le 29 février. L'affirmation est :

La probabilité qu'au moins deux d'entre elles partagent le même anniversaire est de 50.7%, légèrement mieux qu'un pile ou face.

Deux détails comptent. Premièrement, l'affirmation porte sur deux personnes quelconques qui coïncident, pas sur la coïncidence avec une personne particulière. Deuxièmement, « partager un anniversaire » signifie le même jour de l'année, comme le 14 mars, pas le même jour et la même année. Les deux détails semblent mineurs. L'un d'eux, comme nous allons le voir, est tout le paradoxe.

La démonstration n'est qu'un décompte

La question directe, quelle est la probabilité que quelqu'un coïncide avec quelqu'un, est difficile à attaquer de front, parce que les coïncidences peuvent se produire de nombreuses façons qui se chevauchent. Les probabilités ont un geste standard pour cela : calculer la probabilité que rien ne se passe, puis la soustraire de 1. Pour un tour complet des raisons qui rendent ce geste légitime, voir la compréhension intuitive des probabilités.

C'est toute la démonstration : compter les paires pour voir pourquoi une coïncidence est plausible, puis multiplier 23 fractions pour voir exactement à quel point. Aucune machinerie avancée, rien à admettre sur parole. Chaque étape se vérifie avec une calculatrice.

Et la courbe continue de grimper vite. À 30 personnes, la probabilité d'une coïncidence est de 70.6%. À 50 personnes, elle est de 97.0%. À 70 personnes, elle est de 99.9% : un anniversaire partagé est presque garanti alors que 295 jours de l'année restent intacts.

Là où l'intuition se trompe

Le paradoxe des anniversaires trompe les gens de façon fiable, et il les trompe d'une manière précise et diagnosticable : ils répondent à la mauvaise question.

Entends l'énigme, et ton esprit lui substitue discrètement une version dont tu es la vedette. Quelles sont les chances que quelqu'un ici partage mon anniversaire ? Cette question-là a vraiment une petite réponse. Dans une salle de 23 personnes, il n'y a que 22 autres personnes, chacune coïncidant avec toi avec une probabilité de 1/365, et la probabilité totale que quelqu'un coïncide avec toi est d'environ 6%. Si l'énigme portait sur ton anniversaire, les sceptiques auraient raison.

Mais l'énigme porte sur n'importe quelle coïncidence. Toi contre chacun des autres : 22 paires. Mais aussi la personne 2 contre la personne 3, la personne 7 contre la personne 19, et toutes les autres combinaisons qui ne t'impliquent pas du tout : 231 paires de plus, pour 253 au total. L'intuition compte les 22 comparaisons qu'elle peut se représenter de l'intérieur et reste structurellement aveugle aux 231 dont elle ne fait pas partie. Le paradoxe n'est pas que les probabilités se comportent étrangement. C'est qu'une salle de 23 personnes contient onze fois plus de comparaisons que ce qu'une seule personne expérimente.

Il existe une façon élégante de mesurer l'ampleur de cet écart. Pour obtenir 50% de chances que quelqu'un coïncide avec toi en particulier, 22 autres personnes sont très loin de suffire : il te faut 253 personnes en plus de toi. Le nombre d'autres personnes nécessaires pour coïncider avec une date fixée est le même que le nombre de paires parmi 23 personnes. Ce n'est pas une coïncidence, ce sont les deux questions résolues par la même arithmétique, et cela mesure précisément à quel point le cadrage « mon anniversaire » sous-estime la situation.

Les petites lignes qui rendent la réponse honnête

Le calcul supposait 365 anniversaires équiprobables et pas de jour bissextile. Les deux hypothèses sont fausses dans le monde réel, il est donc légitime de demander si les 50.7% survivent au contact de la réalité.

Ils survivent, et en fait la réalité aide. Ajouter le 29 février comme rare 366e jour fait baisser la probabilité d'un cheveu, bien trop peu pour décaler le seuil de 23. Les anniversaires inégalement répartis poussent dans l'autre sens : les vraies données de naissance montrent des pics saisonniers, certains mois étant régulièrement plus chargés que d'autres. Toute irrégularité de ce genre rend les collisions plus probables, parce que concentrer la probabilité sur des jours populaires est exactement ce dont les collisions se nourrissent. Le modèle uniforme est le cadre le plus défavorable possible pour le paradoxe, et il franchit quand même les 50%.

Cette robustesse mérite qu'on s'y arrête, parce que c'est l'inverse du comportement habituel des énigmes à saveur de paradoxe. Le problème de Monty Hall, par exemple, est célèbre pour sa sensibilité aux petites lignes : change ce que sait le présentateur et la réponse change. Le paradoxe des anniversaires est le frère solide. Chaque écart réaliste par rapport aux hypothèses du manuel pousse la probabilité vers le haut, donc la surprise survit à toutes les chicanes.

Du tour de fête au cassage de fonctions de hachage

Le paradoxe des anniversaires mériterait sa place comme pari de fête, mais il a aussi un travail sérieux. En cryptographie, il fixe le prix de la recherche de collisions, et toute une stratégie d'attaque porte son nom.

Une fonction de hachage compresse n'importe quelle entrée en une empreinte de taille fixe, et la sécurité dépend souvent du fait que personne ne trouve deux entrées différentes avec la même empreinte. Suppose que les empreintes font 128 bits, soit 2 puissance 128 possibilités, un nombre astronomiquement grand. Deviner une entrée qui atteint une empreinte précise demande vraiment de l'ordre de 2 puissance 128 tentatives, sans espoir pour toujours. Mais un attaquant qui veut juste une collision quelconque, deux entrées qui coïncident, joue au jeu des anniversaires : génère des entrées aléatoires, et par la règle de la racine carrée, une collision est attendue après environ 2 puissance 64 tentatives. C'est l'attaque des anniversaires, et 2 puissance 64 est un grand nombre mais pas un nombre sûr ; des attaquants déterminés l'ont franchi.

Le paradoxe, autrement dit, divise par deux la force effective d'un hachage, mesurée en bits. C'est pourquoi les cryptographes qui veulent 128 bits de résistance aux collisions utilisent des hachages à sorties de 256 bits : la racine carrée de 2 puissance 256 est 2 puissance 128, ce qui met même le raccourci des anniversaires hors de portée. Un motif qui décide combien de personnes tu invites à une fête décide aussi combien de bits protègent ta connexion bancaire, et c'est le même calcul les deux fois.

Essaie-le, parce que cela ne coûte rien

Comme les meilleurs résultats de probabilités, celui-ci est bon marché à tester. N'importe quel groupe d'environ 25 personnes fait l'affaire : une salle de classe, un étage de bureaux, un effectif d'équipe, une liste d'invités de mariage. Demande l'anniversaire de chacun et guette la coïncidence. Un seul groupe ne prouve rien dans un sens ou dans l'autre, bien sûr. L'affirmation est 50.7%, pas une certitude, donc le pari perd presque une fois sur deux.

La version persuasive, c'est la répétition. Les effectifs sportifs sont idéaux pour cela, et c'est pourquoi la Coupe du monde revient sans cesse dans les articles sur le paradoxe des anniversaires : des sélections de 23 sont l'expérience exactement à la taille du seuil, déjà constituées et publiques. Vérifie dix sélections et tu devrais t'attendre à des coïncidences dans environ cinq. Ou simule-le : quelques lignes de code qui attribuent 23 nombres aléatoires de 1 à 365 et cherchent les répétitions, exécutées dix mille fois, atterriront à une fraction de pourcent de 0.507. L'argument des 23 fractions multipliées fait une prédiction précise, le monde continue de lui donner raison, et il existe peu de façons plus rapides de sentir les probabilités devenir réelles.

Le zen de tout cela

Le paradoxe des anniversaires perdure parce qu'il est une miniature parfaite d'un mode d'échec général. L'intuition évalue les situations depuis un seul point de vue, le tien, et dans les situations combinatoires, le point de vue unique se trompe d'un facteur qui grandit avec la foule. Rien dans le hasard ne se comporte mal. L'erreur tient entièrement à la question qui reçoit silencieusement une réponse.

Et le remède est le même que toujours en probabilités : refuser de deviner, et compter. Compte les paires et la plausibilité apparaît. Multiplie les fractions et le nombre exact en tombe. Le même décompte réapparaît ensuite, inchangé, dans la conception des systèmes cryptographiques, ce qui est la leçon discrète de tout le sujet : un argument probabiliste ne sait pas s'il sert un pari de comptoir ou la sécurisation d'internet.

Vingt-trois personnes. Deux cent cinquante-trois chances. La salle n'a jamais été aussi vide qu'elle en avait l'air.