Une permutation tirée au hasard

Ce qu'on a le droit d'utiliser. L'univers est $\Omega ={\mathcal{S}}_n$, de cardinal $n!$, muni de la probabilité uniforme : pour tout événement $C$, $P(C)=\frac{\mathrm{card}C}{n!}$. Toute la stratégie tient en une phrase : une bijection de $\Omega$ qui envoie un événement sur un autre leur donne le même cardinal, donc la même probabilité — et cela n'est vrai que parce que la probabilité est uniforme.

a) La valeur de $\sigma (1)$. Une permutation telle que $\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 : la valeur $\sigma (1)$ est imposée, et les $n-1$ autres valeurs se répartissent librement sur les $n-1$ éléments restants, soit $(n-1)!$ permutations, d'où $P(\sigma (1)=2)=\frac{1}{n}$ — et de même $P(\sigma (1)=j)=\frac{1}{n}$ pour tout $j$ : $\sigma (1)$ suit la loi uniforme sur $\{1,\dots ,n\}$, aucune valeur n'est privilégiée.

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

Premier constat : $A$ et $A^{\prime }$ forment un système complet. 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. Soit $\tau$ la transposition qui échange $1$ et $2$, et $\Phi :\sigma \mapsto \sigma \circ \tau$. Pour toute permutation $\sigma$, $(\sigma \circ \tau )(1)=\sigma (2)$ et $(\sigma \circ \tau )(2)=\sigma (1)$ : $\Phi$ échange les valeurs $\sigma (1)$ et $\sigma (2)$ et laisse les autres en place, donc $\sigma \in A$ si et seulement si $\Phi (\sigma )\in A^{\prime }$. De plus $\Phi \circ \Phi =\mathrm{Id}$, puisque $\tau \circ \tau =\mathrm{Id}$ : $\Phi$ est une bijection de $\Omega$, qui envoie $A$ dans $A^{\prime }$ et $A^{\prime }$ dans $A$. En appliquant $\Phi$ à l'inclusion $\Phi (A^{\prime })\subset A$, on obtient $A^{\prime }=\Phi (\Phi (A^{\prime }))\subset \Phi (A)$ ; avec $\Phi (A)\subset A^{\prime }$, cela donne $\Phi (A)=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) Trois valeurs, six ordres. Notons $D=(\sigma (1)<\sigma (2)<\sigma (3))$. Les trois valeurs $\sigma (1),\sigma (2),\sigma (3)$ sont deux à deux distinctes, par injectivité ; elles sont donc rangées dans exactement un des six ordres possibles. Précisément, pour chaque permutation $\rho$ de $\{1,2,3\}$, notons $D_{\rho }$ l'événement $(\sigma (\rho (1))<\sigma (\rho (2))<\sigma (\rho (3)))$ : les six événements $D_{\rho }$ sont deux à deux incompatibles et de réunion $\Omega$, et $D$ est celui qui correspond à $\rho =\mathrm{Id}$.

Montrons qu'ils ont tous le même cardinal. Prolongeons $\rho$ en une permutation de $\{1,\dots ,n\}$ en la laissant fixer $4,\dots ,n$, et posons ${\Phi }_{\rho }:\sigma \mapsto \sigma \circ \rho$. Alors $(\sigma \circ \rho )(i)=\sigma (\rho (i))$ pour $i=1,2,3$, de sorte que $$\sigma \in D_{\rho }⟺\sigma (\rho (1))<\sigma (\rho (2))<\sigma (\rho (3))⟺\sigma \circ \rho \in D.$$ L'application ${\Phi }_{\rho }$ est une bijection de $\Omega$ (sa réciproque est $\sigma \mapsto \sigma \circ {\rho }^{-1}$), et l'équivalence ci-dessus dit qu'elle envoie $D_{\rho }$ sur $D$ : $\mathrm{card}{D}_{\rho }=\mathrm{card}D$. Les six événements ont donc le même cardinal, et $6\mathrm{card}D=n!$ : $$P(\sigma (1)<\sigma (2)<\sigma (3))=\frac{1}{6}.$$

Vérification par dénombrement direct. On choisit l'ensemble des trois valeurs $\{\sigma (1),\sigma (2),\sigma (3)\}$ : $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$ choix (« trois parmi $n$ ») ; elles doivent être attribuées dans l'ordre croissant, ce qui ne laisse qu'une possibilité ; puis les $n-3$ autres valeurs se répartissent librement : $(n-3)!$ façons. D'où $\mathrm{card}D=\left(\genfrac{}{}{0ex}{}{n}{3}\right)(n-3)!=\frac{n!}{3!(n-3)!}(n-3)!=\frac{n!}{6}$. C'est bien $\frac{1}{6}$ — mais la symétrie l'a donné sans écrire une seule factorielle.

d) Deux événements qui ne sont pas indépendants. On a $A\cap B=D$, donc $P(A\cap B)=\frac{1}{6}$, alors que $P(A)P(B)=\frac{1}{2}\times \frac{1}{2}=\frac{1}{4}$ (le b) vaut pour $B$ comme pour $A$, avec la transposition qui échange $2$ et $3$). Comme $\frac{1}{6}\ne \frac{1}{4}$, $A$ et $B$ ne sont pas indépendants. Le sens de la dépendance : $P(B\mid A)=\frac{1/6}{1/2}=\frac{1}{3}<\frac{1}{2}=P(B)$ — savoir que $\sigma (2)$ dépasse $\sigma (1)$ le rend « plutôt grand », donc moins susceptible d'être dépassé à son tour.

Contrôle exhaustif, $n=3$. Les six permutations, écrites $(\sigma (1),\sigma (2),\sigma (3))$ : $123$, $132$, $213$, $231$, $312$, $321$. L'événement $A$ contient $123$, $132$, $231$ : probabilité $\frac{3}{6}=\frac{1}{2}$. L'événement $B$ contient $123$, $213$, $312$ : $\frac{1}{2}$. L'intersection ne contient que $123$ : $\frac{1}{6}$. Et $\frac{1}{6}\ne \frac{1}{4}$.

Le point délicat. Le raisonnement de symétrie n'est licite que parce que la probabilité est uniforme : une bijection entre deux événements ne dit rien de leurs probabilités si les issues ne sont pas équiprobables. Et il fallait vérifier que les cas se recouvrent — éliminer $\sigma (1)=\sigma (2)$ — sans quoi on n'aurait obtenu que $P(A)\le \frac{1}{2}$.

Ce que l'exercice installe. La symétrie est un instrument de calcul : quand une bijection de l'univers échange deux événements, ils sont équiprobables, et l'on n'a plus rien à compter. On retrouvera exactement ce geste à l'exercice 7 pour les points fixes d'une permutation, où il donnera $P(\sigma (i)=i)=\frac{1}{n}$ sans qu'on ait à écrire la loi du nombre de points fixes — que personne ne sait écrire simplement.