Les chapeaux rendus au hasard : espérance, variance, concentration

La stratégie. La loi de $N$ est compliquée, et on ne la calculera pas. On écrit $N$ comme une somme d'indicatrices ; la linéarité de l'espérance donne $E(N)$ sans aucune hypothèse d'indépendance ; le développement du carré ramène $E(N^2)$ à des probabilités d'intersections de deux événements ; et l'inégalité de Bienaymé-Tchebychev conclut.

a) L'espérance. Pour chaque $i$, notons $A_i=(\sigma (i)=i)$ ; chaque invité qui retrouve son chapeau compte pour $1$, donc $N={\sum }_{i=1}^n{1}_{A_i}$. Comme à l'exercice 1, $P(A_i)=\frac{(n-1)!}{n!}=\frac{1}{n}$ : les permutations fixant $i$ sont déterminées par une bijection des $n-1$ autres éléments. Par linéarité de l'espérance et grâce à $E(1_A)=P(A)$ : $$E(N)=\sum _{i=1}^{n}P(A_i)=n\times \frac{1}{n}=1.$$ En moyenne, un seul invité retrouve son chapeau, quel que soit le nombre d'invités.

b) Deux points fixes. Une permutation fixant $1$ et $2$ est déterminée par une bijection des $n-2$ autres éléments : il y en a $(n-2)!$, donc $$P(A_1\cap A_2)=\frac{(n-2)!}{n!}=\frac{1}{n(n-1)}.$$ Or $P(A_1)P(A_2)=\frac{1}{n^2}\ne \frac{1}{n(n-1)}$ : les événements ne sont pas indépendants. La dépendance est positive : $P(A_2\mid A_1)=\frac{1}{n-1}>\frac{1}{n}$ — si l'invité $1$ a récupéré son chapeau, il reste $n-1$ chapeaux pour $n-1$ invités. Le même calcul vaut pour tout couple $i\ne j$.

c) Le second moment, par les couples. Développons le carré de la somme : $$N^2=(\sum _{i=1}^n{1}_{A_i}{)}^2=\sum _{i=1}^n\sum _{j=1}^n{1}_{A_i}{1}_{A_j}=\sum _{i=1}^n{1}_{A_i}^2+\sum _{i\ne j}{1}_{A_i}{1}_{A_j}.$$ Une indicatrice ne prend que les valeurs $0$ et $1$, donc $1_A^2=1_A$ ; et le produit de deux indicatrices est l'indicatrice de l'intersection, $1_{A_i}{1}_{A_j}=1_{A_i\cap A_j}$. Par linéarité — la première somme a $n$ termes, la seconde $n(n-1)$, autant que de couples $(i,j)$ avec $i\ne j$ : $$E(N^2)=n\times \frac{1}{n}+n(n-1)\times \frac{1}{n(n-1)}=1+1=2.$$ Par la formule de Koenig-Huygens, $V(N)=E(N^2)-E(N{)}^2=2-1=1$. L'hypothèse $n\ge 2$ sert ici : pour $n=1$, il n'existe aucun couple $(i,j)$ avec $i\ne j$, et $N$, toujours égal à $1$, a une variance nulle.

Contrôle exhaustif, $n=3$. L'identité donne $N=3$, les trois permutations qui échangent deux éléments donnent $N=1$, les deux permutations circulaires donnent $N=0$ : $E(N)=\frac{3+3}{6}=1$ et $E(N^2)=\frac{9+3}{6}=2$. L'énumération complète jusqu'à $n=7$ donne exactement $1$ et $2$.

d) La concentration. L'inégalité de Bienaymé-Tchebychev, avec $E(N)=1$, $V(N)=1$ et $\epsilon =10$, donne $$P(|N-1|\ge 10)\le \frac{V(N)}{10^2}=\frac{1}{100}.$$ Or l'événement $(N\ge 11)$ est inclus dans $(|N-1|\ge 10)$ : si $N\ge 11$, alors $N-1\ge 10$. Par croissance de la probabilité, $P(N\ge 11)\le \frac{1}{100}$, quel que soit $n$ : à mille invités, moins d'une fois sur cent plus de dix personnes retrouvent leur chapeau. L'inégalité de Markov, avec la seule espérance, ne donnerait que $\frac{1}{11}$ : la variance apporte un facteur neuf.

Le point délicat. Espérance et variance ont été calculées sans aucune indépendance — le b) montre qu'il n'y en a pas. $E(N^2)$ ne demande que les probabilités des intersections deux à deux, c'est-à-dire la formule de transfert appliquée aux couples $(1_{A_i},1_{A_j})$, en séparant la diagonale $i=j$ du reste.

Ce que l'exercice installe. Toute variable de comptage est une somme d'indicatrices ; son espérance est une somme de probabilités, son second moment une somme de probabilités d'intersections. Ici, espérance et variance valent $1$ quel que soit $n$. Et le problème du TD 14 a donné la probabilité qu'aucun invité ne retrouve son chapeau, qui tend vers $\frac{1}{e}\approx 0,368$.