Permutation aléatoire

Une permutation aléatoire de taille N, est une permutation prise de manière uniforme dans l'ensemble des permutations de taille N.

De nombreux paramètres ont été étudiés sur les permutations aléatoires, par exemple, le nombre moyen de points fixes ou la longueur des cycles. Plusieurs algorithmes existent pour générer des permutations aléatoires à partir d'un générateur de nombres aléatoires, par exemple le mélange de Fisher-Yates.

Génération de permutations aléatoires

Génération à l'aide de variables aléatoires à densité

Soit ${\displaystyle \scriptstyle \ X=(X_{1},X_{2},\dots ,X_{n})\ }$ une suite de variables aléatoires i.i.d. à densité, définies sur un espace probabilisé ${\displaystyle \scriptstyle \ (\Omega ,{\mathcal {A}},\mathbb {P} ).\ }$ Pour tout entier k compris entre 1 et n, posons

${\displaystyle \sigma (k,\omega )\ =\ \mathrm {Card} \left\{i\ \mathrm {tels~que} \ 1\leq i\leq n,\ \mathrm {et~tels~que} \ X_{i}(\omega )\leq X_{k}(\omega )\right\}.\ }$

Ainsi, ${\displaystyle \scriptstyle \ \sigma (k,\omega )\ }$ s'interprète comme le rang de ${\displaystyle \scriptstyle \ X_{k}(\omega )\ }$ dans l'échantillon, une fois celui-ci rangé dans l'ordre croissant.

On trouvera ici une démonstration de la proposition ci-dessus dans le cas où la distribution de probabilité commune aux variables ${\displaystyle \scriptstyle \ X_{i}\ }$ est la loi uniforme sur [0,1]. On peut en fait se contenter de variables i.i.d. dont la loi est diffuse (sans atomes) modulo une modification mineure de la démonstration. Cependant la loi uniforme est particulièrement commode pour diverses applications.

Algorithme de Fisher-Yates

Le mélange de Fisher-Yates, également appelé mélange de Knuth, est un algorithme en place permettant d'appliquer une permutation aléatoire à n éléments en temps linéaire, les n! permutations possibles étant équiprobables en sortie.

Le principe de cet algorithme est le suivant :

pour i de n - 1 descendant_à 1 :
      j ← nombre aléatoire entier 0 ≤ j ≤ i
      échanger a[j] et a[i]

Génération par les cycles

On peut définir une permutation aléatoire sur l'ensemble {1, ..., n} selon une loi uniforme en définissant les cycles de cette permutation.

On commence par former un cycle commençant par le nombre 1, ce qui constitue l'étape 1 du processus.

Pour i variant de 1 à n, l'étape i est celle où i nombres ont déjà été utilisés pour définir des cycles de la permutation, le dernier cycle étant en cours de construction. Au début de cette étape, il reste n-i nombres non utilisés. On utilise une variable de Bernoulli ${\displaystyle X_{n-i+1}}$ de paramètre ${\displaystyle {\frac {1}{n-i+1}}}$ pour terminer l'étape i et passer à l'étape suivante :

• Si la variable aléatoire prend la valeur 1 (avec donc la probabilité ${\displaystyle {\frac {1}{n-i+1}}}$), on ferme le cycle en cours de construction, et on en ouvre un autre avec la plus petite des n-i valeurs non utilisées.
• Si la variable aléatoire prend la valeur 0, on tire au hasard l'une des n-i valeurs non utilisées selon une loi uniforme, la valeur tirée constituant la valeur suivante du cycle en cours de construction.

À la dernière étape, on utilise la variable ${\displaystyle X_{1}}$, qui est une variable certaine égale à 1, correspondant au fait qu'on ferme le dernier cycle.

L'intérêt de cette démarche est que la variable aléatoire égale au nombre de cycles de la permutation n'est autre que ${\displaystyle X_{1}+X_{2}+\cdots +X_{n}}$, égal au nombre de fois où l'on a fermé un cycle, les ${\displaystyle X_{i}}$ étant indépendantes^[1].

Variables aléatoires portant sur les permutations

Nombre de points fixes

Soit N la variable aléatoire donnant le nombre de points fixes d'une permutation tirée au hasard dans le groupe symétrique ${\displaystyle {\mathcal {S}}_{n}}$.

La probabilité ${\displaystyle \mathbb {P} (N=0)}$ n'est autre que le quotient par n! du nombre de dérangements parmi n éléments, à savoir :

• ${\displaystyle \mathbb {P} (N=0)=\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$

Le cas général ${\displaystyle \mathbb {P} (N=r)}$ s'obtient en divisant par n! le nombre de permutations ayant r points fixes. On dénombre ces dernières en choisissant r éléments parmi n (qui seront les points fixes), puis en choisissant un dérangement sur les n - r éléments restants. D'où :

• ${\displaystyle \mathbb {P} (N=r)={\frac {1}{n!}}{\binom {n}{r}}(n-r)!\sum _{k=0}^{n-r}{\frac {(-1)^{k}}{k!}}={\frac {1}{r!}}\sum _{k=0}^{n-r}{\frac {(-1)^{k}}{k!}}}$

N converge en loi vers la loi de Poisson de paramètre 1.

Le calcul de l'espérance et de la variance se fait aisément en remarquant que N est la somme des variables aléatoires de Bernoulli ${\displaystyle X_{1}+\cdots +X_{n}}$, où ${\displaystyle X_{k}}$ prend la valeur 1 si k est un point fixe. On a ${\displaystyle \mathbb {P} (X_{k}=1)={\frac {1}{n}}}$ et ${\displaystyle \mathbb {P} (X_{j}=X_{k}=1)={\frac {1}{n(n-1)}}}$ pour j différent de k, d'où l'on tire :

• ${\displaystyle \mathbb {E} (N)=1}$
• ${\displaystyle \mathbb {V} (N)=1}$

Nombre de descentes

Une descente d'une permutation π, élément de ${\displaystyle {\mathcal {S}}_{n}}$, est un indice i entre 1 et n-1 tel que π(i+1) < π(i). Le nombre de permutations de ${\displaystyle {\mathcal {S}}_{n}}$ ayant k descentes est, par définition, le nombre eulérien A(n,k).

Si X est la variable aléatoire définie sur ${\displaystyle {\mathcal {S}}_{n}}$ et qui associe à une permutation son nombre de descentes, alors :

• ${\displaystyle \mathbb {P} (X=k)={\frac {A(n,k)}{n!}}}$

Pour n=1, X est la variable certaine 0.

Pour n supérieur ou égal à 2, on montre que^[2] :

• ${\displaystyle \mathbb {E} (X)={\frac {n-1}{2}}}$
• ${\displaystyle \mathbb {V} (X)={\frac {n+1}{12}}}$

Si S est la somme de n variables aléatoires indépendantes suivant chacune une loi uniforme continue sur [0, 1], S suit une loi de Irwin-Hall, d'espérance ${\displaystyle {\frac {n}{2}}}$ et de variance ${\displaystyle {\frac {n}{12}}}$. On montre que X et la partie entière de S suivent la même loi de probabilité.

Plus longue sous-suite croissante

Par exemple, la plus longue sous-suite croissante de la permutation (15423) est (123) de longueur 3. La loi de cette longueur est en relation avec la percolation de dernier passage dans le carré.

Nombre des cycles et nombre de records

Comme vu plus haut, la variable aléatoire ${\displaystyle K_{n}}$ égale au nombre de cycles d'une permutation de {1, ..., n} est égale à ${\displaystyle X_{1}+X_{2}+\cdots +X_{n}}$, où les ${\displaystyle X_{k}}$ sont des variables de Bernoulli indépendantes de paramètres ${\displaystyle {\frac {1}{k}}}$. Il en résulte^[1] immédiatement la valeur de l'espérance et de la variance de ${\displaystyle K_{n}}$ :

• ${\displaystyle \mathbb {E} (K_{n})=\sum _{k=1}^{n}\mathbb {E} (X_{k})=\sum _{k=1}^{n}{\frac {1}{k}}}$
• ${\displaystyle \mathbb {V} (K_{n})=\sum _{k=1}^{n}\mathbb {V} (X_{k})=\sum _{k=1}^{n}{\frac {1}{k}}\left(1-{\frac {1}{k}}\right)}$

Quant à la loi du nombre de cycles, elle vaut :

• ${\displaystyle \mathbb {P} (K_{n}=r)={\frac {1}{n}}\sum _{1\leq k_{1}<k_{2}<\cdots <k_{r-1}\leq n-1}{\frac {1}{k_{1}k_{2}\cdots k_{r-1}}}}$

et elle vérifie la relation de récurrence :

• ${\displaystyle \mathbb {P} (K_{n}=r)={\frac {1}{n}}\mathbb {P} (K_{n-1}=r-1)+{\frac {n-1}{n}}\mathbb {P} (K_{n-1}=r)}$

On peut aussi l'exprimer en fonction des nombres de Stirling de première espèce non signés, notés ${\displaystyle \left[{\begin{matrix}\scriptstyle n\\\scriptstyle k\end{matrix}}\right]}$ :

• ${\displaystyle \mathbb {P} (K_{n}=r)={\frac {1}{n!}}\left[{\begin{matrix}\scriptstyle n\\\scriptstyle k\end{matrix}}\right]}$

La variable centrée réduite obtenue à partir de ${\displaystyle K_{n}}$ converge en loi vers la loi normale centrée réduite^[3]. Autrement dit, le théorème central limite s'applique à ${\displaystyle K_{n}}$, bien que les ${\displaystyle X_{k}}$ ne soient pas de même loi.

La loi du nombre de cycles est identique à celle du nombre de records d'une permutation. Cette identité est apparente lorsqu'on utilise la correspondance fondamentale de Foata, qu'on illustre par l'exemple suivant. Soit la permutation ${\displaystyle \sigma =(1573)(26)(48)}$. Écrivons cette permutation en plaçant en dernier dans chaque cycle son élément le plus petit : ${\displaystyle \sigma =(5731)(62)(84)}$, et associons à la permutation la liste des nombres lus de gauche à droite ${\displaystyle [57316284]}$. Cette liste permet de reconstituer les cycles, le premier cycle se terminant par 1, le second par le plus petit nombre n'apparaissant pas dans le premier cycle, le troisième cycle se terminant par le plus petit nombre n'apparaissant pas dans les deux premiers cycles, etc. Mais si on lit la liste de droite à gauche, les nombres terminant les cycles, ((4, 2, 1) dans l'exemple), sont tels que chacun d'eux est inférieur à tous les autres nombres situés plus à droite qu'eux. Ils constituent des records vers le bas. La correspondance de Foata permet donc d'établir une correspondance entre les variables aléatoires dénombrant le nombre de cycles, et celle dénombrant les records vers le bas.

Par symétrie, la variable aléatoire donnant le nombre de records vers le haut a même loi que la variable aléatoire donnant le nombre de record vers le bas, et donc même loi que la variable aléatoire donnant le nombre de cycles.

Nombre d'inversions

Soit ${\displaystyle Y_{n}}$ la variable aléatoire telle que, pour tout permutation σ élément de ${\displaystyle {\mathcal {S}}_{n}}$, ${\displaystyle Y_{n}(\sigma )}$ donne le nombre d'inversions de σ, c'est-à-dire le nombre de couples (i, j) tels que i < j, mais que σ(i) > σ(j).

Pour j variant de 1 à n, notons ${\displaystyle Z_{j}}$ la variable aléatoire donnant le nombre d'indices i inférieurs à j formant une inversion avec j. ${\displaystyle Y_{n}}$ n'est autre que la somme ${\displaystyle Z_{2}+\cdots +Z_{n}}$ (${\displaystyle Z_{1}}$ étant nécessairement nul).

${\displaystyle (Z_{2},\cdots ,Z_{n})}$ est à valeurs dans ${\displaystyle [\![0,1]\!]\times [\![0,2]\!]\times \dots \times [\![0,n-1]\!]}$, et l'application :

${\displaystyle \sigma \in {\mathcal {S}}_{n}\to (Z_{2}(\sigma ),\cdots ,Z_{n}(\sigma ))\in [\![0,1]\!]\times [\![0,2]\!]\times \dots \times [\![0,n-1]\!]}$

est bijective^[4]. Pour tout j, ${\displaystyle Z_{j}}$ suit une loi uniforme sur ${\displaystyle [\![0,j-1]\!]}$, et ces variables sont indépendantes. On a ${\displaystyle \mathbb {E} (Z_{j})={\frac {j-1}{2}}}$ et ${\displaystyle \mathbb {V} (Z_{j})={\frac {j^{2}-1}{12}}}$. D'où l'on déduit^[4],[1] :

• ${\displaystyle \mathbb {E} (Y_{n})={\frac {(n-1)n}{4}}}$
• ${\displaystyle \mathbb {V} (Y_{n})={\frac {(n-1)n(2n+5)}{72}}}$

La loi de ${\displaystyle Y_{n}}$ n'est pas exprimable simplement, mais on peut utiliser le fait que ${\displaystyle Y_{n-1}}$ a même loi que ${\displaystyle (Z_{2},\cdots ,Z_{n-1})}$ pour en déduire que ${\displaystyle Y_{n}}$ a même loi que ${\displaystyle Y_{n-1}+Z_{n}}$, ces deux variables étant indépendantes. Il en résulte une définition récursive des lois^[5] :

• ${\displaystyle \mathbb {P} (Y_{n}=k)={\frac {1}{n}}\sum _{j={\rm {max}}(0,k-n+1)}^{k}\mathbb {P} (Y_{n-1}=j)}$

Enfin, ${\displaystyle Y_{n}}$ étant la somme des variables aléatoires indépendantes ${\displaystyle Z_{j}}$, sa fonction génératrice ${\displaystyle G_{Y_{n}}}$ est le produit des fonctions génératrices des ${\displaystyle Z_{j}}$^[4] :

• ${\displaystyle G_{Y_{n}}(z)={\frac {\prod _{j=1}^{n}(1-z^{j})}{n!(1-z)^{n}}}}$

Lorsque n tend vers l'infini, la variable centrée réduite déduite de ${\displaystyle Y_{n}}$ converge en loi vers la loi normale centrée réduite^[6].

Longueur des cycles

En attendant le développement de cette section, on pourra se reporter aux pages suivantes

• Nombre de records et nombre de cycles d'une permutation,
• Correspondance fondamentale de Foata, en particulier à la section Stick-breaking process et processus de Poisson-Dirichlet,
• Code de Lehmer,
• Nombre de Stirling.

Notes et références

• Portail des probabilités et de la statistique
• Portail de l'informatique théorique