34
2 Marches aléatoires
2.4 Marche aléatoire sur le groupe symétrique
On considère r 2 cartes à jouer empilées en un paquet vertical, et numérotées de 1 à r. On dit que la carte du dessus est en position 1, etc et que
celle du dessous est en position r. On étudie un battage de cartes très simple
pour mélanger le paquet de cartes, appelé «top to random shuffle» en anglais.
Plus précisément, on considère la k-insertion qui consiste à prendre la carte du
sommet du paquet et à l’insérer entre la k
e et k + 1
e positions. La 1-insertion
n’a aucun effet. On convient que la r-insertion place la carte du sommet sous
le paquet. On choisit d’effectuer des k-insertions successives en utilisant une
suite i.i.d. uniforme sur {1, . . . , r} pour choisir k.
Une configuration du paquet est codée par un élément σ du groupe symétrique Σ r , de sorte que σ(k) désigne la position de la carte numéro k. Une
k-insertion fait passer de la configuration σ à la configuration (k, k−1, . . . , 1)σ
où (k, k − 1, . . . , 1) ∈ S r désigne le k-cycle k → k − 1 → · · · → 1 → k.
En notant X n la configuration du paquet à l’instant n, on obtient une
suite aléatoire (X n ) n0 de Σ r vérifiant pour tout n 0,
X n+1 = ε n+1 X n = ε n+1 · · · ε 1 X 0
où (ε n ) n1 sont i.i.d. de loi uniforme sur C := {(k, k − 1, . . . , 1) : 1 k
r} ⊂ Σ r . La suite (X n ) n0 est une marche aléatoire à gauche sur le groupe
(non abélien) Σ r , d’incréments C. C’est aussi une chaîne de Markov d’espace
d’états fini Σ r (de cardinal r!) et de noyau
P(σ, σ
) =
1 C (σ
σ
−1 )
|C|
=
1 C (σ
σ
−1 )
r
.
1
σ
−1 (1)
. . .
. . .
r
σ
−1 (r)
Configuration initiale Configuration après mélange
Fig. 2.4. La carte en position k se déplace en position σ(k).
Théorème 2.10 (Convergence en loi). La chaîne (X n ) n0 est récurrente
irréductible apériodique. Son unique loi invariante est la loi uniforme sur Σ r :
μ =
σ∈Σr
1
|Σ r |
δ σ =
1
r!
σ∈Σr
δ σ .
La chaîne (X n ) n0 converge en loi vers μ quelle que soit la loi initiale Loi(X 0 ).
2 Marches aléatoires
2.4 Marche aléatoire sur le groupe symétrique
On considère r 2 cartes à jouer empilées en un paquet vertical, et numérotées de 1 à r. On dit que la carte du dessus est en position 1, etc et que
celle du dessous est en position r. On étudie un battage de cartes très simple
pour mélanger le paquet de cartes, appelé «top to random shuffle» en anglais.
Plus précisément, on considère la k-insertion qui consiste à prendre la carte du
sommet du paquet et à l’insérer entre la k
e et k + 1
e positions. La 1-insertion
n’a aucun effet. On convient que la r-insertion place la carte du sommet sous
le paquet. On choisit d’effectuer des k-insertions successives en utilisant une
suite i.i.d. uniforme sur {1, . . . , r} pour choisir k.
Une configuration du paquet est codée par un élément σ du groupe symétrique Σ r , de sorte que σ(k) désigne la position de la carte numéro k. Une
k-insertion fait passer de la configuration σ à la configuration (k, k−1, . . . , 1)σ
où (k, k − 1, . . . , 1) ∈ S r désigne le k-cycle k → k − 1 → · · · → 1 → k.
En notant X n la configuration du paquet à l’instant n, on obtient une
suite aléatoire (X n ) n0 de Σ r vérifiant pour tout n 0,
X n+1 = ε n+1 X n = ε n+1 · · · ε 1 X 0
où (ε n ) n1 sont i.i.d. de loi uniforme sur C := {(k, k − 1, . . . , 1) : 1 k
r} ⊂ Σ r . La suite (X n ) n0 est une marche aléatoire à gauche sur le groupe
(non abélien) Σ r , d’incréments C. C’est aussi une chaîne de Markov d’espace
d’états fini Σ r (de cardinal r!) et de noyau
P(σ, σ
) =
1 C (σ
σ
−1 )
|C|
=
1 C (σ
σ
−1 )
r
.
1
σ
−1 (1)
. . .
. . .
r
σ
−1 (r)
Configuration initiale Configuration après mélange
Fig. 2.4. La carte en position k se déplace en position σ(k).
Théorème 2.10 (Convergence en loi). La chaîne (X n ) n0 est récurrente
irréductible apériodique. Son unique loi invariante est la loi uniforme sur Σ r :
μ =
σ∈Σr
1
|Σ r |
δ σ =
1
r!
σ∈Σr
δ σ .
La chaîne (X n ) n0 converge en loi vers μ quelle que soit la loi initiale Loi(X 0 ).