Attaque anniversaire

Paradoxe des anniversaires

Le paradoxe des anniversaires, dû à Richard von Mises, est à l'origine une estimation probabiliste du nombre de personnes que l'on doit réunir pour avoir une chance sur deux que deux personnes de ce groupe aient leur anniversaire le même jour de l'année. Il se trouve que ce nombre est 23, ce qui choque un peu l'intuition. À partir d'un groupe de 57 personnes, la probabilité est supérieure à 99 %.

Cependant, il ne s'agit pas d'un paradoxe dans le sens de contradiction logique ; c'est un paradoxe, dans le sens où c'est une vérité mathématique qui contredit l'intuition : la plupart des gens estiment que cette probabilité est très inférieure à 50 %.

(Par souci de simplicité, tout l'article est rédigé en supposant que toutes les années sont non-bissextiles. Prendre en compte le 29 février changerait peu les résultats, mais rendrait les calculs très délicats pour les applications où les personnes ne sont pas nées la même année)

Sommaire

Comprendre le problème

La clé consiste à se demander quelles sont les chances qu'aucune paire de personnes ne soit née le même jour. Pour chaque personne ajoutée dans la pièce, le nombre de dates non déjà prises diminue. La première personne a donc 365 choix, la seconde 364, la troisième 363, la quatrième 362, et ainsi de suite.

Le problème consiste à se demander si une quelconque paire d'individus dans la pièce a la même date d'anniversaire.

Dans un groupe de 23 personnes, il y a 23 x 22 ÷ 2 = 253 paires possibles, ce qui représente plus de la moitié du nombre de jours contenu dans une année. À partir de 28, le nombre de paires excède le nombre de jours, et les possibilités sont grandement accrues.

Généralisation

Ce paradoxe des anniversaires se généralise à la situation plus abstraite que l'on peut énoncer sous la forme :

Soit E un ensemble fini. La probabilité p(n) que, parmi n éléments de E, chaque élément étant tiré uniformément dans tout l'ensemble E, deux éléments au moins soient identiques vaut :

p(n)=1 - \frac{|E|!}{(|E|-n)!} \cdot \frac{1}{|E|^n}

où la notation | E | désigne le cardinal de l'ensemble E.

Une valeur approchée est donnée par

p(n)\approx 1 - e^{-\frac{n^2}{2\cdot |E|}}

et une valeur de n en fonction de p par

n(p)\approx \sqrt {2\cdot |E| \ln\left(\frac{1}{1-p}\right)}

Démonstration

Nous donnons une preuve pour le cas d'origine, avec des jours d'anniversaires, mais cela se transpose simplement au cas de la généralisation énoncé.

Le plus simple pour obtenir le résultat annoncé est de calculer la probabilité que chaque personne ait un jour anniversaire différent de celui des autres. On va procéder par dénombrement, c'est-à-dire, que nous allons compter le nombre de cas où n personnes ont des jours d'anniversaires différents et nous diviserons par le nombre de possibilités. Il y a n personnes, pour chacune il y a 365 jours possibles, donc au total si on ne se fixe aucune contrainte, il a 365n possibilités. Si maintenant on veut des jours différents, nous obtenons un arrangement de n parmi 365, soit :A^n_{365}=(365-0)(365-1)...(365-n+1)=\frac{365!}{(365-n)!}.

On a donc

\overline{p}(n)= \frac{365!}{(365-n)!} \cdot \frac{1}{365^n}

Or, l'évènement « un jour anniversaire différent par personne » est le complémentaire de « au moins deux identiques ». Par conséquent la probabilité recherchée est p(n)=1-\overline{p}(n).

En faisant l'application numérique, on trouve 50,73 % pour 23 personnes.

n p(n)
5 2,71 %
10 11,69 %
15 25,29 %
20 41,14 %
25 56,87 %
30 70,63 %
40 89,12 %
50 97,04 %
60 99,41 %
80 99,99 %
100 99,99997 %
200 99,9999999999999999999999999998 %
300  \left(1 - \left(7 .10^{-73}\right)\right)\cdot100\%
350 \left(1 - \left(3 . 10^{-131}\right)\right)\cdot100\%
>365 100 % (par le Théorème des tiroirs)

Approximation

p(n)

La probabilité \overline{p}(n)=1-p(n) peut se réécrire sous la forme :

\overline{p}(n)=\left(1-\frac{0}{365}\right)\left(1-\frac{1}{365}\right)...\left(1-\frac{i}{365}\right)...\left(1-\frac{n-1}{365}\right)

Or, on a le développement limité ex = 1 + x + o(x) pour x voisin de 0. Cela conduit à l'approximation :

\overline{p}(n)\approx \prod_{i=0}^{n-1}e^{-\frac{i}{365}}
\overline{p}(n)\approx e^{-\frac{ \sum_{i=0}^{n-1} i}{365}}

Or, la somme des entiers de 0 à n − 1 vaut (n − 1)n / 2, ce qui donne finalement :

\overline{p}(n)\approx e^{-\frac{ n^2}{2\cdot 365}}

En revenant à p(n) :

p(n)\approx 1- e^{-\frac{ n^2}{2\cdot 365}}

n(p)

L'approximation de p(n) permet d'obtenir simplement une approximation du nombre de personnes nécessaire pour avoir une probabilité donnée p d'avoir au moins deux personnes avec le même jour d'anniversaire. On obtient ainsi :

n(p)\approx \sqrt{2\cdot 365\ln\left(\frac{1}{1-p}\right)}

Quelques valeurs numériques

Le tableau ci-dessous indique, pour une probabilité p, l'approximation n(p), puis, sur la même ligne, l'approximation de la probabilité pour l'entier inférieur ou égal à n(p) (noté \lfloor n\rfloor) et celle de probabilité pour l'entier supérieur ou égal à n(p) (noté \lceil n\rceil). Normalement, la probabilité p fixée au départ doit être comprise entre ces deux valeurs. Les entrées ne vérifiant pas cette condition sont signalées en couleur.

p n \lfloor n\rfloor p(\lfloor n\rfloor) \lceil n\rceil p(\lceil n\rceil)
0,01
2,70864
2 0,00274 3
0,00820
0,05 6,11916 6 0,04046 7 0,05624
0,1
8,77002
8 0,07434 9
0,09462
0,2
12,76302
12 0,16702 13
0,19441
0,3 16,13607 16 0,28360 17 0,31501
0,5 22,49439 22 0,47570 23 0,50730
0,7 29,64625 29 0,68097 30 0,70632
0,8 34,27666 34 0,79532 35 0,81438
0,9 40,99862 40 0,89123 41 0,90315
0,95 46,76414 46 0,94825 47 0,95477
0,99
57,98081
57
0,99012
58 0,99166

Applications

Dans Le Trésor des Paradoxes (Éd Belin, 2007), les auteurs notent que l’informaticien américain Robert Mac Eliece a établi l'intérêt du paradoxe des anniversaires en informatique, pour s’assurer de la fiabilité des mémoires d’ordinateur, grâce à des codes détecteurs d’erreurs, fondés notamment sur les travaux de Richard Hamming aux Laboratoires Bell. La stratégie des codes détecteurs d’erreurs s’avère, du point de vue statistique, similaire au paradoxe des anniversaires. Le paradoxe des anniversaires est utilisé en cryptographie pour élaborer des attaques sur les fonctions de hachage. Une des contraintes imposées sur ces fonctions, pour une utilisation cryptographique, est de produire peu de collisions, autrement dit, de rarement prendre la même valeur sur des entrées différentes.

Le paradoxe des anniversaires donne une borne sur le nombre moyen d'éléments nécessaires pour avoir une collision avec une probabilité p=\frac{1}{2}, à savoir essentiellement la racine carrée du nombre de valeurs possibles pour la fonction de hachage, sous l'hypothèse que cette fonction est uniformement distribuée sur ses valeurs d'arrivée.

Plus concrètement, si une fonction de hachage a une sortie de N bits alors l'ensemble d'arrivée possède 2N éléments et il faut environ 2^\frac N2 hachés d'éléments distincts pour produire une collision avec 50 % de chance ; les sorties de la fonction pouvant être comparées à des personnes avec des anniversaires se répartissant sur 2N valeurs.

Anecdote

Dans Le Livre qui rend fou, Raymond Smullyan raconte que lui-même a fait établir la formule à ses 19 élèves. Il conclut après application numérique qu'il y a nettement moins d'une chance sur deux (un peu moins de 38%) pour que deux élèves aient leur anniversaire le même jour. Un élève lui répond qu'il parie que c'est tout de même le cas. Le professeur fait l'appel en demandant aux élèves de donner leur date de naissance, et éclate de rire avant la fin, suivi de toute la classe, en se souvenant que deux de ses élèves sont jumeaux.

Voir aussi

Lien externe

Ce document provient de « Paradoxe des anniversaires ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Attaque anniversaire de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Luis Attaque —  Pour l’article homophone, voir Louise Attaque. Luis Attaque Présentateur(s) Luis Fernandez Fl …   Wikipédia en Français

  • Première attaque atomique — Bombardements atomiques de Hiroshima et Nagasaki Champignon atomique produit par l explosion sur Hiroshima, le 6 août 1945 Les bombardements atomiques de Hiroshima et Nagasaki ont eu lieu les 6 et 9 août 1945 à l initiative des États… …   Wikipédia en Français

  • Équipe du 75e anniversaire de la NFL — L’équipe du 75e anniversaire de la NFL a été désignée par une sélection de journalistes et de personnel de la National Football League (NFL) en 1994. Attaque Source:[1] Position Joueur Équipe(s) Université Quarterback Sammy Baugh Washington… …   Wikipédia en Français

  • Specifications SHA-1 — Spécifications SHA 1 SHA 1 est une fonction de hachage cryptographique qui fournit une empreinte de 160 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article principal : SHA 1. Sommaire 1… …   Wikipédia en Français

  • Spécifications SHA-1 — SHA 1 est une fonction de hachage cryptographique qui fournit une empreinte de 160 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article principal : SHA 1. Sommaire 1 Introduction 2 Symboles et… …   Wikipédia en Français

  • Spécifications sha-1 — SHA 1 est une fonction de hachage cryptographique qui fournit une empreinte de 160 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article principal : SHA 1. Sommaire 1 Introduction 2 Symboles et… …   Wikipédia en Français

  • Specifications SHA-256 — Spécifications SHA 256 SHA 256 est une fonction de hachage cryptographique dérivée de SHA 1 qui fournit une empreinte de 256 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article SHA 256. Sommaire 1… …   Wikipédia en Français

  • Spécifications SHA-256 — SHA 256 est une fonction de hachage cryptographique dérivée de SHA 1 qui fournit une empreinte de 256 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article SHA 256. Sommaire 1 Introduction 2 Symboles et… …   Wikipédia en Français

  • Spécifications sha-256 — SHA 256 est une fonction de hachage cryptographique dérivée de SHA 1 qui fournit une empreinte de 256 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article SHA 256. Sommaire 1 Introduction 2 Symboles et… …   Wikipédia en Français

  • Logarithme Discret — En algèbre générale et dans ses applications d arithmétique modulaire, le logarithme discret est défini en théorie des groupes par analogie avec le logarithme ordinaire. On considère un groupe cyclique G d ordre n (dont la loi sera notée… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”