4.2 Permutations aléatoires
59
Un algorithme naïf pour simuler une permutation σ uniforme consiste à tirer uniformément et sans remise les valeurs de σ(1), . . . , σ(n) dans {1, . . . , n}.
Cet algorithme d’apparence séduisante a une complexité plus élevée que celui du tri, car il faut tenir compte dans l’implémentation des éléments déjà
tirés. Un bon algorithme de simulation (exacte !) de la loi uniforme sur S n est
connu sous le nom d’algorithme de Fisher-Yates-Knuth
4 . Il nécessite n − 1
variables aléatoires indépendantes de loi uniforme sur {1, 2}, . . . , {1, 2, . . . , n}
respectivement, soit de l’ordre de
n
k=2 log(k) = log(n!) ≈ n log(n) bits i.i.d.
Théorème 4.1 (Permutations et algorithme de Fisher-Yates-Knuth). Si
U 1 , . . . , U n sont des variables aléatoires indépendantes avec U i de loi uniforme
sur {1, . . . , i} pour tout 1 i n alors la permutation formée par le produit
de transpositions aléatoires (1, U 1 ) · · · (n, U n ) suit la loi uniforme sur S n .
L’inversion dans S n étant bijective, et les transpositions étant leur propre
inverse, il en découle que le produit renversé (n, U n ) · · · (1, U 1 ) suit également
la loi uniforme sur S n . La transposition (1, U 1 ) est triviale (élément neutre de
S n ) et il n’est pas nécessaire d’en tenir compte si n 2 (elle rend cependant
la formule valable pour n = 1). L’algorithme de Fisher-Yates-Knuth pour
permuter un vecteur v s’écrit en pseudo-code :
for k from length(v) downto 2 do
swap(v[ceil(k*rand)],v[k])
Démonstration du théorème 4.1. On procède par récurrence sur n. La propriété est triviale pour n = 1. Supposons qu’elle est vraie pour n 1. Pour
tout σ ∈ S n , on note encore σ l’élément de S n+1 obtenu à partir de σ en
ajoutant le cycle (n + 1) (point fixe). Supposons que σ n = (1, U 1 ) · · · (n, U n )
suit la loi uniforme sur S n . Soit U n+1 une variable aléatoire indépendante de
σ n , de loi uniforme sur {1, . . . , n + 1}. Montrons que σ n+1 = σ n (n + 1, U n+1 )
suit la loi uniforme sur S n+1 . Pour tout σ ∈ S n+1 , on a
P(σ n+1 = σ) =
n+1
i=1
P(σ n = σ(n + 1, i))P(U n+1 = i)
=
1
n + 1
n+1
i=1
P(σ n = σ(n + 1, i)).
Comme n + 1 est point fixe de σ n , et n’est point fixe de σ(n + 1, i) que pour
une et une seule valeur de i, notée i σ , image réciproque de n + 1 par σ, il en
découle finalement que
P(σ n+1 = σ) =
1
n + 1
P(σ n = σ(n + 1, i σ )) =
1
n + 1
1
n!
=
1
(n + 1)!
.
4. «Fisher-Yates shuffle» ou «Knuth shuffle» en anglais.
59
Un algorithme naïf pour simuler une permutation σ uniforme consiste à tirer uniformément et sans remise les valeurs de σ(1), . . . , σ(n) dans {1, . . . , n}.
Cet algorithme d’apparence séduisante a une complexité plus élevée que celui du tri, car il faut tenir compte dans l’implémentation des éléments déjà
tirés. Un bon algorithme de simulation (exacte !) de la loi uniforme sur S n est
connu sous le nom d’algorithme de Fisher-Yates-Knuth
4 . Il nécessite n − 1
variables aléatoires indépendantes de loi uniforme sur {1, 2}, . . . , {1, 2, . . . , n}
respectivement, soit de l’ordre de
n
k=2 log(k) = log(n!) ≈ n log(n) bits i.i.d.
Théorème 4.1 (Permutations et algorithme de Fisher-Yates-Knuth). Si
U 1 , . . . , U n sont des variables aléatoires indépendantes avec U i de loi uniforme
sur {1, . . . , i} pour tout 1 i n alors la permutation formée par le produit
de transpositions aléatoires (1, U 1 ) · · · (n, U n ) suit la loi uniforme sur S n .
L’inversion dans S n étant bijective, et les transpositions étant leur propre
inverse, il en découle que le produit renversé (n, U n ) · · · (1, U 1 ) suit également
la loi uniforme sur S n . La transposition (1, U 1 ) est triviale (élément neutre de
S n ) et il n’est pas nécessaire d’en tenir compte si n 2 (elle rend cependant
la formule valable pour n = 1). L’algorithme de Fisher-Yates-Knuth pour
permuter un vecteur v s’écrit en pseudo-code :
for k from length(v) downto 2 do
swap(v[ceil(k*rand)],v[k])
Démonstration du théorème 4.1. On procède par récurrence sur n. La propriété est triviale pour n = 1. Supposons qu’elle est vraie pour n 1. Pour
tout σ ∈ S n , on note encore σ l’élément de S n+1 obtenu à partir de σ en
ajoutant le cycle (n + 1) (point fixe). Supposons que σ n = (1, U 1 ) · · · (n, U n )
suit la loi uniforme sur S n . Soit U n+1 une variable aléatoire indépendante de
σ n , de loi uniforme sur {1, . . . , n + 1}. Montrons que σ n+1 = σ n (n + 1, U n+1 )
suit la loi uniforme sur S n+1 . Pour tout σ ∈ S n+1 , on a
P(σ n+1 = σ) =
n+1
i=1
P(σ n = σ(n + 1, i))P(U n+1 = i)
=
1
n + 1
n+1
i=1
P(σ n = σ(n + 1, i)).
Comme n + 1 est point fixe de σ n , et n’est point fixe de σ(n + 1, i) que pour
une et une seule valeur de i, notée i σ , image réciproque de n + 1 par σ, il en
découle finalement que
P(σ n+1 = σ) =
1
n + 1
P(σ n = σ(n + 1, i σ )) =
1
n + 1
1
n!
=
1
(n + 1)!
.
4. «Fisher-Yates shuffle» ou «Knuth shuffle» en anglais.