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.

Par exemple pour N=5, nous pouvons obtenir (15423) ou encore (34125).


Les permutations aléatoires peuvent être mises en relation avec un processus de Poisson de N points sur le carré.


On peut s'intéresser au nombre de points fixes d'une permutation aléatoire, ainsi qu'à la plus longue sous-suite croissante.

Sommaire

Nombre de points fixes

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

Nombre de descentes

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

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 et longueurs des cycles

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

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\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

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 0 à n-1
   j := nombre aléatoire entre 0 et i (inclus)
   si i ≠ j, alors échanger T[i] et T[j]
  • Portail des probabilités et des statistiques Portail des probabilités et des statistiques

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Permutation aléatoire de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Permutation aleatoire — 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. Par exemple pour N=5, nous pouvons obtenir (15423) ou encore (34125). Les permutations… …   Wikipédia en Français

  • Permutation — En mathématiques, la notion de permutation exprime l idée de réarrangement d objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un changement de l ordre de succession de ces n objets. La… …   Wikipédia en Français

  • Matrice De Permutation — Une matrice de permutation est une matrice carrée qui vérifie les propriétes suivantes : les coefficients sont 0 ou 1 ; il y a un et un seul 1 par ligne ; il y a un et un seul 1 par colonne. Ainsi : est une matrice de… …   Wikipédia en Français

  • Matrice de permutation — Une matrice de permutation est une matrice carrée qui vérifie les propriétes suivantes : les coefficients sont 0 ou 1 ; il y a un et un seul 1 par ligne ; il y a un et un seul 1 par colonne. Ainsi : est une matrice de… …   Wikipédia en Français

  • Générateur aléatoire — Générateur de nombres aléatoires Pour les articles homonymes, voir GNA. Un générateur de nombres aléatoires, random number generator (RNG) en anglais, est un dispositif capable de produire une séquence de nombres dont on ne peut pas… …   Wikipédia en Français

  • Reseau de substitution-permutation — Réseau de substitution permutation En cryptographie, un réseau de permutation substitution (SPN en anglais) est une architecture utilisée dans les chiffrements par bloc comme AES. Elle consiste en une série de transformations mathématiques sur le …   Wikipédia en Français

  • Réseau de substitution permutation — En cryptographie, un réseau de permutation substitution (SPN en anglais) est une architecture utilisée dans les chiffrements par bloc comme AES. Elle consiste en une série de transformations mathématiques sur le bloc en clair en entrée pour… …   Wikipédia en Français

  • Matrice Aléatoire — Une matrice aléatoire est une matrice dont les éléments sont des variables aléatoires. Face à la complexité croissante des spectres nucléaires observés expérimentalement dans les années 1950, Wigner a suggeré de remplacer l opérateur hamiltonien… …   Wikipédia en Français

  • Matrice aleatoire — Matrice aléatoire Une matrice aléatoire est une matrice dont les éléments sont des variables aléatoires. Face à la complexité croissante des spectres nucléaires observés expérimentalement dans les années 1950, Wigner a suggeré de remplacer l… …   Wikipédia en Français

  • Matrice aléatoire —  Ne pas confondre avec la notion de matrice stochastique. Une matrice aléatoire est une matrice dont les éléments sont des variables aléatoires. Face à la complexité croissante des spectres nucléaires observés expérimentalement dans les… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”