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

La stratégie. La loi de $N$ est compliquée — on ne la calculera pas. On écrit $N$ comme 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 Bienaymé-Tchebychev conclut.

a) L'espérance. Chaque invité qui retrouve son chapeau contribue pour $1$ au compte : $N={\sum }_{i=1}^n{1}_{A_i}$. Par symétrie (exercice 1), $P(A_i)=\frac{(n-1)!}{n!}=\frac{1}{n}$ pour tout $i$ : les permutations fixant $i$ sont les permutations des $n-1$ autres éléments. Par linéarité de l'espérance et $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 $n$.

b) Deux points fixes. Pour $i\ne j$, une permutation fixant $i$ et $j$ est déterminée par sa restriction aux $n-2$ autres éléments : il y en a $(n-2)!$, donc $$P(A_i\cap A_j)=\frac{(n-2)!}{n!}=\frac{1}{n(n-1)}.$$ Or $P(A_i)P(A_j)=\frac{1}{n^2}$, et $\frac{1}{n(n-1)}\ne \frac{1}{n^2}$ : $A_i$ et $A_j$ ne sont pas indépendants. La dépendance est positive, $P(A_j\mid A_i)=\frac{1}{n-1}>\frac{1}{n}$ : si $i$ a récupéré son chapeau, il reste $n-1$ chapeaux pour $n-1$ invités, et $j$ a une chance sur $n-1$.

c) Le second moment par les couples. Développons le carré de la somme : $$N^2={\left(\sum _{i=1}^n{1}_{A_i}\right)}^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}.$$ Or une indicatrice vérifie $1_A^2=1_A$ (elle ne prend que les valeurs $0$ et $1$), et le produit de deux indicatrices est l'indicatrice de l'intersection : $1_{A_i}{1}_{A_j}=1_{A_i\cap A_j}$. Donc $$N^2=\sum _{i=1}^n{1}_{A_i}+\sum _{i\ne j}{1}_{A_i\cap A_j},$$ et, par linéarité — il y a $n$ termes dans la première somme et $n(n-1)$ couples $(i,j)$ avec $i\ne j$ dans la seconde : $$E(N^2)=\sum _{i=1}^{n}P(A_i)+\sum _{i\ne j}P(A_i\cap A_j)=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.$$

Contrôle exhaustif. Pour $n=2$ : les deux permutations donnent $N=2$ (l'identité) et $N=0$ (la transposition), chacune avec probabilité $\frac{1}{2}$ ; $E(N)=1$, $E(N^2)=\frac{4+0}{2}=2$, $V(N)=1$. Pour $n=3$ : l'identité donne $N=3$, les trois transpositions donnent $N=1$, les deux $3$-cycles donnent $N=0$ ; $E(N)=\frac{3+3\times 1+0}{6}=1$ et $E(N^2)=\frac{9+3\times 1+0}{6}=2$.

d) Concentration. L'inégalité de Bienaymé-Tchebychev, avec $E(N)=1$, $V(N)=1$ et $\epsilon =10$ : $$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)$, donc, par croissance de la probabilité, $P(N\ge 11)\le \frac{1}{100}$. La borne ne dépend pas de $n$ — et pour $n\le 10$ elle est triviale, puisque $N\le n$ ; c'est pour les grandes assemblées qu'elle dit quelque chose : à mille invités, moins d'une fois sur cent plus de dix personnes retrouvent leur chapeau. (Markov, avec la seule espérance, ne donnerait que $P(N\ge 11)\le \frac{1}{11}$ : la variance apporte un facteur neuf.)

Le point délicat. L'espérance et la variance de $N$ ont été calculées sans aucune indépendance — les $A_i$ ne sont pas indépendants, le b) le montre. La linéarité ne demande rien ; c'est le calcul de $E(N^2)$ qui demande les probabilités des intersections deux à deux, et rien de plus. Le développement du carré est la « formule de transfert sur les couples » : on n'a eu besoin que de la loi conjointe de $(1_{A_i},1_{A_j})$, c'est-à-dire de $P(A_i\cap A_j)$.

Ce que l'exercice installe. Toute variable de comptage est une somme d'indicatrices ; son espérance est une somme de probabilités, sa variance une somme de probabilités d'intersections. Ici, moyenne et variance valent $1$ quel que soit $n$ : le nombre de points fixes d'une grande permutation aléatoire ne fluctue presque pas — on montrera en seconde année qu'il suit approximativement la loi de Poisson de paramètre $1$. Et le chapitre de dénombrement a déjà dit ce que vaut $P(N=0)$, la proportion de dérangements : $\sum _{k=0}^n\frac{(-1{)}^k}{k!}$, qui tend vers $\frac{1}{e}\approx 0,368$.