Paradoxe des anniversaires

Pour les articles homonymes, voir anniversaire (homonymie).

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (mai 2014).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article n’est pas rédigé dans un style encyclopédique (août 2024).

Vous pouvez améliorer sa rédaction !

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 23 personnes, 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 57 personnes, 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[1].

## Comprendre le problème

[modifier | modifier le code]

Par souci de simplicité, toutes les années sont supposées non bissextiles. On néglige donc la possibilité d'être né un 29 février, dont la prise en compte compliquerait les calculs pour une différence de résultat minime.

### Explication intuitive

[modifier | modifier le code]

Le problème des anniversaires revient à choisir un nombre n d'éléments dans un ensemble qui en contient N, 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 a a priori pas 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éunissant n personnes, de petits papiers sur lesquels sont notés les nombres de 1 à N sont 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, ou a contrario, pour qu'ils soient tous différents.

Pour calculer cette probabilité, il est plus simple de calculer celle où tous les nombres sont différents puis d'utiliser la formule  p ( 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 elle confond 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[2].

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 des sciences cognitives.

## Démonstration

[modifier | modifier le code]

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ù  n {\displaystyle n} personnes ( n ⩽ 365 {\displaystyle n\leqslant 365} ) 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  n {\displaystyle n} personnes et 365 jours possibles pour chacune, ce qui signifie que si aucune contrainte n'est fixée, il y a au total 365n possibilités. En ajoutant la contrainte d'avoir des jours différents, nous obtenons un arrangement de  n {\displaystyle n} parmi 365, soit :  A 365 n = ( 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

p ¯ ( n ) = 365 ! ( 365 − n ) ! ⋅ 1 365 n . {\displaystyle {\overline {p}}(n)={\frac {365!}{(365-n)!}}\cdot {\frac {1}{365^{n}}}.}

On peut aussi le voir comme une multiplication de probabilités d'évènements indépendants, conduisant au même résultat :

p ¯ ( n ) = 365 365 ⋅ 364 365 ⋅ 363 365 ⋅ ⋯ ⋅ 365 − n + 1 365 ⏟ n  facteurs = 365 ! ( 365 − n ) ! ⋅ 1 365 n . {\displaystyle {\overline {p}}(n)=\underbrace {{\frac {365}{365}}\cdot {\frac {364}{365}}\cdot {\frac {363}{365}}\cdot \cdots \cdot {\frac {365-n+1}{365}}} _{n\,{\text{ facteurs}}}={\frac {365!}{(365-n)!}}\cdot {\frac {1}{365^{n}}}.}

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  p ( n ) = 1 − p ¯ ( n ) {\textstyle p(n)=1-{\overline {p}}(n)} .

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[2].

n | p(n)

|

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 %
300 |  ( 1 − ( 6 ⋅ 10 − 82 ) ) ⋅ 100 % {\textstyle \left(1-\left(6\cdot 10^{-82}\right)\right)\cdot 100\%}
350 |  ( 1 − ( 3 ⋅ 10 − 131 ) ) ⋅ 100 % {\textstyle \left(1-\left(3\cdot 10^{-131}\right)\right)\cdot 100\%}
> 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

[modifier | modifier le code]

Une explication possible du « paradoxe » réside dans la confusion intuitive entre le problème des anniversaires et l'un des problèmes suivants[2].

### Premier problème

[modifier | modifier le code]

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 − ( 364 365 ) n − 1 . {\displaystyle q(n)={\displaystyle 1-\left({\frac {364}{365}}\right)^{n-1}}.}

Cela donne pour  n = 23 {\displaystyle n=23} une probabilité très faible de 5,86 %, et il faut réunir au moins 253 personnes pour que cette probabilité soit supérieure à 50 %[2].

Ce problème est parfois confondu avec le problème classique des anniversaires[3].

### Deuxième problème

[modifier | modifier le code]

Si les  n − 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 − 1 365 . {\displaystyle r(n)={\displaystyle {\frac {n-1}{365}}}.}

Il faut alors qu'il y ait au moins  183 = ⌈ 365 2 ⌉ {\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[2].

## Généralisation

[modifier | modifier le code]

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

Soit  E {\displaystyle E} un ensemble fini de cardinal N {\displaystyle N} . La probabilité  p ( n ) {\displaystyle p(n)} que, parmi  n {\displaystyle n} éléments de  E {\displaystyle E} (chaque élément étant tiré uniformément avec remise), deux éléments au moins soient identiques vaut :

p ( n ) = 1 − N ! ( N − n ) ! ⋅ 1 N n . {\displaystyle p(n)=1-{\frac {N!}{(N-n)!}}\cdot {\frac {1}{N^{n}}}.}

### Approximation de la probabilité

[modifier | modifier le code]

La probabilité  p ¯ ( n ) = 1 − p ( n ) {\displaystyle {\overline {p}}(n)=1-p(n)} peut se réécrire sous la forme :

p ¯ ( n ) = ∏ k = 0 n − 1 ( N − k ) / N . {\displaystyle {\overline {p}}(n)=\prod _{k=0}^{n-1}(N-k)/N.} D'où
p ¯ ( n ) = ( 1 − 1 N ) ( 1 − 2 N ) . . . ( 1 − n − 1 N ) . {\displaystyle {\overline {p}}(n)=\left(1-{\frac {1}{N}}\right)\left(1-{\frac {2}{N}}\right)...\left(1-{\frac {n-1}{N}}\right).}

Et d'après le développement limité e x = 1 + x + o ( x ) {\displaystyle {\rm {e}}^{x}=1+x+o(x)} pour  x {\displaystyle x} au voisinage de 0. Cela conduit à l'approximation :

p ¯ ( n ) ≈ ∏ k = 0 n − 1 e − k N . {\displaystyle {\overline {p}}(n)\approx \prod _{k=0}^{n-1}{\rm {e}}^{-{\frac {k}{N}}}.}
Posons  ϕ n = ∑ k = 0 n − 1 k N {\displaystyle \phi _{n}=\sum _{k=0}^{n-1}{\frac {k}{N}}} . On a donc  p ¯ ( n ) ≈ e − ϕ n . {\displaystyle {\overline {p}}(n)\approx {\rm {e}}^{-\phi _{n}}.}

Or, la somme des entiers de 0 à  n − 1 {\displaystyle n-1} vaut  n ( n − 1 ) / 2 {\displaystyle n(n-1)/2} , ce qui donne finalement :

p ¯ ( n ) ≈ e − n ( n − 1 ) 2 ⋅ N . {\displaystyle {\overline {p}}(n)\approx {\rm {e}}^{-{\frac {n(n-1)}{2\cdot N}}}.}

En revenant à  p ( n ) {\displaystyle p(n)}  :

p ( n ) ≈ 1 − e − n ( n − 1 ) 2 ⋅ N . {\displaystyle p(n)\approx 1-{\rm {e}}^{-{\frac {n(n-1)}{2\cdot N}}}.}

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

[modifier | modifier le code]

En résolvant en  n {\displaystyle n} l'égalité  p = 1 − e − n 2 2 ⋅ N {\displaystyle p=1-{\rm {e}}^{-{\frac {n^{2}}{2\cdot N}}}} on obtient une approximation  n ( p ) {\displaystyle n(p)} 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  p {\displaystyle p} . Ce nombre s'obtient :

n ( p ) = 2 N ⋅ ln ⁡ ( 1 1 − p ) . {\displaystyle n(p)={\sqrt {2N\cdot \ln \left({\frac {1}{1-p}}\right)}}.}

### Quelques valeurs numériques

[modifier | modifier le code]

Le tableau ci-dessous indique dans le cas originel ( N = 365 {\displaystyle N=365} ), pour une probabilité  p {\displaystyle p} , l'approximation  n ( 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 la 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 en couleur.

p {\displaystyle p} |  n ( p ) {\displaystyle n(p)} |  ⌊ n ⌋ {\displaystyle \lfloor n\rfloor } |  p ( ⌊ n ⌋ ) {\displaystyle p(\lfloor n\rfloor )} |  ⌈ n ⌉ {\displaystyle \lceil n\rceil } |  p ( ⌈ n ⌉ ) {\displaystyle 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

### Lien avec la loi de Rayleigh

[modifier | modifier le code]

Article détaillé : Loi de Rayleigh#Problème des anniversaires.

Dans l'expression :

p ( n ) ≈ 1 − e − n ( n − 1 ) 2 ⋅ 365 , {\displaystyle p(n)\approx 1-{\rm {e}}^{-{\frac {n(n-1)}{2\cdot 365}}},}

on reconnaît la fonction de répartition de la loi de Rayleigh :

F ( x ) = 1 − e − x 2 2 . {\displaystyle F(x)=1-{\rm {e}}^{-{\frac {x^{2}}{2}}}.}

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 . Pour exemple, on considère  m {\displaystyle m} boîtes numérotées de 1 à  m {\displaystyle m} (pour l'instant fixé). On suppose qu'on y alloue des boules, chacune étant placée dans une des  m {\displaystyle m} boîtes de manière équiprobable, indépendamment des allocations précédentes, et cela indéfiniment. Si  m = 365 {\displaystyle m=365} , ceci est la situation du problème des anniversaires pour un groupe de personnes qui s'agrandit régulièrement. On note  T m {\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 :

p ( n ) = P ( T 365 ⩽ n ) , {\displaystyle p(n)=\mathbb {P} (T_{365}\leqslant n),}

et l'approximation ci-dessus peut donc s'écrire :

P ( T 365 / 365 ⩽ x ) ≈ 1 − e − x 2 2 . {\displaystyle \mathbb {P} (T_{365}/{\sqrt {365}}\leqslant x)\approx 1-{\rm {e}}^{-{\frac {x^{2}}{2}}}.}

Cela traduit le fait que la suite de variables aléatoires  T m / 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 que  T m {\displaystyle T_{m}} soit du même ordre de grandeur que  m {\displaystyle m} , alors que cette convergence en loi révèle que  T m {\displaystyle T_{m}} est du même ordre de grandeur que  m . {\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.

## Cas non uniforme

[modifier | modifier le code]

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[4], ce qui renforce encore le paradoxe.

Démonstration de ce fait

Comme la démonstration se fait par récurrence sur le nombre de jours dans l'année, nous notons  n {\displaystyle n} ce nombre, et  k ⩽ n {\displaystyle k\leqslant n} le nombre de personnes ; soit  X j {\displaystyle X_{j}} la variable aléatoire donnant la date anniversaire de la personne n°  j {\displaystyle j} . De façon naturelle, les variables  X j {\displaystyle X_{j}} sont supposées indépendantes de même loi :  P ( X j = i ) = x i {\displaystyle P\left(X_{j}=i\right)=x_{i}} , indépendant de  j {\displaystyle j} .

L'évènement cherché (« les personnes sont nées des jours différents ») est la réunion des évènements disjoints  { ( X 1 , . . . , X k ) = ( i 1 , . . , i k ) } , ( i 1 , . . , i k ) {\displaystyle \\{(X_{1},...,X_{k})=(i_{1},..,i_{k})\\},(i_{1},..,i_{k})} étant un arrangement de  [ [ 1 , n ] ] {\displaystyle [\\!\left[1,n\right]\\!]} .

La probabilité recherchée est donc

p k ( x 1 , . . , x n ) = ∑ ( i 1 , . . , i k )   arrangement de  [ [ 1 , n ] ] x i 1 ⋅ x i 2 ⋅ . . . ⋅ x i k = k ! ∑ 1 ⩽ i 1 < . . < i k ⩽ n x i 1 ⋅ x i 2 . . . ⋅ x i k {\displaystyle p_{k}(x_{1},..,x_{n})=\sum _{(i_{1},..,i_{k})~{\text{arrangement de }}[\\!\left[1,n\right]\\!]}x_{i_{1}}\cdot x_{i_{2}}\cdot ...\cdot x_{i_{k}}=k!{\underset {1\leqslant i_{1}<..<i_{k}\leqslant n}{\sum }}x_{i_{1}}\cdot x_{i_{2}}...\cdot x_{i_{k}}} .

Comme annoncé, nous allons démontrer que pour tout  k {\displaystyle k} entre 2 et  n {\displaystyle n} ,

p k ( x 1 , . . , x n ) ⩽ p k ( 1 / n , . . . , 1 / n )  si  ∑ i = 1 n x i = 1 , x i ⩾ 0 {\displaystyle p_{k}(x_{1},..,x_{n})\leqslant p_{k}(1/n,...,1/n){\text{ si }}\sum _{i=1}^{n}x_{i}=1,x_{i}\geqslant 0} .

Posant  φ k ( x 1 , . . , x n ) = ∑ 1 ⩽ i 1 < . . < i k ⩽ n x i 1 . x i 2 . . . . x i k {\displaystyle \varphi _{k}(x_{1},..,x_{n})=\sum _{1\leqslant i_{1}<..<i_{k}\leqslant n}x_{i_{1}}.x_{i_{2}}....x_{i_{k}}} , nous allons même plus généralement démontrer par récurrence sur  n {\displaystyle n} que pour tout  k {\displaystyle k} entre 2 et  n {\displaystyle n}  :

φ k ( x 1 , . . , x n ) ⩽ φ k ( s / n , . . . , s / n )  si  ∑ i = 1 n x k = s , x i ⩾ 0 {\displaystyle \varphi _{k}(x_{1},..,x_{n})\leqslant \varphi _{k}(s/n,...,s/n){\text{ si }}\sum _{i=1}^{n}x_{k}=s,x_{i}\geqslant 0} .

Pour  n = 2 {\displaystyle n=2} , la seule possibilité pour  k {\displaystyle k} est  k = 2 {\displaystyle k=2} , et l'inégalité  φ 2 ( x 1 , x 2 ) = x 1 x 2 ⩽ ( x 1 + x 2 2 ) 2 {\displaystyle \varphi _{2}\left(x_{1},x_{2}\right)=x_{1}x_{2}\leqslant \left({\dfrac {x_{1}+x_{2}}{2}}\right)^{2}} est facile.

Supposons la propriété vraie à l'ordre  n {\displaystyle n} et montrons-la à l'ordre  n + 1 {\displaystyle n+1} .

Posons  ∑ k = 1 n + 1 x k = s {\displaystyle \sum _{k=1}^{n+1}x_{k}=s} et  x n + 1 = x {\displaystyle x_{n+1}=x} .

Remarquons que  φ k ( x 1 , . . . , x n , x ) = x φ k − 1 ( x 1 , . . , x n ) + φ k ( x 1 , . . , x n ) {\displaystyle \varphi _{k}\left(x_{1},...,x_{n},x\right)=x\varphi _{k-1}(x_{1},..,x_{n})+\varphi _{k}(x_{1},..,x_{n})} .

Par hypothèse de récurrence,

φ k − 1 ( x 1 , . . , x n ) ⩽ φ k − 1 ( s − x n , . . . , s − x n ) = ( n k − 1 ) ( s − x n ) k − 1 {\displaystyle \varphi _{k-1}(x_{1},..,x_{n})\leqslant \varphi _{k-1}\left({\dfrac {s-x}{n}},...,{\dfrac {s-x}{n}}\right)={\binom {n}{k-1}}\left({\dfrac {s-x}{n}}\right)^{k-1}} et  φ k ( x 1 , . . , x n ) ⩽ φ k ( s − x n , . . . , s − x n ) = ( n k ) ( s − x n ) k {\displaystyle \varphi _{k}(x_{1},..,x_{n})\leqslant \varphi _{k}\left({\dfrac {s-x}{n}},...,{\dfrac {s-x}{n}}\right)={\binom {n}{k}}\left({\dfrac {s-x}{n}}\right)^{k}} .

On obtient donc  φ k ( x 1 , . . . , x n , x ) ⩽ x ( n k − 1 ) ( s − x n ) k − 1 + ( n k ) ( s − x n ) k {\displaystyle \varphi _{k}\left(x_{1},...,x_{n},x\right)\leqslant x{\binom {n}{k-1}}\left({\dfrac {s-x}{n}}\right)^{k-1}+{\binom {n}{k}}\left({\dfrac {s-x}{n}}\right)^{k}} .

Soit

φ k ( x 1 , . . . , x n , x ) ⩽ 1 k n k ( n k − 1 ) [ k n x ( s − x ) k − 1 + ( n − k + 1 ) ( s − x ) k ] {\displaystyle \varphi _{k}\left(x_{1},...,x_{n},x\right)\leqslant {\dfrac {1}{kn^{k}}}{\binom {n}{k-1}}\left[knx\left(s-x\right)^{k-1}+\left(n-k+1\right)\left(s-x\right)^{k}\right]} .

Posant  y = s − x {\displaystyle y=s-x} , la dernière parenthèse vaut

f ( y ) = k n ( s − y ) y k − 1 + ( n − k + 1 ) y k = k n s y k − 1 − ( n + 1 ) ( k − 1 ) y k {\displaystyle f\left(y\right)=kn\left(s-y\right)y^{k-1}+\left(n-k+1\right)y^{k}=knsy^{k-1}-\left(n+1\right)\left(k-1\right)y^{k}} .

La dérivée  f ′ ( y ) = k ( k − 1 ) y k − 2 ( n s − ( n + 1 ) y ) {\displaystyle f'(y)=k(k-1)y^{k-2}(ns-(n+1)y)} montre que  f {\displaystyle f} est maximale pour  y = n n + 1 s {\displaystyle y={\dfrac {n}{n+1}}s} , soit  x = s n + 1 {\displaystyle x={\dfrac {s}{n+1}}} .

Donc  φ k ( x 1 , . . . , x n , x ) ⩽ s n + 1 ( n k − 1 ) ( s n + 1 ) k − 1 + ( n k ) ( s n + 1 ) k = ( n + 1 k ) ( s n + 1 ) k {\displaystyle \varphi _{k}\left(x_{1},...,x_{n},x\right)\leqslant {\dfrac {s}{n+1}}{\binom {n}{k-1}}\left({\dfrac {s}{n+1}}\right)^{k-1}+{\binom {n}{k}}\left({\dfrac {s}{n+1}}\right)^{k}={\binom {n+1}{k}}\left({\dfrac {s}{n+1}}\right)^{k}} = φ k ( s n + 1 , . . . , s n + 1 ) {\displaystyle =\varphi _{k}\left({\dfrac {s}{n+1}},...,{\dfrac {s}{n+1}}\right)} , ce qui achève la récurrence.

Remarquons que cela revient à démontrer que l'espérance du produit de  k {\displaystyle k} nombres distincts pris parmi  n {\displaystyle n} nombres positifs de somme donnée est maximale quand ces  n {\displaystyle n} nombres sont égaux.

Géométriquement : parmi tous les hyperparallélépipèdes rectangles (ou orthotopes) de dimension  n {\displaystyle n} de somme des longueurs des arêtes donnée, celui qui a la plus grande moyenne des hypervolumes des  k {\displaystyle k} -cellules est l'hypercube. Pour  n = 3 , k = 2 {\displaystyle n=3,k=2} 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

[modifier | modifier le code]

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é  p = 1 2 {\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 N bits alors l'ensemble d'arrivée possède  2 N {\displaystyle 2^{N}} éléments et il faut environ  2 N 2 {\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 sur  2 N {\displaystyle 2^{N}} valeurs.

### Application pratique du paradoxe des anniversaires

[modifier | modifier le code]

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.

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é[5]. 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

[modifier | modifier le code]

Dans le domaine judiciaire, les probabilités d'identification fournies par la technique d'empreinte génétique sont souvent mal comprises[6]. 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[6].

## Notes et références

[modifier | modifier le code]

1. ↑ (de) Richard von Mises, « Über Aufteilungs- und Besetzungswahrscheinlichkeiten », Revue de la faculté des sciences de l'université d'Istanbul, vol. 4,‎ 1939, p. 145-163.
2. ↑ a b c d et e Jean-Paul Delahaye, « Notre vision du hasard est bien hasardeuse... », Pour la science, no 293,‎ mars 2002 (lire en ligne [PDF]).
3. ↑ Gérard Lavau, « Les aléas de l'aléatoire », PLOT, no 40,‎ octobre 1987, p. 43-44 (lire en ligne [PDF]).
4. ↑ (en) William Knight et D. M. Bloom, « E2386 », The American Mathematical Monthly, vol. 80, no 10,‎ décembre 1973, p. 1141 (DOI 10.2307/2318556).
5. ↑ « Attaque « des anniversaires » », sur hds.utc.fr.
6. ↑ a et b 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 »).

## Annexes

[modifier | modifier le code]

Sur les autres projets Wikimedia :

* Paradoxe des anniversaires, sur Wikimedia Commons

### Bibliographie

[modifier | modifier le code]

* [Ross 2014] (en) Sheldon Ross, A First Course in Probability, Pearson, 2014, 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 »], 1982, 226 p. (ISBN 0-8129-2117-8).

### Articles connexes

[modifier | modifier le code]

* Attaque des anniversaires
* Date de naissance

### Liens externes

[modifier | modifier le code]

*   *   * Notice dans un dictionnaire ou une encyclopédie généraliste :
* Britannica

v · m

Mesures de sécurité cryptographique

Cryptographie |

* Preuve de sécurité
* Sécurité inconditionnelle
* Niveaux d'attaques
* IND-CPA
* Principe de Kerckhoffs
* Malléabilité
* Sécurité calculatoire
* Confusion et diffusion

Cryptanalyse de base |

* Biais statistique
* Corrélation
* Dictionnaire
* Force brute
* Fréquence
* Indice de coïncidence
* Interpolation
* Mot probable
* Paramètre de sécurité

Cryptanalyse par canal auxiliaire |

* Acoustique
* Consommation
* Émanations EM
* Faute
* Sondage
* Temporel

Cryptanalyse ciblée |

* Clé apparentée
* Clé faible
* EFF
* Enigma
* Glissement
* Intégrale
* Linéaire / Différentielle / Différentielle impossible / Différentielle-linéaire / Boomerang
* Modes opératoires
* Modulo n
* Quadratique
* Rectangle
* Rencontre au milieu
* Vigenère
* χ²

Systèmes asymétriques |

* Clé apparentée
* Clé faible
* Homme au milieu
* Sécurité sémantique

Fonctions de hachage |

* Effet avalanche
* Linéaire / Différentielle
* Paradoxe des anniversaires
* Pseudo-collision

Autres |

* Anonymat
* Confidentialité
* Intégrité
* Sécurité par l'obscurité

* Portail des probabilités et de la statistique

*[(de)]: Langue : allemand
*[vol.]: volume
*[p.]: pages
*[no]: numéro
*[[PDF]]: Document au format Portable Document Format (PDF) d'Adobe
*[(en)]: Langue : anglais
*[trad.]: traduction
*[coll.]: collection
*[chap.]: chapitre(s)
*[v]: Voir ce modèle.
*[m]: Modifier ce modèle. Merci de prévisualiser avant de sauvegarder.