La variance des points fixes

Stratégie : développer le carré d'une somme d'indicatrices, puis appliquer le transfert sur les couples. On sait déjà que $E(N)=1$ ; pour la variance, la formule de Koenig-Huygens demande $E\left(N^2\right)$, et le carré d'une somme se développe en une double somme dont chaque terme est une probabilité.

1) Le point de départ. Écrivons $N=\sum _{i=1}^n{1}_{A_i}$, où $A_i$ est l'événement « $\sigma (i)=i$ ». On sait que $P(A_i)=\frac{(n-1)!}{n!}=\frac{1}{n}$, donc $E(N)=1$.

2) Le développement du carré.

$$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}.$$

⚠️ Le point délicat est le traitement de la diagonale. Une indicatrice ne prend que les valeurs $0$ et $1$ : elle est donc égale à son propre carré, $1_{A_i}^2=1_{A_i}$. Les $n$ termes diagonaux se recollent en $N$, tandis que les $n(n-1)$ termes hors diagonale se traitent séparément. Confondre les deux familles fausse tout le compte.

Par ailleurs, pour $i\ne j$, le produit $1_{A_i}{1}_{A_j}$ vaut $1$ exactement quand les deux événements sont réalisés, c'est-à-dire $1_{A_i\cap A_j}$.

3) Le calcul de $E\left(N^2\right)$. Par linéarité :

$$E\left(N^2\right)=E(N)+\sum _{i\ne j}P(A_i\cap A_j).$$

Pour $i\ne j$, les permutations fixant à la fois $i$ et $j$ sont déterminées par une bijection des $n-2$ éléments restants sur eux-mêmes :

$$P(A_i\cap A_j)=\frac{(n-2)!}{n!}=\frac{1}{n(n-1)}.$$

Il y a exactement $n(n-1)$ couples ordonnés $(i,j)$ avec $i\ne j$, d'où

$$E\left(N^2\right)=1+n(n-1)\times \frac{1}{n(n-1)}=2.$$

4) La variance. Par la formule de Koenig-Huygens :

$$\boxed{V(N)=E\left(N^2\right)-E(N{)}^2=2-1=1.}$$

Espérance $1$, variance $1$, quel que soit $n$ — un fait remarquable : le nombre d'invités retrouvant leur chapeau ne dépend ni en moyenne ni en dispersion du nombre d'invités.

⚠️ L'hypothèse $n\ge 2$ est nécessaire, faute de quoi il n'existe aucun couple $(i,j)$ avec $i\ne j$ : pour $n=1$, la variable $N$ vaut toujours $1$ et sa variance est nulle.

5) La majoration par Bienaymé-Tchebychev. Avec $\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)$ : si $N\ge 11$ alors $N-1\ge 10$, donc $|N-1|\ge 10$. Par croissance de la probabilité :

$$\boxed{P(N\ge 11)\le \frac{1}{100}=1\%.}$$

⚠️ Le point délicat de cette dernière étape est qu'il s'agit d'une inclusion, non d'une égalité. L'inégalité de Bienaymé-Tchebychev majore un écart des deux côtés de la moyenne, alors qu'on ne s'intéresse ici qu'au côté droit. La majoration reste valable — elle est simplement un peu généreuse — mais il faut dire pourquoi elle s'applique.

Contrôle exhaustif. Pour $n$ de $2$ à $8$, un programme a parcouru toutes les permutations et calculé la moyenne du nombre de points fixes et celle de son carré : il trouve exactement $1$ et $2$ dans tous les cas, donc une variance de $1$ ✓. On vérifie aussi la formule $\frac{(n-2)!}{n!}=\frac{1}{n(n-1)}$ sur la même plage ✓.

Ce que l'exercice installe. Le moment d'ordre deux d'une somme d'indicatrices se calcule par transfert sur les couples d'indices, en séparant soigneusement la diagonale. Et la borne obtenue ne dépend pas de $n$ : c'est une inégalité de concentration, la forme la plus élémentaire des résultats qui gouvernent aujourd'hui l'analyse des algorithmes aléatoires.