Voir la source de Permutation aléatoire

{{Ébauche|probabilités et statistiques|informatique théorique}}
Une '''permutation aléatoire''' de taille N, est une [[permutation]] prise de manière [[Loi uniforme discrète|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 <math>\scriptstyle\ X=(X_{1}, X_{2}, \dots, X_{n})\ </math> une suite de variables aléatoires i.i.d. à [[Densité de probabilité|densité]], définies sur un espace probabilisé <math>\scriptstyle\ (\Omega,\mathcal A,\mathbb P).\ </math> Pour tout entier ''k'' compris entre 1 et ''n'', posons
<center><math>\sigma(k,\omega)\ =\  \mathrm{Card}\left\{i\ \mathrm{tels~que}\ 1\le i\le n,\ \mathrm{et~tels~que}\ X_{i}(\omega)\le X_{k}(\omega)\right\}.\ </math></center>
Ainsi, <math>\scriptstyle\ \sigma(k,\omega)\ </math> s'interprète comme le '''''rang''''' de <math>\scriptstyle\ X_{k}(\omega)\ </math> dans l'échantillon, une fois celui-ci rangé dans l'ordre croissant.
{{Théorème|Proposition| L'application <math>\scriptstyle\ k\to\sigma(k,\omega)\ </math> est une permutation aléatoire uniforme.}}
On trouvera [[Loi uniforme continue#Construction d'une permutation aléatoire uniforme à l'aide d'un échantillon de loi uniforme|ici]] une démonstration de la proposition ci-dessus dans le cas où la [[Loi de probabilité|distribution de probabilité]] commune aux variables <math>\scriptstyle\ X_{i}\ </math> est la [[Loi uniforme continue|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 continue|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 [[Loi de Bernoulli|variable de Bernoulli]] <math>X_{n-i+1}</math> de paramètre <math>\frac1{n-i+1}</math> pour terminer l'étape ''i'' et passer à l'étape suivante :
* Si la variable aléatoire prend la valeur 1 (avec donc la probabilité <math>\frac1{n-i+1}</math>), 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 <math>X_1</math>, 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 <math>X_1 + X_2 + \cdots + X_n</math>, égal au nombre de fois où l'on a fermé un cycle, les <math>X_i</math> étant indépendantes<ref name=Feller>{{article|auteur=W. Feller|titre=The fundamental limit theorems in probability|périodique=Bull. Amer. Math. Soc|langue=en|volume=51|numéro=11|année=1945|pages=800-832|lire en ligne=http://www.ams.org/bull/1945-51-11/S0002-9904-1945-08448-1/S0002-9904-1945-08448-1.pdf}}</ref>.

== Variables aléatoires portant sur les permutations ==
=== Nombre de points fixes ===
Soit ''N'' la variable aléatoire donnant le nombre de [[Loi de Bernoulli#Points fixes d'une permutation tirée au hasard|points fixes d'une permutation tirée au hasard]] dans le groupe symétrique <math>\mathcal S_n</math>. 

La probabilité <math>\mathbb P(N=0)</math> n'est autre que le quotient par ''n''! du nombre de [[Principe d'inclusion-exclusion#Dérangements et nombre de points fixes d'une permutation|dérangements]] parmi ''n'' éléments, à savoir :
* <math>\mathbb P(N=0) = \sum_{k=0}^n \frac{(-1)^k}{k!}</math>
Le cas général <math>\mathbb P(N=r)</math> 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ù :
* <math>\mathbb P(N=r) = \frac1{n!} \binom{n}{r} (n-r)! \sum_{k=0}^{n-r} \frac{(-1)^k}{k!} = \frac1{r!} \sum_{k=0}^{n-r} \frac{(-1)^k}{k!}</math>
''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 [[Loi de Bernoulli|Bernoulli]] <math>X_1 + \cdots + X_n</math>, où <math>X_k</math> prend la valeur 1 si ''k'' est un point fixe. On a <math>\mathbb P(X_k = 1) = \frac1n</math> et <math>\mathbb P(X_j = X_k = 1) = \frac1{n(n-1)}</math> pour ''j'' différent de ''k'', d'où l'on tire :
* <math> \mathbb E(N) = 1</math>
* <math> \mathbb V(N) = 1</math>

=== Nombre de descentes ===
Une descente d'une permutation π, élément de <math>\mathcal S_n</math>, est un indice {{Mvar|i}} entre 1 et {{Mvar|n}}-1 tel que π({{Mvar|i}}+1) < π({{Mvar|i}}). Le nombre de permutations de <math>\mathcal S_n</math> ayant {{Mvar|k}} descentes est, par définition, le [[nombre eulérien]] {{Mvar|A}}({{Mvar|n}},{{Mvar|k}}). 

Si {{Mvar|X}} est la variable aléatoire définie sur <math>\mathcal S_n</math> et qui associe à une permutation son nombre de descentes, alors :
*<math>\mathbb P(X=k) = \frac{A(n,k)}{n!}</math>

Pour {{Mvar|n}}=1, {{Mvar|X}} est la variable certaine 0. 

Pour {{Mvar|n}} supérieur ou égal à 2, on montre que<ref name=KnuthACP>{{ouvrage|titre=The Art of Computer Programming|auteur=Donald Knuth|page=34-45|année=1973|volume=3|isbn=0-201-03803-X}}. Dans cet ouvrage, la valeur de {{Mvar|X}} est décalée d'une unité car D. Knuth compte le nombre de suites croissantes constituées d'images consécutives de la permutation, séparées par {{Mvar|X}}-1 descentes.</ref> :
*<math>\mathbb E(X) = \frac{n-1}{2}</math>
*<math>\mathbb V(X) = \frac{n+1}{12}</math>

Si {{Mvar|S}} est la somme de {{Mvar|n}} variables aléatoires indépendantes suivant chacune une [[loi uniforme continue]] sur [0, 1], {{Mvar|S}} suit une [[loi de Irwin-Hall]], d'espérance <math>\frac{n}{2}</math> et de variance <math>\frac{n}{12}</math>. On [[Loi uniforme continue#Nombres de descentes d'une permutation aléatoire, et nombres eulériens|montre]] que {{Mvar|X}} et la partie entière de {{Mvar|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 [[#Génération par les cycles|vu plus haut]], la variable aléatoire <math>K_n</math> égale au nombre de cycles d'une permutation de {1, ..., ''n''} est égale à <math>X_1 + X_2 + \cdots + X_n</math>, où les <math>X_k</math> sont des [[loi de Bernoulli|variables de Bernoulli]] indépendantes de paramètres <math>\frac1{k}</math>. Il en résulte<ref name=Feller/> immédiatement la valeur de l'espérance et de la variance de <math>K_n</math> :
* <math>\mathbb{E}(K_n) = \sum_{k=1}^n \mathbb{E}(X_k) = \sum_{k=1}^n \frac1{k}</math>
* <math>\mathbb{V}(K_n) = \sum_{k=1}^n \mathbb{V}(X_k) = \sum_{k=1}^n \frac1{k}\left(1 - \frac1{k}\right)</math>

Quant à la loi du nombre de cycles, elle vaut :
* <math>\mathbb{P}(K_n=r) = \frac1{n} \sum_{1 \leq k_1<k_2<\cdots<k_{r-1}\leq n-1} \frac1{k_1 k_2 \cdots k_{r-1}}</math>
et elle vérifie la relation de récurrence :
* <math>\mathbb{P}(K_n=r) = \frac1n \mathbb{P}(K_{n-1}=r-1) + \frac{n-1}{n} \mathbb{P}(K_{n-1}=r)</math>
On peut aussi l'exprimer en fonction des [[Nombre_de_Stirling#Nombre_de_Stirling_de_première_espèce|nombres de Stirling de première espèce]] non signés, notés <math>\left[\begin{matrix}\scriptstyle n \\\scriptstyle k \end{matrix}\right]  </math> :
* <math>\mathbb{P}(K_n=r) = \frac1{n!} \left[\begin{matrix}\scriptstyle n \\\scriptstyle k \end{matrix}\right]</math>

La [[variable centrée réduite]] obtenue à partir de <math>K_n</math> [[Convergence en loi|converge en loi]] vers la [[loi normale#Loi normale centrée réduite|loi normale centrée réduite]]<ref>{{article|auteur=Larry Goldstein|titre=A Probabilistic Proof of the Lindeberg-Feller Central Limit Theorem|périodique=Amer. Math. Monthly|volume=116|numéro=1|année=2009|langue=en|pages=45-60}}</ref>. Autrement dit, le [[théorème central limite]] s'applique à <math>K_n</math>, bien que les <math>X_k</math> ne soient pas de même loi.

La loi du nombre de cycles est identique à celle du [[Loi de Bernoulli#Nombre de records et nombre de cycles des permutations|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 <math>\sigma = (1 5 7 3)(2 6)(4 8)</math>. Écrivons cette permutation en plaçant en dernier dans chaque cycle son élément le plus petit : <math>\sigma = (5 7 3 1)(6 2)(8 4)</math>, et associons à la permutation la liste des nombres lus de gauche à droite <math>[5 7 3 1 6 2 8 4]</math>. 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 <math>Y_n</math> la variable aléatoire telle que, pour tout permutation σ élément de <math>\mathcal S_n</math>, <math>Y_n(\sigma)</math> donne le nombre d'inversions de σ, c'est-à-dire le nombre de couples ({{math|''i''}}, {{math|''j''}}) tels que {{math|''i''}} < {{math|''j''}}, mais que σ({{math|''i''}}) > σ({{math|''j''}}). 

Pour {{math|''j''}} variant de 1 à {{math|''n''}}, notons <math>Z_j</math> la variable aléatoire donnant le nombre d'indices {{math|''i''}} inférieurs à {{math|''j''}} formant une inversion avec {{math|''j''}}. <math>Y_n</math> n'est autre que la somme <math>Z_2 + \cdots + Z_n</math> (<math>Z_1</math> étant nécessairement nul). 

<math>(Z_2, \cdots,Z_n)</math> est à valeurs dans <math>[\![0,1]\!]\times[\![0,2]\!]\times\dots\times[\![0,n-1]\!]</math>, et l'application :
:<math>\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]\!]</math>
est bijective<ref name=Knuth>{{ouvrage|auteur=[[Donald Knuth]]|titre=The art of computer programming|langue=en|tome=III|page=12-16|année=1973|éditeur=Addison-Wesley|isbn=0-201-03803-X}}. Les <math>Z_j</math>forment une variante du [[code de Lehmer]].</ref>. Pour tout {{math|''j''}}, <math>Z_j</math> suit une [[Loi uniforme discrète|loi uniforme]] sur <math>[\![0,j-1]\!]</math>, et ces variables sont indépendantes. On a <math>\mathbb E(Z_j) = \frac{j-1}{2}</math> et <math>\mathbb V(Z_j) = \frac{j^2-1}{12}</math>. D'où l'on déduit<ref name=Knuth/>{{,}}<ref name=Feller/> :
* <math>\mathbb E(Y_n) = \frac{(n-1)n}{4}</math>
* <math>\mathbb V(Y_n) = \frac{(n-1)n(2n+5)}{72}</math>
La loi de <math>Y_n</math> n'est pas exprimable simplement, mais on peut utiliser le fait que <math>Y_{n-1}</math> a même loi que <math>(Z_2, \cdots,Z_{n-1})</math> pour en déduire que <math>Y_n</math> a même loi que <math>Y_{n-1} + Z_n</math>, ces deux variables étant indépendantes. Il en résulte une définition récursive des lois<ref>Voir aussi la {{OEIS|A008302}}.</ref> :
*<math>\mathbb P(Y_n=k) = \frac1n \sum_{j={\rm max}(0,k-n+1)}^k \mathbb P(Y_{n-1} = j)</math>
Enfin, <math>Y_n</math> étant la somme des variables aléatoires indépendantes <math>Z_j</math>, sa [[Fonction génératrice des probabilités|fonction génératrice]] <math>G_{Y_n}</math> est le produit des fonctions génératrices des <math>Z_j</math><ref name=Knuth/> :
* <math>G_{Y_n}(z) = \frac{\prod_{j=1}^n (1-z^j)}{n! (1-z)^n}</math>

Lorsque ''n'' tend vers l'infini, la variable centrée réduite déduite de <math>Y_n</math> [[convergence en loi|converge en loi]] vers la [[Loi normale#Loi normale centrée réduite|loi normale centrée réduite]]<ref>Le plus simple pour le montrer est d'utiliser la [[Théorème central limite#Condition de Lindeberg|condition de Lindeberg]] du théorème central limite.</ref>.

=== Longueur des cycles ===
En attendant le développement de cette section, on pourra se reporter aux pages suivantes
* [[Loi de Bernoulli#Nombre de records et nombre de cycles des permutations|Nombre de records et nombre de cycles d'une permutation]],
* [[Correspondance fondamentale de Foata]], en particulier à la section [[Correspondance fondamentale de Foata#Stick-breaking process et processus de Poisson-Dirichlet|Stick-breaking process et processus de Poisson-Dirichlet]],
* [[Code de Lehmer]],
* [[Nombre de Stirling]].

== Notes et références ==
{{références}}

{{Portail|probabilités|informatique théorique}}

[[Catégorie:Variable aléatoire]]
[[Catégorie:Permutation|Aleatoire]]