Les points fixes d'une permutation aléatoire

La stratégie. Ne jamais chercher la loi de $F_n$ : elle fait intervenir les dérangements et une formule d'inclusion-exclusion. On écrit $F_n$ comme un compteur, c'est-à-dire une somme d'indicatrices : l'espérance tombe par linéarité, et la variance ne demande que les probabilités d'intersections deux à deux.

a) Les indicatrices et l'espérance. Posons $A_i=(\sigma (i)=i)$ pour $i\in \{1,\dots ,n\}$, de sorte que $$F_n=\sum _{i=1}^n{1}_{A_i}.$$ Les permutations fixant $i$ sont en bijection avec les permutations de l'ensemble à $n-1$ éléments restant : il y en a $(n-1)!$. Donc $$P(A_i)=\frac{(n-1)!}{n!}=\frac{1}{n},1_{A_i}\sim \mathcal{B}\left(\frac{1}{n}\right),$$ et par linéarité $$E(F_n)=\sum _{i=1}^{n}P(A_i)=n\cdot \frac{1}{n}=1.$$ Une permutation aléatoire a en moyenne exactement un point fixe, quelle que soit sa taille — ce qui est déjà surprenant : ni $\ln n$, ni $\sqrt{n}$, mais $1$, pour $n=3$ comme pour $n=10^6$.

b) Les covariances. Soient $i\ne j$, ce qui suppose $n\ge 2$. Les permutations fixant $i$ et $j$ sont au nombre de $(n-2)!$, donc $$P(A_i\cap A_j)=\frac{(n-2)!}{n!}=\frac{1}{n(n-1)}.$$ Comme $1_{A_i}{1}_{A_j}=1_{A_i\cap A_j}$, il vient $$\mathrm{Cov}(1_{A_i},1_{A_j})=E(1_{A_i\cap A_j})-E(1_{A_i})E(1_{A_j})=\frac{1}{n(n-1)}-\frac{1}{n^2}=\frac{n-(n-1)}{n^2(n-1)}=\frac{1}{n^2(n-1)}.$$ Elle est strictement positive : savoir que $i$ est fixe augmente légèrement la chance que $j$ le soit, puisqu'il reste une place de moins où envoyer $j$ ailleurs. Les indicatrices ne sont donc pas indépendantes, et la variance n'est pas simplement additive.

c) La variance. Chaque $1_{A_i}$ étant de Bernoulli de paramètre $\frac{1}{n}$, sa variance vaut $\frac{1}{n}\left(1-\frac{1}{n}\right)$. La formule de la variance d'une somme, avec $\frac{n(n-1)}{2}$ couples $i<j$ — donc $n(n-1)$ après le facteur $2$ —, donne $$V(F_n)=\sum _{i=1}^{n}V(1_{A_i})+2\sum _{i<j}\mathrm{Cov}(1_{A_i},1_{A_j})=n\cdot \frac{1}{n}\left(1-\frac{1}{n}\right)+n(n-1)\cdot \frac{1}{n^2(n-1)},$$ c'est-à-dire $$V(F_n)=\left(1-\frac{1}{n}\right)+\frac{1}{n}=1.$$ Les deux $\frac{1}{n}$ se compensent exactement : c'est le terme de covariance, souvent oublié, qui restaure la valeur $1$.

Le cas de bord. Le calcul du b) suppose l'existence d'un couple $i\ne j$, donc $n\ge 2$. Pour $n=1$, il n'y a qu'une permutation et $F_1=1$ est constante : $E(F_1)=1$ mais $V(F_1)=0$, et l'égalité $V=1$ est fausse. L'énoncé est à lire pour $n\ge 2$.

d) L'erreur invisible, et la vérification à la main. En oubliant les covariances, on écrirait $V(F_n)=\sum V(1_{A_i})=1-\frac{1}{n}$ : un résultat presque juste — il tend vers $1$ — mais faux pour tout $n$ fini, et l'erreur est indétectable à l'œil nu.

Vérifions donc pour $n=3$, en énumérant les $6$ permutations : l'identité a $3$ points fixes, les $3$ transpositions en ont $1$ chacune, les $2$ cycles d'ordre $3$ n'en ont aucun. Donc $$E(F_3)=\frac{3+1+1+1+0+0}{6}=1,E(F_3^2)=\frac{9+1+1+1+0+0}{6}=2,$$ d'où $V(F_3)=E(F_3^2)-E(F_3{)}^2=2-1=1$. C'est bien $1$, et non $1-\frac{1}{3}=0,667$ : la formule sans covariances est fausse, et l'énumération le prouve.

Ce que l'exercice installe. Écrire un compteur comme une somme d'indicatrices est la méthode la plus rentable du chapitre : l'espérance tombe par linéarité sans jamais chercher la loi, et la variance ne demande que les probabilités d'intersections deux à deux. Elle s'applique telle quelle aux montées d'une permutation, aux collisions dans une table de hachage, aux triangles d'un graphe aléatoire — et le programme demande explicitement de faire travailler les élèves « sur divers objets aléatoires : permutations, graphes, matrices ». Plus profondément, $E(F_n)=V(F_n)=1$ est la signature de la loi de Poisson de paramètre $1$, pour laquelle moyenne et variance coïncident ; et le calcul des dérangements de première année donne $P(F_n=0)={\sum }_{k=0}^n\frac{(-1{)}^k}{k!}$, dont la valeur approche $e^{-1}\approx 0,368$ dès $n=5$ : un battage de cartes ne laisse aucune carte à sa place un peu plus d'une fois sur trois, et ce nombre ne dépend pratiquement pas de la taille du jeu.