Permutation aléatoire

Un article de Wikipédia, l'encyclopédie libre.

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[modifier | modifier le code]

Génération à l'aide de variables aléatoires à densité[modifier | modifier le code]

Soit une suite de variables aléatoires i.i.d. à densité, définies sur un espace probabilisé Pour tout entier k compris entre 1 et n, posons

Ainsi, s'interprète comme le rang de dans l'échantillon, une fois celui-ci rangé dans l'ordre croissant.

Proposition —  L'application 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 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[modifier | modifier le code]

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[modifier | modifier le code]

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 de paramètre pour terminer l'étape i et passer à l'étape suivante :

  • Si la variable aléatoire prend la valeur 1 (avec donc la probabilité ), 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 , 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 , égal au nombre de fois où l'on a fermé un cycle, les étant indépendantes[1].

Variables aléatoires portant sur les permutations[modifier | modifier le code]

Nombre de points fixes[modifier | modifier le code]

Soit N la variable aléatoire donnant le nombre de points fixes d'une permutation tirée au hasard dans le groupe symétrique .

La probabilité n'est autre que le quotient par n! du nombre de dérangements parmi n éléments, à savoir :

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

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 , où prend la valeur 1 si k est un point fixe. On a et pour j différent de k, d'où l'on tire :

Nombre de descentes[modifier | modifier le code]

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

Si X est la variable aléatoire définie sur et qui associe à une permutation son nombre de descentes, alors :

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

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

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 et de variance . On montre que X et la partie entière de S suivent la même loi de probabilité.

Plus longue sous-suite croissante[modifier | modifier le code]

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[modifier | modifier le code]

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

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

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

On peut aussi l'exprimer en fonction des nombres de Stirling de première espèce non signés, notés  :

La variable centrée réduite obtenue à partir de converge en loi vers la loi normale centrée réduite[3]. Autrement dit, le théorème central limite s'applique à , bien que les 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 . Écrivons cette permutation en plaçant en dernier dans chaque cycle son élément le plus petit : , et associons à la permutation la liste des nombres lus de gauche à droite . 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[modifier | modifier le code]

Soit la variable aléatoire telle que, pour tout permutation σ élément de , 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 la variable aléatoire donnant le nombre d'indices i inférieurs à j formant une inversion avec j. n'est autre que la somme ( étant nécessairement nul).

est à valeurs dans , et l'application :

est bijective[4]. Pour tout j, suit une loi uniforme sur , et ces variables sont indépendantes. On a et . D'où l'on déduit[4],[1] :

La loi de n'est pas exprimable simplement, mais on peut utiliser le fait que a même loi que pour en déduire que a même loi que , ces deux variables étant indépendantes. Il en résulte une définition récursive des lois[5] :

Enfin, étant la somme des variables aléatoires indépendantes , sa fonction génératrice est le produit des fonctions génératrices des [4] :

Lorsque n tend vers l'infini, la variable centrée réduite déduite de converge en loi vers la loi normale centrée réduite[6].

Longueur des cycles[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. a b et c (en) W. Feller, « The fundamental limit theorems in probability », Bull. Amer. Math. Soc, vol. 51, no 11,‎ , p. 800-832 (lire en ligne)
  2. Donald Knuth, The Art of Computer Programming, vol. 3, (ISBN 0-201-03803-X), p. 34-45. Dans cet ouvrage, la valeur de 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 X-1 descentes.
  3. (en) Larry Goldstein, « A Probabilistic Proof of the Lindeberg-Feller Central Limit Theorem », Amer. Math. Monthly, vol. 116, no 1,‎ , p. 45-60
  4. a b et c (en) Donald Knuth, The art of computer programming, t. III, Addison-Wesley, (ISBN 0-201-03803-X), p. 12-16. Les forment une variante du code de Lehmer.
  5. Voir aussi la suite A008302 de l'OEIS.
  6. Le plus simple pour le montrer est d'utiliser la condition de Lindeberg du théorème central limite.