Permutation aléatoire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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é sur les permutations aléatoires, par exemple, le nombre moyen de points fixes ou la longueur des cycles. Plusieurs algorithme existent pour générer des permutations aléatoire à partir d'un générateur de nombres aléatoires, par exemple le mélange de Fisher–Yates (en).

Propriétés des permutations aléatoires[modifier | modifier le code]

Nombre de points fixes[modifier | modifier le code]

En attendant le développement de cette section, se reporter aux sections

Nombre de descentes[modifier | modifier le code]

En attendant le développement de cette section, se reporter aux sections

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 et longueurs des cycles[modifier | modifier le code]

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

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 \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\le i\le n,\ \mathrm{et~tels~que}\ X_{i}(\omega)\le 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[modifier | modifier le code]

Le mélange de Fisher–Yates (en), é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]

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