Paradoxe des anniversaires

Enthéorie des probabilités, leparadoxe des anniversairesest un résultat mathématique contre-intuitif concernant la probabilité que deux personnes, dans un groupe, aient le même anniversaire.
Il stipule que dans un groupe de 23 personnes, il y a plus d'une chance sur deux que deux personnes partagent le même anniversaire. À partir d'un groupe de57 personnes, la probabilité dépasse 99 %.
Il s'agit non pas d'unparadoxeau senslogique, mais plutôt d'un résultat qui défie l'intuition: si la question était posée à un groupe de personnes, la plupart des gens donneraient une estimation bien inférieure à la réalité.
L'étude détaillée de cette situation est due àRichard von Mises.
Par souci de simplicité, toutes les années sont supposées nonbissextiles. On néglige donc la possibilité d'être né un29 février, dont la prise en compte compliquerait les calculs pour une différence de résultat minime.
Le problème des anniversaires revient à choisir un nombrend'éléments dans un ensemble qui en contientN, sans retrait, c'est-à-dire sans retirer les éléments choisis, si bien que certains peuvent être identiques. Le paradoxe des anniversaires est un cas de ce type, car chacun a une date d'anniversaire considérée comme aléatoire et il n'y aa prioripas de raison autre que le hasard pour que deux dates soient identiques.
Ce problème est analogue à la situation suivante : au cours d'une soirée réunissantnpersonnes, de petits papiers sur lesquels sont notés les nombres de 1 àNsont placés dans une corbeille. Chacun tire un papier à tour de rôle, lit le nombre qu'il porte, puis le replace dans la corbeille. Il s'agit alors de déterminer les chances pour qu'au moins deux des nombres tirés soient identiques, oua contrario,pour qu'ils soient tous différents.
Pourcalculer cette probabilité, il est plus simple de calculer celle où tous les nombres sont différents puis d'utiliser la formulep(n)=1−p¯(n){\textstyle p(n)=1-{\overline {p}}(n)}afin d'en déduire le résultat. Le point clé qui trompe l'intuition est la sous-estimation des chances que deux nombres au moins soient identiques.
L'intuition est induite en erreur, car il y a mélange de deux questions différentes : « Quelles sont les chances que n'importe quel élément choisi soit identique à n'importe quel autre ? » et « Quelles sont les chances que n'importe quel élément choisi soit identique à un élément donné ? ».
La question posée est celle du premier énoncé, tandis qu'il est naturel d'avoir tendance à évaluer le second. Dans le cas des anniversaires, on a tendance à évaluer intuitivement la probabilité pour qu'une personne partage une date d’anniversaire précise, au lieu de la probabilité que deux personnes quelconques partagent le même anniversaire.
La question de savoir pourquoi l'intuition est ainsi trompée et ne semble pas spontanément capable d'aborder un problème de ce type est du domaine dessciences cognitives.
Une erreur fréquente dans la démonstration est de compter le nombre de paires, on omet alors le fait que les évènements ne sont pasdisjointset que trois personnes peuvent partager la même date de naissance.
Cette démonstration procède pardénombrement, c'est-à-dire en comptant le nombre de cas oùn{\displaystyle n}personnes (n⩽365{\displaystyle n\leqslant 365}) ont des jours d'anniversairesdifférentspuis en divisant par le nombre de possibilités et l'on fait une hypothèse d'équiprobabilitédes jours de naissance.
Il y an{\displaystyle n}personnes et 365 jours possibles pour chacune, ce qui signifie que si aucune contrainte n'est fixée, il y a au total365possibilités. En ajoutant la contrainte d'avoir des joursdifférents, nous obtenons unarrangementden{\displaystyle n}parmi 365, soit :A365n=(365−0)(365−1)...(365−n+1)=365!(365−n)!{\displaystyle A_{365}^{n}=(365-0)(365-1)...(365-n+1)={\frac {365!}{(365-n)!}}}On a donc
Il est aussi possible de voir cela comme une multiplication de probabilités d'évènementsindépendants, ce qui conduit au même résultat :
Or, l’évènement «chaque personne a un jour d'anniversaire différent» est lecomplémentairede « au moins deux personnes ont un jour d'anniversaire identique ». Par conséquent la probabilité recherchée estp(n)=1−p¯(n){\textstyle p(n)=1-{\overline {p}}(n)}.
En faisant l'application numérique, on trouve une probabilité de 50,73 % pour que deux personnes aient la même date d'anniversaire dans une assemblée de vingt-trois personnes.
Une explication possible du « paradoxe » réside dans la confusion intuitive entre le problème des anniversaires et l'un des problèmes suivants.
Pour un individu qui fait partie du groupe, la probabilité qu'une autre personne du groupe ait la même date d'anniversaire que lui est égale à :
q(n)=1−(364365)n−1{\displaystyle q(n)={\displaystyle 1-\left({\frac {364}{365}}\right)^{n-1}}}
Cela donne pourn=23{\displaystyle n=23}une probabilité très faible de 5,86 %, et il faut réunir au moins253 personnespour que cette probabilité soit supérieure à 50 %.
Ce problème est parfois confondu avec le problème classique des anniversaires.
Si lesn−1{\displaystyle n-1}autres personnes du groupe ont toutes des dates d'anniversaires différentes, la probabilité que l'une d'entre elles ait la même date qu'un individu donné vaut :
r(n)=n−1365{\displaystyle r(n)={\displaystyle {\frac {n-1}{365}}}}
Il faut alors qu'il y ait au moins183=⌈3652⌉{\textstyle 183=\left\lceil {\frac {365}{2}}\right\rceil }autres personnes pour que cette probabilité soit supérieure à 50% , ce qui est parfois la réponse donnée au problème initial.
Ce paradoxe des anniversaires se généralise à la situation plus abstraite que l'on peut énoncer sous la forme :
SoitE{\displaystyle E}unensemblefini decardinalN{\displaystyle N}. La probabilitép(n){\displaystyle p(n)}que, parmin{\displaystyle n}éléments deE{\displaystyle E}, chaque élément étant tiré uniformément (avec remise) dans tout l'ensembleE{\displaystyle E}, deux éléments au moins soient identiques vaut :
La probabilitép¯(n)=1−p(n){\displaystyle {\overline {p}}(n)=1-p(n)}peut se réécrire sous la forme :
Or, on a ledéveloppement limitéex=1+x+o(x){\displaystyle {\rm {e}}^{x}=1+x+o(x)}pourxvoisinde 0. Cela conduit à l'approximation :
Or, la somme des entiers de 0 àn−1{\displaystyle n-1}vautn(n−1)/2{\displaystyle n(n-1)/2}, ce qui donne finalement :
En revenant àp(n){\displaystyle p(n)}:
En résolvant enn{\displaystyle n}l'égalitép=1−e−n22⋅N{\displaystyle p=1-{\rm {e}}^{-{\frac {n^{2}}{2\cdot N}}}}on obtient une approximationn(p){\displaystyle n(p)}du nombre de personnes nécessaire pour avoir une probabilité donnéep{\displaystyle p}d'avoir au moins deux personnes avec le même jour d'anniversaire. On obtient :
Le tableau ci-dessous indique dans le cas originel (N=365{\displaystyle N=365}), pour une probabilitép{\displaystyle p}, l'approximationn(p){\displaystyle n(p)}indiquée ci-dessus, puis, sur la même ligne, l'approximation de la probabilité pour l'entier inférieur ou égal àn(p){\displaystyle n(p)}(noté⌊n⌋{\displaystyle \lfloor n\rfloor }) et celle de probabilité pour l'entier supérieur ou égal àn(p){\displaystyle n(p)}(noté⌈n⌉{\displaystyle \lceil n\rceil }). Normalement, la probabilitép{\displaystyle 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 encouleur.
Dans l'expression :
on reconnaît lafonction de répartitionde laloi de Rayleigh:
En effet, vu dans le cadre plus général des problèmes d'allocation, le calcul ci-dessus s'interprète comme la convergence d'une fonction de répartition vers une autre, traduisant laconvergence en loid'une suite devariables aléatoires. Pour exemple, on considèremboîtes numérotées de 1 àm,métant, pour l'instant,fixé. On suppose qu'on y alloue des boules, chacune étant placée dans une desmboîtes de manière équiprobable, indépendamment des allocations précédentes, et celaindéfiniment. Sim= 365, ceci est la situation du problème des anniversaires pour un groupe de personnesqui s'agrandit régulièrement. On noteTm{\displaystyle T_{m}}le rang de la première boule qui est allouée dans une boite contenant déjà une autre boule, ce qui correspondrait au rang de la première personne, arrivant dans le groupe, dont la date anniversaire est déjà celle d'un autre membre du groupe (avant son arrivée tous les membres du groupe ont des dates d'anniversaires différentes, après son arrivée ce n'est plus le cas).
Alors :
Et l'approximation ci-dessus peut donc s'écrire :
Cela traduit le fait que la suite de variables aléatoiresTm/m{\displaystyle T_{m}/{\sqrt {m}}}converge en loi vers la loi de Rayleigh, et, par là même, cela révèle un paradoxe, pour le sens commun : on s'attend probablement à ce queTm{\displaystyle T_{m}}soit du même ordre de grandeur quem, alors que cette convergence en loi révèle queTm{\displaystyle T_{m}}est du même ordre de grandeur quem.{\displaystyle {\sqrt {m}}.}Le phénomène de répétition des anniversaires a donc lieu plus tôt, pour un groupe plus petit qu'on ne s'y attendrait.
Dans le calcul précédent, une équipartition des jours de naissance dans l'année a été supposée implicitement. Si on ne la suppose plus, cela augmente les chances de réussir le pari que deux personnes soient nées le même jour, ce qui renforce encore le paradoxe.
Dans LeTrésor des Paradoxes(Éd Belin, 2007), les auteurs notent que l’informaticien américainRobert McEliecea é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 deRichard Hammingauxlaboratoires Bell.  La stratégie des codes détecteurs d’erreurs s’avère, du point de vuestatistique, similaire au paradoxe des anniversaires. Le paradoxe des anniversaires est utilisé encryptographiepour élaborer des attaques sur lesfonctions de hachage. Une des contraintes imposées sur ces fonctions, pour une utilisation cryptographique, est de produire peu decollisions, 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=12{\displaystyle 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 uniformément distribuée sur ses valeurs d'arrivée.
Plus concrètement, si une fonction de hachage a une sortie de Nbitsalors l'ensemble d'arrivée possède2N{\displaystyle 2^{N}}éléments et il faut environ2N2{\displaystyle 2^{\frac {N}{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 sur2N{\displaystyle 2^{N}}valeurs.
On suppose ici que Martine souhaite forcer Daniel à signer un contrat très défavorable, contrat devant être validé par son empreinte (valeurhachée), celle-ci garantissant que le contrat n'a pas pu être modifié après signature.
Elle prépare un contrat équitable et un contrat défavorable. Elle génère ensuite automatiquement des variantes de chacun des contrats avec des changements cosmétiques (ajouts d'espaces, utilisation de synonymes, réordonnancement des paragraphes, etc). Elle calcule l’empreinte de chaque contrat en recherchant des paires de mêmes empreintes (avec et sans modifications). Dès qu’une collision a été trouvée, elle donne le contrat équitable correspondant à Daniel qui le vérifie, le signe, calcule l'empreinte et l'attache au contrat.
Martine fait de même avec le contrat défavorable, et le présente à Daniel. S'il conteste les termes du contrat qu'il a signé, l'empreinte prouve qu'il est impossible qu'il ait pu être modifié. Il lui sera tout de même possible d'opposer le contrat original à Martine ce qui devrait conduire à lanullité du contrat.
Dans le domaine judiciaire, les probabilités d'identification fournies par la technique d'empreinte génétiquesont souvent mal comprises. Ainsi, si la probabilité que deux individus partagent neuflocusest environ d'une sur13 milliards, on peut s'attendre à ce que dans une base de données de 65 000 personnes, environ116 pairesd'individus aient en commun 9 des13 locusutilisés à des fins d'identification.