Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Permutation aléatoire
Résumé
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.
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.
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.
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]
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.