La méthode du second moment, et les points fixes d'une permutation

a) La minoration. Ce qu'on a le droit d'utiliser : si $X^2$ est d'espérance finie, $X$ l'est aussi ; l'inégalité de Cauchy-Schwarz, $E(UV{)}^2\le E(U^2)E(V^2)$ dès que $U^2$ et $V^2$ sont d'espérance finie ; une variable positive d'espérance nulle est nulle presque sûrement.

L'idée : une écriture exacte. Posons $Z=1_{(X>0)}$. En tout point $\omega$ de l'univers, $X=XZ$ : si $X(\omega )>0$, alors $Z(\omega )=1$ ; sinon $X(\omega )=0$, puisque $X$ est positive, et les deux membres sont nuls. C'est ici — et seulement ici — que sert la positivité : sans elle, l'événement $(X\ne 0)$ ne serait pas $(X>0)$.

Cauchy-Schwarz. $X^2$ est d'espérance finie, et $Z^2=Z$ est bornée par $1$. L'inégalité de Cauchy-Schwarz, appliquée à $X$ et à $Z$, donne $$E(X{)}^2=E(XZ{)}^2\le E(X^2)E(Z^2)=E(X^2)P(X>0),$$ car $E(Z^2)=E(Z)=P(X>0)$ : l'espérance d'une indicatrice est la probabilité de son événement.

La division est licite. Si l'on avait $E(X^2)=0$, la variable positive $X^2$ serait nulle presque sûrement, donc $X$ aussi, et $E(X)$ serait nulle, contrairement à l'hypothèse. Donc $E(X^2)>0$, et $$P(X>0)\ge \frac{E(X{)}^2}{E(X^2)}.$$

Le cas d'égalité. Notons $\rho =P(X>0)$ ; il est strictement positif, sinon $X$ serait nulle presque sûrement. Posons $c=\frac{E(X)}{\rho }>0$ et développons, par linéarité, l'espérance du carré de $X-cZ$, en utilisant $E(XZ)=E(X)$ et $E(Z^2)=\rho$ : $$E((X-cZ{)}^2)=E(X^2)-2cE(X)+c^2\rho =E(X^2)-\frac{E(X{)}^2}{\rho }.$$ Cette identité redonne l'inégalité — son membre de gauche est positif — et dit exactement quand elle est une égalité : si et seulement si la variable positive $(X-cZ{)}^2$ est d'espérance nulle, c'est-à-dire si et seulement si $X=cZ$ presque sûrement. Il y a égalité si et seulement si $X$ ne prend, presque sûrement, que deux valeurs : $0$ et une constante $c>0$. Par exemple, pour $X=c{1}_A$, le quotient vaut $\frac{c^{2}P(A{)}^2}{c^{2}P(A)}=P(A)=P(X>0)$ : la constante ne peut pas être améliorée. (C'est le cas d'égalité de Cauchy-Schwarz, au programme, redémontré sous la forme où il sert.)

b) Les points fixes. La stratégie : ne jamais chercher la loi de $F_n$, qui est compliquée. Les indicatrices donnent l'espérance par linéarité et le moment d'ordre deux par un double comptage, sans indépendance — elle est d'ailleurs fausse ici.

Pour $i\in [[1,n]]$, soit $A_i$ l'événement $(\sigma (i)=i)$, de sorte que $F_n={\sum }_{i=1}^n{1}_{A_i}$. Deux dénombrements, dans l'univers fini ${\mathfrak{S}}_n$ muni de la probabilité uniforme :

• les permutations qui fixent $i$ correspondent aux permutations des $n-1$ autres éléments : il y en a $(n-1)!$, donc $P(A_i)=\frac{(n-1)!}{n!}=\frac{1}{n}$ ;
• pour $i\ne j$, celles qui fixent $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)}$.

L'espérance. Par linéarité, $E(F_n)={\sum }_{i=1}^{n}P(A_i)=n\times \frac{1}{n}=1$.

Le moment d'ordre deux. Développons le carré de la somme : $F_n^2={\sum }_i{1}_{A_i}^2+{\sum }_{i\ne j}{1}_{A_i}{1}_{A_j}$, la seconde somme portant sur les $n(n-1)$ couples $(i,j)$ d'indices distincts. Or $1_{A_i}^2=1_{A_i}$ et $1_{A_i}{1}_{A_j}=1_{A_i\cap A_j}$. Par linéarité, $$E(F_n^2)=\sum _{i=1}^{n}P(A_i)+\sum _{i\ne j}P(A_i\cap A_j)=1+n(n-1)\cdot \frac{1}{n(n-1)}=2.$$ D'où $V(F_n)=E(F_n^2)-E(F_n{)}^2=2-1=1$. L'espérance et la variance valent $1$ quel que soit $n\ge 2$ : ce sont les deux premiers moments d'une loi de Poisson de paramètre $1$.

Les événements $A_i$ ne sont pas indépendants : $P(A_i\cap A_j)=\frac{1}{n(n-1)}$ est strictement plus grand que $P(A_i)P(A_j)=\frac{1}{n^2}$. Savoir que $i$ est fixe rend un second point fixe un peu plus probable.

c) Un point fixe, au moins une fois sur deux. $F_n$ est positive, $F_n^2$ est d'espérance finie (l'univers est fini) et $E(F_n)=1>0$. Comme $F_n$ est à valeurs entières, $(F_n>0)=(F_n\ge 1)$, et le a) donne, pour tout $n\ge 2$, $$P(F_n\ge 1)\ge \frac{E(F_n{)}^2}{E(F_n^2)}=\frac{1}{2}.$$

Le cas d'égalité. Pour $n=2$, les deux permutations sont l'identité, qui a deux points fixes, et l'échange des deux éléments, qui n'en a aucun : $F_2$ ne prend que les valeurs $0$ et $2$, c'est le cas d'égalité, et $P(F_2\ge 1)=\frac{1}{2}$. Pour $n\ge 3$, $F_n$ prend avec une probabilité non nulle deux valeurs strictement positives distinctes, $n$ (l'identité) et $n-2$ (l'échange de deux éléments) : l'inégalité est stricte.

Les valeurs exactes. Pour $n=3$, seules les deux permutations circulaires n'ont aucun point fixe : $P(F_3\ge 1)=1-\frac{2}{6}=\frac{2}{3}$. Pour $n=4$, les permutations sans point fixe sont les trois qui échangent deux paires et les six qui permutent circulairement les quatre éléments : $P(F_4\ge 1)=1-\frac{9}{24}=\frac{5}{8}=0,625$. La valeur limite, admise ici car elle relève de la formule du crible, hors programme, est $1-e^{-1}\approx 0,632$ ($\frac{19}{30}\approx 0,633$ déjà pour $n=5$). La minoration par $\frac{1}{2}$ n'est pas la valeur exacte, mais elle est uniforme en $n$, et obtenue sans rien savoir de la loi de $F_n$.

Ce que l'exercice installe. La méthode du second moment : pour minorer la probabilité qu'un objet aléatoire existe, on ne calcule pas la loi de $X$, mais ses deux premiers moments. Avec l'inégalité de Markov, qui majore par le premier ($P(X\ge 1)\le E(X)$ pour une variable entière), on encadre une probabilité d'existence entre $\frac{E(X{)}^2}{E(X^2)}$ et $E(X)$. Le cas d'égalité se lit sur une identité — l'espérance d'un carré est positive. C'est l'outil des graphes aléatoires et de la percolation, où l'on prouve qu'un chemin existe sans le construire.