En théorie des probabilités, le paradoxe des anniversaires est un résultat mathématique contre-intuitif concernant la probabilité que deux personnes, dans un groupe, aient la même date d'anniversaire.
Il y est montré que dans un groupe de , il y a plus d'une chance sur deux qu'au moins deux personnes partagent la même date d'anniversaire. À partir d'un groupe de , la probabilité dépasse 99 %.
Il ne s'agit pas d'un paradoxe au sens logique, mais plutôt d'un résultat qui défie l'intuition.
L'étude détaillée de cette situation est due à Richard von Mises..
Comprendre le problème Par souci de simplicité, toutes les années sont supposées non bissextiles. On néglige donc la possibilité d'être né un , dont la prise en compte compliquerait les calculs pour une différence de résultat minime.
Explication intuitive Le problème des anniversaires se modélise à l'aide de l'expérience aléatoire suivante. Dans un ensemble de taille , on tire uniformément éléments, sans retirer les éléments déjà choisis : certains peuvent alors être identiques. Dans le cas du paradoxe des anniversaires, la date d'anniversaire de chacune des personnes est considérée comme tirée au hasard uniformément parmi les jours de l'année. On s'intéresse alors à la probabilité que deux personnes aient la même date d'anniversaire. Pour calculer cette probabilité, il est plus simple de calculer celle de la situation inverse , où toutes les dates sont différentes, puis d'utiliser la formule afin d'en déduire le résultat.
L'aspect contre-intuitif du paradoxe des anniversaires réside dans la confusion entre les deux évènements suivants : et
Ce deuxième évènement, inclus dans le premier, a une probabilité beaucoup plus faible d'arriver. C'est pourtant la probabilité du premier évènement que l'on cherche à estimer. 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 la même date d'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 relève du domaine des sciences cognitives.
Démonstration
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 pas disjoints et que trois personnes peuvent partager la même date de naissance.
Cette démonstration procède par dénombrement, c'est-à-dire en comptant le nombre de cas où personnes () ont des jours d'anniversaires différents puis en divisant par le nombre de possibilités et l'on fait une hypothèse d'équiprobabilité des jours de naissance.
Il y a personnes et 365 jours possibles pour chacune, ce qui signifie que si aucune contrainte n'est fixée, il y a au total possibilités. En ajoutant la contrainte d'avoir des jours différents, nous obtenons un arrangement de parmi 365, soit : On a donc
On peut aussi le voir comme une multiplication de probabilités d'évènements indépendants, conduisant au même résultat :
Or, l’évènement « chaque personne a un jour d'anniversaire différent » est le complémentaire de « au moins deux personnes ont un jour d'anniversaire identique ». En conséquence, la probabilité recherchée est .
vignette|redresse=1.5|Courbes des probabilités de coïncidence et de non-coïncidence de deux anniversaires en fonction du nombre de personnes. En appliquant ce calcul au cas d'une assemblée de vingt-trois personnes, on trouve une probabilité de 50,73 % pour que deux personnes aient la même date d'anniversaire.
np(n) : probabilité qu'au moins deux personnes parmi n aient un jour d'anniversaire identique 5 2,71 %10 11,69 %15 25,29 %20 41,14 %23 50,73 %25 56,87 %30 70,63 %40 89,12 %50 97,04 %60 99,41 %80 99,99 %100 99,99997 %200 99,9999999999999999999999999998 %300350 > 366 100 % (par le principe des tiroirs) si on prend en compte la possibilité d'être né le 29 février.
Problèmes apparentés pouvant expliquer le paradoxe Une explication possible du « paradoxe » réside dans la confusion intuitive entre le problème des anniversaires et l'un des problèmes suivants.
Premier problème 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 à :
Cela donne pour une probabilité très faible de 5,86 %, et il faut réunir au moins pour que cette probabilité soit supérieure à 50 %.
Ce problème est parfois confondu avec le problème classique des anniversaires..
Deuxième problème Si les autres personnes du groupe ont toutes des dates d'anniversaires différentes, la probabilité qu'au moins une d'entre elles ait la même date qu'un individu donné vaut :
Il faut alors qu'il y ait au moins autres personnes pour que cette probabilité soit supérieure à 50 %, ce qui est parfois la réponse donnée au problème initial.
Généralisation Ce paradoxe des anniversaires se généralise à la situation plus abstraite que l'on peut énoncer sous la forme suivante.
Soit un ensemble fini de cardinal . La probabilité que, parmi éléments de (chaque élément étant tiré uniformément avec remise), deux éléments au moins soient identiques vaut :
Approximation de la probabilité
La probabilité peut se réécrire sous la forme :
D'où
Et d'après le développement limité pour au voisinage de 0, cela conduit à l'approximation :
Posons . On a donc Or, la somme des entiers de 0 à vaut , ce qui donne finalement :
En revenant à :
Estimation du nombre de tirages pour une probabilité donnée En résolvant en l'égalité on obtient une approximation du nombre de personnes nécessaire pour qu'avoir au moins deux personnes avec le même jour d'anniversaire au sein d'un groupe aie une probabilité donnée . Ce nombre s'obtient :
Quelques valeurs numériques Le tableau ci-dessous indique dans le cas originel (), pour une probabilité , l'approximation indiquée ci-dessus, puis, sur la même ligne, l'approximation de la probabilité pour l'entier inférieur ou égal à (noté ) et celle de la probabilité pour l'entier supérieur ou égal à (noté ). Normalement, la probabilité 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.
2 3 6 7 8 9 12 13 16 17 22 23 29 30 34 35 40 41 46 47 57 58
Lien avec la loi de Rayleigh
Dans l'expression :
on reconnaît la fonction de répartition de la loi 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 la convergence en loi d'une suite de variables aléatoires . Par exemple, on considère boîtes numérotées de 1 à (pour l'instant fixé). On suppose qu'on y alloue des boules, chacune étant placée dans une des boîtes de manière équiprobable, indépendamment des allocations précédentes, et cela indéfiniment. Si , ceci est la situation du problème des anniversaires pour un groupe de personnes qui s'agrandit régulièrement. On note le rang de la première boule qui est allouée dans une boîte 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éatoires 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 que soit du même ordre de grandeur que , alors que cette convergence en loi révèle que est du même ordre de grandeur que 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.
Cas non uniforme 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.
Comme la démonstration se fait par récurrence sur le nombre de jours dans l'année, nous notons ce nombre, et le nombre de personnes ; soit la variable aléatoire donnant la date anniversaire de la personne n° . De façon naturelle, les variables sont supposées indépendantes de même loi : , indépendant de .
L'évènement cherché (« les personnes sont nées des jours différents ») est la réunion des évènements disjoints étant un arrangement de .
La probabilité recherchée est donc .
Comme annoncé, nous allons démontrer que pour tout entre 2 et , .
Posant , nous allons même plus généralement démontrer par récurrence sur que pour tout entre 2 et : .
Pour , la seule possibilité pour est , et l'inégalité est facile.
Supposons la propriété vraie à l'ordre et montrons-la à l'ordre .
Posons et .
Remarquons que .
Par hypothèse de récurrence, et .
On obtient donc .
Soit .
Posant , la dernière parenthèse vaut .
La dérivée montre que est maximale pour , soit .
Donc , ce qui achève la récurrence.
Remarquons que cela revient à démontrer que l'espérance du produit de nombres distincts pris parmi nombres positifs de somme donnée est maximale quand ces nombres sont égaux.
Géométriquement : parmi tous les hyperparallélépipèdes rectangles (ou orthotopes) de dimension de somme des longueurs des arêtes donnée, celui qui a la plus grande moyenne des hypervolumes des -cellules est l'hypercube. Pour ou 3 : parmi tous les parallélépipèdes rectangles de somme des longueurs des arêtes données, celui qui a la plus grande aire (ou volume) est le cube.
Applications Dans Le Trésor des Paradoxes (Éd Belin, 2007), les auteurs notent que l’informaticien américain Robert McEliece 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. L'attaque des anniversaires est utilisée en cryptographie pour viser 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é , à 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 N bits alors l'ensemble d'arrivée possède éléments et il faut environ 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 valeurs.
Application pratique du paradoxe des anniversaires On suppose ici que Martine souhaite forcer Daniel à signer un contrat très défavorable, contrat devant être validé par son empreinte (valeur hachée), celle-ci garantissant que le contrat n'a pas pu être modifié après signature.