Paradoxe des anniversaires
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (Le jour ou la journée est l'intervalle qui sépare le lever du coucher du Soleil ; c'est la période entre deux nuits, pendant laquelle les rayons du Soleil éclairent le ciel. Son début (par rapport à minuit heure locale) et sa durée...). Il se trouve que ce nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) est 23, ce qui choque un peu l'intuition. À partir d'un groupe de 57 personnes, la probabilité (La probabilité (du latin probabilitas) est une évaluation du caractère probable d'un évènement. En mathématiques, l'étude...) est supérieure à 99 %.

Cependant, il ne s'agit pas d'un paradoxe (Un paradoxe est une proposition qui contient ou semble contenir une contradiction logique, ou un raisonnement qui, bien que sans faille apparente, aboutit à une absurdité, ou encore, une situation...) dans le sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du ralentissement du vieillissement, suivi de son...) de contradiction (Une contradiction existe lorsque deux affirmations, idées, ou actions s'excluent mutuellement.) 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 %.

Les gens pensent en général à la probabilité que 2 personnes soient nées en même temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) un jour (Le jour ou la journée est l'intervalle qui sépare le lever du coucher du Soleil ; c'est la période entre deux nuits, pendant laquelle les rayons du Soleil...) donné, probabilité qui est en effet très faible.

Généralisation (La généralisation est un procédé qui consiste à abstraire un ensemble de concepts ou d'objets en négligeant les détails de façon à ce qu'ils puissent...)

Ce 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...) se généralise bien évidemment à la situation (En géographie, la situation est un concept spatial permettant la localisation relative d'un espace par rapport à son environnement proche ou non. Il inscrit un lieu dans...) plus abstraite que l'on peut énoncer sous la forme :

Soit E un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.). La probabilité p(n) que, parmi n éléments de E, chaque élément étant tiré uniformement dans tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui...) 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 (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un événement, etc.) 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 (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment démontrées à partir de propositions initiales, en s'appuyant sur un...)

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 ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme. Exemple : "Le total des dettes". ...) si on ne se fixe aucune contrainte, il a 365n possibilités. Si maintenant on veut des jours différents, nous obtenons un arrangement (La notion d'arrangement est utilisée en probabilités, et notamment pour les dénombrements en analyse combinatoire.) 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 (En sciences, particulièrement en physique, l'application numérique est l'obtention de la valeur numérique d'une grandeur physique à partir de celles d'autre grandeurs lorsque l'on connaît une formule analytique...), on trouve 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 (Un pourcentage est une façon d'exprimer une proportion ou une fraction dans un ensemble. Une expression comme « 45 % » (lue « 45 pour cent ») est en réalité la...) indiqué.

n p(n)
10 12%
20 41%
30 70%
50 97%
100 99.99996%
200 99.9999999999999999999999999998%
300 \left(1 - \left(7 .10^{-73}\right)\right)\cdot100\%
350 \left(1 - \left(3 . 10^{-131}\right)\right)\cdot100\%
≥366 100% (par le Théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un...) des tiroirs)

Approximation (Une approximation est une représentation grossière c'est-à-dire manquant de précision et d'exactitude, de quelque chose, mais encore assez...)

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é (En physique et en mathématiques, un développement limité d'une fonction f au voisinage de x0, est l'écriture d'une fonction sous la forme d'une fonction polynôme et d'un reste .) 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 (Tableau peut avoir plusieurs sens suivant le contexte employé :) 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 (La couleur est la perception subjective qu'a l'œil d'une ou plusieurs fréquences d'ondes lumineuses, avec une (ou des) amplitude(s) donnée(s).).

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

Le paradoxe des anniversaires est utilisé en cryptographie (La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets ou clés.) 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 (Une collision est un choc direct entre deux objets. Un tel impact transmet une partie de l'énergie et de l'impulsion de l'un des corps au second.) avec une probabilité p=\frac{1}{2}, à savoir essentiellement la racine carrée (La racine carrée d’un nombre réel positif x est le nombre positif dont le carré vaut x. On le note ou x½; dans cette expression, x...) 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 |2N/2 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.

Page générée en 0.092 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique