Le paradoxe des anniversaires, encadré

La stratégie. Passer au complémentaire — « les $k$ anniversaires sont deux à deux distincts », qui se compte comme un nombre de listes sans répétition —, puis encadrer le produit obtenu, pour décider sans machine à partir de quelle taille la coïncidence devient plus probable que son absence.

a) Le complémentaire. Notons $X_1,\dots ,X_k$ les jours d'anniversaire. Par indépendance, pour toute liste $(x_1,\dots ,x_k)$ de jours, $$P(X_1=x_1,\dots ,X_k=x_k)=\prod _{i=1}^{k}P(X_i=x_i)=\frac{1}{N^k}:$$ le $k$-uplet suit la loi uniforme sur $\{1,\dots ,N{\}}^k$. L'événement « les $X_i$ sont deux à deux distincts » est réalisé par les listes de $k$ éléments distincts, au nombre de $N(N-1)\cdots (N-k+1)$ : $N$ choix pour le premier terme, $N-1$ pour le deuxième, et ainsi de suite. Donc $$1-p_k=\frac{N(N-1)\cdots (N-k+1)}{N^k}=\prod _{i=0}^{k-1}\frac{N-i}{N}=\prod _{i=1}^{k-1}(1-\frac{i}{N}),$$ le facteur d'indice $0$ valant $1$. Le numérateur compte exactement $k$ facteurs, le dernier étant $N-k+1$ : c'est là qu'on se trompe d'une unité.

b) Les deux inégalités.

Majoration. Le chapitre de calcul différentiel et intégral établit $e^x\ge 1+x$ pour tout réel $x$. Avec $x=-a_i$ : $0\le 1-a_i\le e^{-a_i}$, la positivité venant de $a_i\le 1$. On peut multiplier membre à membre des inégalités entre réels positifs : $\prod (1-a_i)\le \prod e^{-a_i}=\exp (-\sum a_i)$.

Minoration, par récurrence sur $m$. Pour $m=1$, c'est une égalité. Supposons ${\prod }_{i=1}^m(1-a_i)\ge 1-{\sum }_{i=1}^m{a}_i$, et multiplions par $1-a_{m+1}\ge 0$, ce qui conserve le sens : $$\prod _{i=1}^{m+1}(1-a_i)\ge (1-\sum _{i=1}^m{a}_i)(1-a_{m+1})=1-\sum _{i=1}^{m+1}{a}_i+a_{m+1}\sum _{i=1}^m{a}_i.$$ Le dernier terme est positif : on peut l'oublier, et l'hérédité est acquise.

c) L'encadrement de $p_k$. Appliquons le b) avec $m=k-1$ et $a_i=\frac{i}{N}$, qui sont dans $[0,1]$ puisque $i\le k-1<N$. La somme vaut ${\sum }_{i=1}^{k-1}\frac{i}{N}=\frac{k(k-1)}{2N}$, donc $1-\frac{k(k-1)}{2N}\le 1-p_k\le e^{-k(k-1)/(2N)}$, c'est-à-dire $$1-e^{-k(k-1)/(2N)}\le p_k\le \frac{k(k-1)}{2N}.$$

Pour $k\ge 23$. La minoration dépasse $\frac{1}{2}$ dès que $e^{-k(k-1)/(2N)}<\frac{1}{2}$, c'est-à-dire dès que $k(k-1)>2N\ln 2=730\ln 2=505,997\dots$ Pour $k=23$, $k(k-1)=506$, et $k(k-1)$ croît avec $k$ : pour tout $k\ge 23$, $$p_k\ge 1-e^{-506/730}\approx 0,500002>\frac{1}{2}.$$

Pour $k\le 19$. La majoration donne $p_{19}\le \frac{19\times 18}{730}=\frac{342}{730}\approx 0,468<\frac{1}{2}$, et $\frac{k(k-1)}{2N}$ croît avec $k$ : $p_k<\frac{1}{2}$ pour tout $k\le 19$.

Le point délicat. La minoration décide $k=23$ avec une marge infime, $506$ contre $505,997$ : il faut $\ln 2$ à six décimales, $0,693147$, à comparer à $\frac{506}{730}=0,693151$. Les valeurs exactes sont $p_{22}\approx 0,4757$ et $p_{23}\approx 0,5073$ ; pour $k=20$, $21$, $22$, l'encadrement ne décide pas — il est fait pour l'ordre de grandeur.

d) L'échelle de la racine. L'encadrement dit que $p_k$ est petit tant que $k(k-1)$ est petit devant $2N$, et proche de $1$ dès qu'il est grand devant $2N$ : la bascule a lieu vers $k\approx \sqrt{2N\ln 2}\approx 1,18\sqrt{N}$. Une coïncidence devient probable pour $k$ de l'ordre de $\sqrt{N}$, pas de $N$, parce que ce sont les paires qui comptent : il y en a $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ (« deux parmi $k$ »), chacune coïncide avec probabilité $\frac{1}{N}$, et la majoration $\frac{k(k-1)}{2N}$ est leur nombre moyen de coïncidences.

Ce que l'exercice installe. Le passage au complémentaire pour toute question en « au moins », et l'encadrement d'un produit par une exponentielle, $1-\sum a_i\le \prod (1-a_i)\le e^{-\sum a_i}$, qui transforme un produit intraitable en une somme — le geste du TD 15, celui du dénombrement, pour les molécules réparties entre deux compartiments. Et un ordre de grandeur : les collisions arrivent à l'échelle $\sqrt{N}$ ; des étiquettes tirées au hasard parmi $2^{64}$ se répètent dès quelques milliards d'objets, puisque $\sqrt{2^{64}}=2^{32}$.