Permutation aléatoire
# 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 $\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é $\scriptstyle \ (\Omega ,{\mathcal {A}},\mathbb {P} ).\$ Pour tout entier k compris entre 1 et n, posons

$\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, $\scriptstyle \ \sigma (k,\omega )\$ s'interprète comme le rang de $\scriptstyle \ X_{k}(\omega )\$ dans l'échantillon, une fois celui-ci rangé dans l'ordre croissant.

Proposition — L'application $\scriptstyle \ k\to \sigma (k,\omega )\$ est une permutation aléatoire uniforme.

On trouvera ici une démonstration de la proposition ci-dessus dans le cas où la distribution de probabilité commune aux variables $\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 :

### 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 $X_{n-i+1}$ de paramètre ${\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é ${\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 $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 $X_{1}+X_{2}+\cdots +X_{n}$, égal au nombre de fois où l'on a fermé un cycle, les $X_{i}$ étant indépendantes.

## 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 ${\mathcal {S}}_{n}$.

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

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

Le cas général $\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ù :

* $\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 $X_{1}+\cdots +X_{n}$, où $X_{k}$ prend la valeur 1 si k est un point fixe. On a $\mathbb {P} (X_{k}=1)={\frac {1}{n}}$ et $\mathbb {P} (X_{j}=X_{k}=1)={\frac {1}{n(n-1)}}$ pour j différent de k, d'où l'on tire :

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

### Nombre de descentes

Une descente d'une permutation π, élément de ${\mathcal {S}}_{n}$, est un indice i entre 1 et n-1 tel que π(i+1) < π(i). Le nombre de permutations de ${\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 ${\mathcal {S}}_{n}$ et qui associe à une permutation son nombre de descentes, alors :

* $\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 :

* $\mathbb {E} (X)={\frac {n-1}{2}}$
* $\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 ${\frac {n}{2}}$ et de variance ${\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 $K_{n}$ égale au nombre de cycles d'une permutation de {1, ..., n} est égale à $X_{1}+X_{2}+\cdots +X_{n}$, où les $X_{k}$ sont des variables de Bernoulli indépendantes de paramètres ${\frac {1}{k}}$. Il en résulte immédiatement la valeur de l'espérance et de la variance de $K_{n}$ :

* $\mathbb {E} (K_{n})=\sum _{k=1}^{n}\mathbb {E} (X_{k})=\sum _{k=1}^{n}{\frac {1}{k}}$
* $\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 :

* $\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 :

* $\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 $\left[{\begin{matrix}\scriptstyle n\\\scriptstyle k\end{matrix}}\right]$ :

* $\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 $K_{n}$ converge en loi vers la loi normale centrée réduite. Autrement dit, le théorème central limite s'applique à $K_{n}$, bien que les $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 $\sigma =(1573)(26)(48)$. Écrivons cette permutation en plaçant en dernier dans chaque cycle son élément le plus petit : $\sigma =(5731)(62)(84)$, et associons à la permutation la liste des nombres lus de gauche à droite Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://localhost:6011/fr.wikipedia.org/v1/ » :): {\displaystyle [5 7 3 1 6 2 8 4]} . 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 $Y_{n}$ la variable aléatoire telle que, pour tout permutation σ élément de ${\mathcal {S}}_{n}$, $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 $Z_{j}$ la variable aléatoire donnant le nombre d'indices i inférieurs à j formant une inversion avec j. $Y_{n}$ n'est autre que la somme $Z_{2}+\cdots +Z_{n}$ ($Z_{1}$ étant nécessairement nul).

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

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

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

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

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

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

* $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 $Y_{n}$ converge en loi vers la loi normale centrée réduite.

### 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.
