Paradoxe des anniversaires
157549
31615747
2008-07-16T07:26:18Z
Jerome66
35967
/* Démonstration */ correction lien interne
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 à {{unité|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 à {{unité|50|%}}.
Les personnes interrogées pensent en général à la probabilité que 2 personnes soient nées un même jour '''donné''', probabilité en effet très faible.
==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 bien évidemment à la situation plus abstraite que l'on peut énoncer sous la forme :
Soit <math>E</math> un [[ensemble]] fini. La probabilité <math>p(n)</math> que, parmi <math>n</math> éléments de <math>E</math>, chaque élément étant tiré uniformément dans tout l'ensemble <math>E</math>, deux éléments au moins soient identiques vaut :
:<math>p(n)=1 - \frac{|E|!}{(|E|-n)!} \cdot \frac{1}{|E|^n}</math>
où la notation <math>|E|</math> désigne le [[Nombre cardinal|cardinal]] de l'ensemble <math>E</math>.
Une valeur approchée est donnée par
:<math>p(n)\approx 1 - e^{-\frac{n^2}{2\cdot |E|}}</math>
et une valeur de <math>n</math> en fonction de <math>p</math> par
:<math>n(p)\approx \sqrt {2\cdot |E| \ln\left(\frac{1}{1-p}\right)}</math>
== 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ù <math>n</math> personnes ont des jours d'anniversaires différents et nous diviserons par le nombre de possibilités. Il y a <math>n</math> personnes, pour chacune il y a 365 jours possibles, donc au total si on ne se fixe aucune contrainte, il a <math>365^n</math> possibilités. Si maintenant on veut des jours différents, nous obtenons un [[arrangement]] de <math>n</math> parmi 365, soit :<math>A^n_{365}=(365-0)(365-1)...(365-n+1)=\frac{365!}{(365-n)!}</math>.
On a donc
:<math>\overline{p}(n)= \frac{365!}{(365-n)!} \cdot \frac{1}{365^n}</math>
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 <math>p(n)=1-\overline{p}(n)</math>.
En faisant l'application numérique, on trouve {{unité|50.72|%}} pour 23 personnes … Le calcul exposé néglige la date du [[29 février]] dont la prise en compte changerait très peu le pourcentage indiqué.
{| class="wikitable gauche"
!''n''!!''p''(''n'')
|-
|10 || {{unité|12|%}}
|-
|20 || {{unité|41|%}}
|-
|30 || {{unité|70|%}}
|-
|50 || {{unité|97|%}}
|-
|100 || {{unité|99.99996|%}}
|-
|200 || {{unité|99.9999999999999999999999999998|%}}
|-
|300 ||<math> \left(1 - \left(7 .10^{-73}\right)\right)\cdot100\%</math>
|-
|350 || <math>\left(1 - \left(3 . 10^{-131}\right)\right)\cdot100\%</math>
|-
|≥366 || {{unité|100|%}} (par le [[Principe des tiroirs|Théorème des tiroirs]])
|}
{{-}}
== Approximation ==
=== p(n) ===
La probabilité <math>\overline{p}(n)=1-p(n)</math> peut se réécrire sous la forme :
:<math>\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)</math>
Or, on a le [[développement limité]] <math>e^x=1+x+o(x)</math> pour <math>x</math> [[Voisinage|voisin]] de 0. Cela conduit à l'approximation :
:<math>\overline{p}(n)\approx \prod_{i=0}^{n-1}e^{-\frac{i}{365}}</math>
:<math>\overline{p}(n)\approx e^{-\frac{ \sum_{i=0}^{n-1} i}{365}}</math>
Or, la somme des entiers de 0 à <math>n-1</math> vaut <math>(n-1)n/2</math>, ce qui donne finalement :
:<math>\overline{p}(n)\approx e^{-\frac{ n^2}{2\cdot 365}}</math>
En revenant à <math>p(n)</math> :
:<math>p(n)\approx 1- e^{-\frac{ n^2}{2\cdot 365}}</math>
=== n(p) ===
L'approximation de <math>p(n)</math> permet d'obtenir simplement une approximation du nombre de personnes nécessaire pour avoir une probabilité donnée <math>p</math> d'avoir au moins deux personnes avec le même jour d'anniversaire.
On obtient ainsi :
:<math>n(p)\approx \sqrt{2\cdot 365\ln\left(\frac{1}{1-p}\right)}</math>
=== Quelques valeurs numériques===
Le tableau ci-dessous indique, pour une probabilité <math>p</math>, l'approximation <math>n(p)</math>, puis, sur la même ligne, l'approximation de la probabilité pour l'entier inférieur ou égal à <math>n(p)</math> (noté <math>\lfloor n\rfloor</math>) et celle de probabilité pour l'entier supérieur ou égal à <math>n(p)</math> (noté <math>\lceil n\rceil</math>). Normalement, la probabilité <math>p</math> 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 <span style="color:magenta">couleur</span>.
{| class="wikitable"
|-----
| <math>p</math> || <math>n</math> || <math>\lfloor n\rfloor</math>
| <math>p(\lfloor n\rfloor)</math> || <math>\lceil n\rceil</math>
| <math>p(\lceil n\rceil)</math>
|-----
| <div style="color:magenta">{{formatnum:0.01}}</div>
| <div style="color:magenta"> {{formatnum:2.70864}}</div>
| align="right" | 2 || {{formatnum:0.00274}} || align="right" | 3
| <div style="color:magenta">{{formatnum:0.00820}}</div>
|-----
| {{formatnum:0.05}} || {{formatnum:6.11916}} || align="right" | 6
| {{formatnum:0.04046}} || align="right" | 7 || {{formatnum:0.05624}}
|-----
| <div style="color:magenta">{{formatnum:0.1}}</div>
| <div style="color:magenta"> {{formatnum:8.77002}}</div>
| align="right" | 8 || {{formatnum:0.07434}} || align="right" | 9
| <div style="color:magenta">{{formatnum:0.09462}}</div>
|-----
| <div style="color:magenta">{{formatnum:0.2}}</div>
<td><div style="color:magenta">{{formatnum:12.76302}}</div>
| align="right" | 12 || {{formatnum:0.16702}} || align="right" | 13
| <div style="color:magenta">{{formatnum:0.19441}}</div>
|-----
| {{formatnum:0.3}} || {{formatnum:16.13607}} || align="right" | 16
| {{formatnum:0.28360}} || align="right" | 17 || {{formatnum:0.31501}}
|-----
| {{formatnum:0.5}} || {{formatnum:22.49439}} || align="right" | 22
| {{formatnum:0.47570}} || align="right" | 23 || {{formatnum:0.50730}}
|-----
| {{formatnum:0.7}} || {{formatnum:29.64625}} || align="right" | 29
| {{formatnum:0.68097}} || align="right" | 30 || {{formatnum:0.70632}}
|-----
| {{formatnum:0.8}} || {{formatnum:34.27666}} || align="right" | 34
| {{formatnum:0.79532}} || align="right" | 35 || {{formatnum:0.81438}}
|-----
| {{formatnum:0.9}} || {{formatnum:40.99862}} || align="right" | 40
| {{formatnum:0.89123}} || align="right" | 41 || {{formatnum:0.90315}}
|-----
| {{formatnum:0.95}} || {{formatnum:46.76414}} || align="right" | 46
| {{formatnum:0.94825}} || align="right" | 47 || {{formatnum:0.95477}}
|-----
| <div style="color:magenta">{{formatnum:0.99}}</div>
| <div style="color:magenta">{{formatnum:57.98081}}</div>
| align="right" | 57
| <div style="color:magenta">{{formatnum:0.99012}}</div>
| align="right" | 58 || {{formatnum: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]]. On montre que la stratégie des codes détecteurs d’erreurs s’avère, du point de vue statistique, isomorphe au paradoxe des anniversaires.
Le paradoxe des anniversaires est utilisé en [[cryptographie]] pour élaborer des attaques sur les [[fonction de hachage|fonctions de hachage]]. Une des contraintes imposées sur ces fonctions, pour une utilisation cryptographique, est de produire peu de [[pseudo-collision|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é <math>p=\frac{1}{2}</math>, à 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 [[Bit (informatique)|bits]] alors l'ensemble d'arrivée possède <math>2^N</math> éléments et il faut environ <math>2^\frac N2</math> hachés d'éléments distincts pour produire une collision avec {{unité|50|%}} de chance ; les sorties de la fonction pouvant être comparées à des personnes avec des anniversaires se répartissant sur <math>2^N</math> valeurs.
== Voir aussi ==
=== Article connexe ===
* [[Condensat de Bose-Einstein]]
=== Lien externe ===
* [http://www.nestel.net/maple/bd/bd.html Calcul de probabilité à l'aide de Maple]
{{Mesures de sécurité cryptographique}}
[[Catégorie:Paradoxe probabiliste|Anniversaire]]
[[Catégorie:Anniversaire]]
[[cs:Narozeninový problém]]
[[de:Geburtstagsparadoxon]]
[[en:Birthday problem]]
[[es:Paradoja del cumpleaños]]
[[fi:Syntymäpäiväongelma]]
[[gl:Paradoxo do aniversario]]
[[he:פרדוקס יום ההולדת]]
[[hu:Születésnap-paradoxon]]
[[it:Paradosso del compleanno]]
[[ja:誕生日のパラドックス]]
[[ko:생일 문제]]
[[lt:Gimimo dienų paradoksas]]
[[nl:Verjaardagenparadox]]
[[pl:Paradoks dnia urodzin]]
[[pt:Paradoxo do aniversário]]
[[ru:Парадокс дней рождения]]
[[sv:Födelsedagsparadoxen]]
[[zh:生日悖论]]