AccueilđŸ‡«đŸ‡·Chercher

Paradoxe des anniversaires

Le paradoxe des anniversaires rĂ©sulte de l'estimation probabiliste du nombre de personnes que l'on doit rĂ©unir pour avoir au moins une chance sur deux que deux personnes de ce groupe aient leur anniversaire le mĂȘme jour. Il se trouve que ce nombre est 23[1], ce qui choque un peu l'intuition. À partir d'un groupe de 57 personnes, la probabilitĂ© est supĂ©rieure Ă  99 %.

Il s'agit d'un paradoxe non pas dans le sens de contradiction logique, mais 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 %.

Cette Ă©tude est due Ă  Richard von Mises.

Comprendre le problĂšme

Par souci de simplicité, l'article est rédigé en supposant que toutes les années sont non bissextiles. Prendre en compte le changerait peu les résultats, mais rendrait les calculs trÚs délicats.

Signification intuitive

Le problĂšme des anniversaires revient Ă  choisir un nombre n d'Ă©lĂ©ments dans un ensemble qui en comprend N, sans retrait ; c'est-Ă -dire sans retirer les Ă©lĂ©ments choisis, si bien que certains peuvent ĂȘtre identiques. Le paradoxe des anniversaires est bien un cas de ce type, car chacun a une date d'anniversaire plus ou moins alĂ©atoire, et il n'y a pas a priori de raison autre que la probabilitĂ© pour que deux dates soient identiques ou diffĂ©rentes.

Imaginez par exemple qu'au cours d'une soirée réunissant n personnes, des petits papiers, sur lesquels sont notés les nombres de 1 à N, soient placés dans une corbeille. Chacun à son tour tire un papier, lit le nombre qu'il porte, puis le replace dans la corbeille. Quelles sont les chances pour que 2 nombres tirés au moins soient identiques ? ou au contraire pour que tous soient différents ?

Pour calculer la probabilité numérique, il est plus simple de compter les chances que tous les nombres soient différents. Le point-clé non évident qui induit notre intuition en erreur, concerne au contraire les chances que 2 nombres au moins soient identiques. Au bout du compte, les deux approches sont bien sûr équivalentes.

Si l'on considĂšre un nombre tirĂ© donnĂ©, quelles sont ses chances d'ĂȘtre identique Ă  un autre ? Il peut ĂȘtre Ă©gal Ă  n'importe quel autre ; en revanche, le nombre total de possibilitĂ©s restreint ses chances : on a donc intuitivement une chance proportionnelle Ă  n/N. Mais cette chance-lĂ  s'applique Ă  tous les nombres tirĂ©s, si bien qu'Ă  la fin, la chance qu'un nombre tirĂ© quelconque soit identique Ă  n'importe quel autre nombre tirĂ© est dans une proportion d'environ n2/N. C'est lĂ  que notre intuition est trompĂ©e, et on prĂ©dit une probabilitĂ© de 50 % pour n proche de N/2 alors que √N est une meilleure approximation.

Cela revient Ă  dire que l’on confond la question posĂ©e : les chances de n’importe quel Ă©lĂ©ment choisi d’ĂȘtre identique Ă  n’importe quel autre, avec une autre question proche : les chances de n’importe quel Ă©lĂ©ment choisi d’ĂȘtre identique Ă  un autre Ă©lĂ©ment donnĂ©. Dans le cas des anniversaires, on tend Ă  Ă©valuer intuitivement la probabilitĂ© pour que la date d’anniversaire de quiconque soit la mĂȘme qu’une date d’anniversaire donnĂ©e (par exemple, la mienne) ; au lieu de la probabilitĂ© pour que la date d’anniversaire de quiconque soit la mĂȘme que celle de n’importe qui d’autre.

Reste Ă  savoir pourquoi notre intuition est ainsi trompĂ©e, c’est-Ă -dire pourquoi elle ne semble pas spontanĂ©ment capable d’aborder correctement un problĂšme de ce type. C’est une question pour les sciences cognitives.

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Ă©e. 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 bien partager la mĂȘme date de naissance : ces Ă©vĂšnements ne sont pas disjoints. 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 : le contraire de ce que l’on cherche.

On peut procĂ©der par rĂ©currence : la premiĂšre personne a donc 365 choix, la deuxiĂšme 364, la troisiĂšme 363, la quatriĂšme 362, et ainsi de suite. On va ici 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. Dans les deux cas nous faisons une hypothĂšse d'Ă©quiprobabilitĂ© des jours de naissance.

Il y a personnes, pour chacune il y a 365 jours possibles, donc au total si on ne se fixe aucune contrainte, il y a 365n possibilités. Si maintenant on veut des jours différents, nous obtenons un arrangement de parmi 365, soit : .

On a donc

On peut également le voir comme une multiplication de probabilités d'évÚnements indépendants :

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 .

En faisant l'application numérique, on trouve 50,73 % de chances pour deux dates anniversaires identiques dans une assemblée de vingt-trois personnes.

Probabilité de coïncidence de 2 anniversaires en fonction du nombre de personnes.
np(n)
52,71 %
1011,69 %
1525,29 %
2041,14 %
2350,73 %
2556,87 %
3070,63 %
4089,12 %
5097,04 %
6099,41 %
8099,99 %
10099,99997 %
20099,9999999999999999999999999998 %
300
350
> 366100 % (par le principe des tiroirs) si on prend en compte la possibilitĂ© d'ĂȘtre nĂ© le 29 fĂ©vrier.
Probabilité de non-coïncidence de 2 anniversaires en fonction du nombre de personnes.

Généralisation

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

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

Approximation de la probabilité

La probabilité peut se réécrire sous la forme :

, d'oĂč

Or, on a le développement limité pour x voisin de 0. Cela conduit à l'approximation :

Or, la somme des entiers de 0 Ă  vaut , ce qui donne finalement :

En revenant Ă  :

Estimation du nombre de tirages pour une probabilité donnée

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

Quelques valeurs numériques

Le tableau ci-dessous indique dans le cas originel (), pour une probabilitĂ© , l'approximation , puis, sur la mĂȘme ligne, l'approximation de la probabilitĂ© pour l'entier infĂ©rieur ou Ă©gal Ă  (notĂ© ) et celle de 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.

0,01
2,70864
20,002743
0,00820
0,056,119166 0,0404670,05624
0,1
8,77002
80,074349
0,09462
0,2
12,76302
120,1670213
0,19441
0,316,1360716 0,28360170,31501
0,522,4943922 0,47570230,50730
0,729,6462529 0,68097300,70632
0,834,2766634 0,79532350,81438
0,940,9986240 0,89123410,90315
0,9546,7641446 0,94825470,95477
0,99
57,98081
57
0,99012
580,99166

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 : considérons m boßtes numérotées de 1 à m, m étant, pour l'instant, fixé. Supposons qu'on y alloue des boules, chaque boule étant placée dans une des m boßtes de maniÚre équiprobable, indépendamment des allocations précédentes, et cela indéfiniment. Si m=365, 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 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Ă©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 m, 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, l'Ă©quirĂ©partition des jours de naissance dans l'annĂ©e a Ă©tĂ© supposĂ©e implicitement. Que se passe-t-il si on ne la suppose plus ? La rĂ©ponse est que 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.

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é , à 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 de l'attaque des anniversaires

Supposons que Martine souhaite forcer Daniel Ă  signer un contrat trĂšs dĂ©favorable, contrat devant ĂȘtre validĂ© par son empreinte (valeur hashĂ©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Ă©[2]. Il lui sera tout de mĂȘme possible d'opposer le contrat original Ă  Martine ce qui devrait conduire Ă  la nullitĂ© du contrat.

Lien avec l'identification par l'ADN

Dans le domaine judiciaire, les probabilitĂ©s d'identification fournies par la technique d'empreinte gĂ©nĂ©tique sont souvent mal comprises[3]. Ainsi, si la probabilitĂ© que deux individus partagent neuf locus est environ d'une sur 13 milliards on peut s'attendre Ă  ce que dans une base de donnĂ©es de 65 000 personnes, environ 116 paires d'individus aient en commun 9 des 13 locus utilisĂ©s Ă  des fins d'identification[3].

Anecdote

Dans Le Livre qui rend fou[4], Raymond Smullyan raconte qu'il 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.

Notes et références

  1. Ross 2014, p. 37.
  2. « Attaque « des anniversaires » »
  3. Leila Schneps et Coralie Colmez (trad. de l'anglais par Coralie Colmez), Les maths au tribunal : les erreurs de calcul font les erreurs judiciaires [« Math on Trial. How Numbers Get Used and Abused in the Courtroom »], Paris, Seuil, coll. « Science ouverte », 280 p. (ISBN 978-2-02-110439-4), chap. 5 (« L'affaire Diana Sylvester : analyse d'un cold hit »).
  4. Smullyan 1982, p. 6.

Annexes

Bibliographie

  • [Ross 2014] (en) Sheldon Ross, A First Course in Probability, Pearson, , 467 p. (ISBN 978-0-321-79477-2 et 032179477X), chap. 2.
  • [Smullyan 1982] (en) Raymond Smullyan, The Lady or the Tiger? [« Le Livre qui rend fou »], , 226 p. (ISBN 0-8129-2117-8).

Articles connexes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.