2.4 Marche aléatoire sur le groupe symétrique
35
Démonstration. L’ensemble de transpositions spécial
T := {(r, r − 1), . . . , (2, 1), (1, r)}
engendre Σ r . Comme les k-insertions (r, r − 1, . . . , 1) et (2, 1) correspondant à
k = r et à k = 2 engendrent T , on en déduit qu’elles engendrent Σ r . Donc C
engendre Σ r et la chaîne est irréductible. Comme l’identité (1) est également
une k-insertion (k = 1), la diagonale de la matrice de transition de la chaîne
est > 0 et donc la chaîne est apériodique. Comme Σ r est un groupe, il y
a exactement r états qui conduisent à chaque état, donc les colonnes de la
matrice de transition ont exactement r entrées non nulles, toutes égales à 1/r.
Ainsi, la transposée de la matrice de transition est également une matrice
de transition
5 et donc la loi uniforme est invariante. Or toute chaîne finie
récurrente apériodique possède une unique loi invariante vers laquelle elle
converge en loi quelle que soit sa loi initiale.
On souhaite à présent étudier la vitesse de convergence de la chaîne vers sa
loi invariante, partant d’une configuration initiale X 0 fixée. Par invariance par
translation, on peut supposer que X 0 = (1), c’est-à-dire que toutes les cartes
sont dans l’ordre au départ. Au temps 0 la carte r est en position r (tout
en bas du paquet), et subit une remontée pas à pas au fil du temps jusqu’au
sommet. Cette remontée est de plus en plus rapide. Pour tout 1 k r − 1,
on note T k le temps que cette carte passe en position r − k (et T 0 = 0). Pour
tout k 1, on a, avec la convention T 1 + · · · + T k−1 = 0 si k = 1,
T k = min{n 1 : X T1+···+T k−1 +n = r − k}
= min{n 1 : X n (r) = r − k} − (T 1 + · · · + T k−1 ).
Au temps T 1 + · · · + T r−1 la carte r est en position 1 (sommet du paquet). La
variable aléatoire
T := 1 + T 1 + · · · + T r−1
suit la loi du collectionneur de coupons de r coupons de probabilité d’apparition uniforme (chapitre 1). Les variables aléatoires T 1 , . . . , T r−1 sont indépendantes avec T k ∼ Geo(k/r) pour tout 1 k r − 1. Notons que T r.
Théorème 2.11 (Bon mélange après remontée). Le temps T est un temps
fort de stationnarité : pour tout n 0, les variables aléatoires X T +n et T sont
indépendantes et de plus X T +n suit la loi uniforme μ sur Σ r .
Démonstration. La loi uniforme sur Σ r peut s’obtenir en tirant uniformément
sans remise les images de 1, . . . , r. D’autre part, la loi uniforme sur Σ r est
invariante par translation.
5. Elle est doublement stochastique (ou bistochastique). L’ensemble des matrices
doublement stochastiques n × n est un polytope (intersection de demi-espaces)
convexe et compact à (n − 1)
2 degrés de liberté. Ses points extrémaux sont les
matrices de permutations (Birkhoff et von Neumann). Encore le groupe symétrique !
35
Démonstration. L’ensemble de transpositions spécial
T := {(r, r − 1), . . . , (2, 1), (1, r)}
engendre Σ r . Comme les k-insertions (r, r − 1, . . . , 1) et (2, 1) correspondant à
k = r et à k = 2 engendrent T , on en déduit qu’elles engendrent Σ r . Donc C
engendre Σ r et la chaîne est irréductible. Comme l’identité (1) est également
une k-insertion (k = 1), la diagonale de la matrice de transition de la chaîne
est > 0 et donc la chaîne est apériodique. Comme Σ r est un groupe, il y
a exactement r états qui conduisent à chaque état, donc les colonnes de la
matrice de transition ont exactement r entrées non nulles, toutes égales à 1/r.
Ainsi, la transposée de la matrice de transition est également une matrice
de transition
5 et donc la loi uniforme est invariante. Or toute chaîne finie
récurrente apériodique possède une unique loi invariante vers laquelle elle
converge en loi quelle que soit sa loi initiale.
On souhaite à présent étudier la vitesse de convergence de la chaîne vers sa
loi invariante, partant d’une configuration initiale X 0 fixée. Par invariance par
translation, on peut supposer que X 0 = (1), c’est-à-dire que toutes les cartes
sont dans l’ordre au départ. Au temps 0 la carte r est en position r (tout
en bas du paquet), et subit une remontée pas à pas au fil du temps jusqu’au
sommet. Cette remontée est de plus en plus rapide. Pour tout 1 k r − 1,
on note T k le temps que cette carte passe en position r − k (et T 0 = 0). Pour
tout k 1, on a, avec la convention T 1 + · · · + T k−1 = 0 si k = 1,
T k = min{n 1 : X T1+···+T k−1 +n = r − k}
= min{n 1 : X n (r) = r − k} − (T 1 + · · · + T k−1 ).
Au temps T 1 + · · · + T r−1 la carte r est en position 1 (sommet du paquet). La
variable aléatoire
T := 1 + T 1 + · · · + T r−1
suit la loi du collectionneur de coupons de r coupons de probabilité d’apparition uniforme (chapitre 1). Les variables aléatoires T 1 , . . . , T r−1 sont indépendantes avec T k ∼ Geo(k/r) pour tout 1 k r − 1. Notons que T r.
Théorème 2.11 (Bon mélange après remontée). Le temps T est un temps
fort de stationnarité : pour tout n 0, les variables aléatoires X T +n et T sont
indépendantes et de plus X T +n suit la loi uniforme μ sur Σ r .
Démonstration. La loi uniforme sur Σ r peut s’obtenir en tirant uniformément
sans remise les images de 1, . . . , r. D’autre part, la loi uniforme sur Σ r est
invariante par translation.
5. Elle est doublement stochastique (ou bistochastique). L’ensemble des matrices
doublement stochastiques n × n est un polytope (intersection de demi-espaces)
convexe et compact à (n − 1)
2 degrés de liberté. Ses points extrémaux sont les
matrices de permutations (Birkhoff et von Neumann). Encore le groupe symétrique !