Une permutation tirée au hasard

Ce qu'on a le droit d'utiliser. Le chapitre de dénombrement : il y a $n!$ bijections de $\{1,\dots ,n\}$ sur lui-même, donc $\mathrm{card}\Omega =n!$, et $P(C)=\frac{\mathrm{card}C}{n!}$ pour tout événement $C$. La stratégie : une bijection de $\Omega$ qui envoie un événement sur un autre leur donne le même cardinal, donc la même probabilité — ce qui n'est vrai que parce que la probabilité est uniforme.

a) La valeur de $\sigma (1)$. Une permutation vérifiant $\sigma (1)=1$ est entièrement déterminée par sa restriction à $\{2,\dots ,n\}$, qui est une bijection de cet ensemble sur lui-même : il y en a $(n-1)!$. Donc $$P(\sigma (1)=1)=\frac{(n-1)!}{n!}=\frac{1}{n}.$$ Pour $\sigma (1)=2$, le compte est le même : une telle permutation est déterminée par une bijection de $\{2,\dots ,n\}$ sur $\{1,3,\dots ,n\}$, deux ensembles à $n-1$ éléments ; il y en a encore $(n-1)!$, donc $P(\sigma (1)=2)=\frac{1}{n}$. Le même argument donne $P(\sigma (1)=j)=\frac{1}{n}$ pour tout $j$ : $\sigma (1)$ suit la loi uniforme sur $\{1,\dots ,n\}$.

b) La symétrie. Notons $A=(\sigma (1)<\sigma (2))$ et $A^{\prime }=(\sigma (1)>\sigma (2))$.

Premier constat : $A$ et $A^{\prime }$ forment un système complet d'événements. Ils sont incompatibles, et leur réunion est $\Omega$ tout entier, parce que le cas $\sigma (1)=\sigma (2)$ est impossible : $\sigma$ est injective et $1\ne 2$. Donc $P(A)+P(A^{\prime })=1$.

Second constat : $A$ et $A^{\prime }$ ont le même cardinal. Associons à $\sigma$ la permutation $\Phi (\sigma )$ qui échange les deux premières valeurs : $\Phi (\sigma )(1)=\sigma (2)$, $\Phi (\sigma )(2)=\sigma (1)$, et $\Phi (\sigma )(i)=\sigma (i)$ pour $i\ge 3$. C'est encore une bijection de $\{1,\dots ,n\}$ — elle prend les mêmes valeurs que $\sigma$, dans un autre ordre —, donc un élément de $\Omega$. L'application $\Phi$ est sa propre réciproque, puisque échanger deux fois les mêmes valeurs ne change rien : c'est une bijection de $\Omega$. Enfin $\sigma \in A$ si et seulement si $\Phi (\sigma )\in A^{\prime }$ : $\Phi$ réalise une bijection de $A$ sur $A^{\prime }$, et $\mathrm{card}A=\mathrm{card}{A}^{\prime }$.

En combinant : $2\mathrm{card}A=n!$, donc $P(\sigma (1)<\sigma (2))=\frac{1}{2}$.

c) Les records. Fixons $k$ et, pour $j\in \{1,\dots ,k\}$, notons $M_j$ l'événement « la plus grande des $k$ valeurs $\sigma (1),\dots ,\sigma (k)$ est $\sigma (j)$ ». L'événement « $k$ est un record » est exactement $M_k$ : $\sigma (k)$ dépasse toutes les valeurs précédentes si et seulement si elle est la plus grande des $k$ premières.

Les $M_j$ forment un système complet. Les valeurs $\sigma (1),\dots ,\sigma (k)$ sont deux à deux distinctes, par injectivité ; leur maximum est donc atteint en exactement un indice. D'où $P(M_1)+\cdots +P(M_k)=1$.

Ils ont tous le même cardinal. Soit $j<k$, et ${\Phi }_j(\sigma )$ la permutation qui échange les valeurs placées en $j$ et en $k$ et garde les autres. Comme au b), ${\Phi }_j$ est une bijection de $\Omega$, sa propre réciproque. L'échange se fait à l'intérieur des $k$ premières places : l'ensemble $\{\sigma (1),\dots ,\sigma (k)\}$ est inchangé, et la valeur qui occupait la place $k$ occupe désormais la place $j$. Donc $\sigma \in M_k$ si et seulement si ${\Phi }_j(\sigma )\in M_j$, et $\mathrm{card}{M}_j=\mathrm{card}{M}_k$.

En combinant : $kP(M_k)=1$, soit $P(k\text{ est un record})=\frac{1}{k}$.

Vérification par dénombrement. Choisir l'ensemble des $k$ premières valeurs — $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ façons, le coefficient binomial se lisant « $k$ parmi $n$ » —, placer la plus grande en position $k$, ranger les $k-1$ autres puis les $n-k$ suivantes : $\left(\genfrac{}{}{0ex}{}{n}{k}\right)(k-1)!(n-k)!=\frac{n!}{k}$ permutations. La symétrie l'avait dit sans une factorielle.

Contrôle exhaustif, $n=3$. Les six permutations, écrites $(\sigma (1),\sigma (2),\sigma (3))$ : $123$, $132$, $213$, $231$, $312$, $321$. L'événement $\sigma (1)<\sigma (2)$, qui est aussi « $2$ est un record », contient $123$, $132$ et $231$ : $\frac{3}{6}=\frac{1}{2}$. Et $3$ est un record pour $123$ et $213$ : $\frac{2}{6}=\frac{1}{3}$.

Le point délicat. Deux vérifications que l'on oublie : que les événements comparés recouvrent l'univers — c'est l'injectivité qui élimine le cas d'égalité —, et que la bijection envoie bien l'un sur l'autre. Et l'argument n'est licite que sous la probabilité uniforme.

Ce que l'exercice installe. La symétrie est un instrument de calcul : quand une bijection de l'univers échange des événements, ils sont équiprobables. Avec la linéarité de l'espérance, qui servira à l'exercice 7, le nombre moyen de records vaut $1+\frac{1}{2}+\cdots +\frac{1}{n}$, qui croît comme $\ln n$ : cent relevés annuels dans un ordre tiré uniformément ne donnent en moyenne qu'environ cinq records — en observer beaucoup plus signale une tendance.