Permutation aléatoire - Random permutation

Une permutation aléatoire est un ordre aléatoire d'un ensemble d'objets, c'est-à-dire une variable aléatoire à valeur de permutation . L'utilisation de permutations aléatoires est souvent fondamentale dans les domaines qui utilisent des algorithmes aléatoires tels que la théorie du codage , la cryptographie et la simulation . Un bon exemple de permutation aléatoire est le brassage d'un jeu de cartes : il s'agit idéalement d'une permutation aléatoire des 52 cartes.

Générer des permutations aléatoires

Méthode de force brute entrée par entrée

Une méthode pour générer une permutation aléatoire d'un ensemble de longueur n uniformément au hasard (c'est-à-dire que chacune des n ! permutations est également susceptible d'apparaître) consiste à générer une séquence en prenant un nombre aléatoire entre 1 et n de manière séquentielle, en n'y a pas de répétition, et en interprétant cette séquence ( x ₁ , ..., x _n ) comme la permutation

${\displaystyle {\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}},}$

représenté ici en notation sur deux lignes .

Cette méthode de force brute nécessitera des tentatives occasionnelles chaque fois que le nombre aléatoire choisi est une répétition d'un nombre déjà sélectionné. Ceci peut être évité si, à la i ème étape (lorsque x ₁ , ..., x _{i - 1} ont déjà été choisi), on choisit un nombre j au hasard entre 1 et n - i + 1 et ensembles ix _i égal au j ème plus grand des nombres non choisis.

Mélanges Fisher-Yates

Un algorithme simple pour générer une permutation de n éléments uniformément au hasard sans réessais, connu sous le nom de Fisher-Yates shuffle , consiste à commencer par n'importe quelle permutation (par exemple, la permutation d'identité ), puis à parcourir les positions 0 à n − 2 (on utilise une convention dans laquelle le premier élément a l' indice 0, et le dernier élément a l' indice n - 1), et pour chaque position i échanger l'élément actuellement là avec un élément choisi au hasard à partir de positions i par n - 1 (fin) , inclus. Il est facile de vérifier que toute permutation de n éléments sera produite par cet algorithme avec une probabilité exactement 1/ n !, donnant ainsi une distribution uniforme sur toutes ces permutations.

unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m-1 with uniform distribution */

void initialize_and_permute(unsigned permutation[], unsigned n)
{
    unsigned i;
    for (i = 0; i <= n-2; i++) {
        unsigned j = i+uniform(n-i); /* A random integer such that i ≤ j < n */
        swap(permutation[i], permutation[j]);   /* Swap the randomly picked element with permutation[i] */
    }
}

Notez que si la uniform()fonction est implémentée simplement comme random() % (m)alors un biais dans les résultats est introduit si le nombre de valeurs de retour de random()n'est pas un multiple de m, mais cela devient insignifiant si le nombre de valeurs de retour de random()est des ordres de grandeur supérieur à m.

Statistiques sur les permutations aléatoires

Points fixes

La distribution de probabilité du nombre de points fixes dans une permutation aléatoire uniformément distribuée s'approche d'une distribution de Poisson avec la valeur attendue 1 à mesure que n augmente. En particulier, c'est une application élégante du principe d' inclusion-exclusion pour montrer que la probabilité qu'il n'y ait pas de points fixes approche 1/ e . Lorsque n est suffisamment grand, la distribution de probabilité des points fixes est presque la distribution de Poisson d' espérance 1. Les n premiers moments de cette distribution sont exactement ceux de la distribution de Poisson.

Tests aléatoires

Comme pour tous les processus aléatoires, la qualité de la distribution résultante d'une implémentation d'un algorithme aléatoire tel que le mélange de Knuth (c'est-à-dire à quel point il est proche de la distribution uniforme souhaitée) dépend de la qualité de la source sous-jacente du caractère aléatoire, telle que un générateur de nombres pseudo-aléatoires . Il existe de nombreux tests aléatoires possibles pour les permutations aléatoires, tels que certains des tests Diehard . Un exemple typique d'un tel test consiste à prendre une statistique de permutation dont la distribution est connue et à tester si la distribution de cette statistique sur un ensemble de permutations générées aléatoirement se rapproche étroitement de la vraie distribution.

Voir également

• La formule d'échantillonnage d'Ewens — un lien avec la génétique des populations
• Faro shuffle
• Constante de Golomb–Dickman
• Statistiques de permutation aléatoire
• Algorithmes de brassage — méthode de tri aléatoire, méthode d'échange itérative

Les références

Liens externes

• Permutation aléatoire à MathWorld
• Génération de permutation aléatoire -- explication détaillée et pratique de l'algorithme de mélange de Knuth et de ses variantes pour générer des k -permutations (permutations de k éléments choisis dans une liste) et des k -sous-ensembles (générer un sous-ensemble des éléments de la liste sans remplacement) avec pseudocode