36
2 Marches aléatoires
Au temps T 1 , la carte r se trouve pour la première fois en position r−1, car
la carte numéro 1 a été glissée sous le paquet. Au temps T 1 + T 2 , la carte r se
trouve pour la première fois en position r−2 car la carte numéro 2 a été glissée
sous ou sur la carte 1. Les numéros des deux cartes sous le paquet sont 1, 2 ou
2, 1 avec probabilité 1/2. Par récurrence, au temps T 1 + · · · + T r−1 = T − 1, la
carte r se trouve au sommet du paquet pour la première fois et les r − 1 cartes
qui sont sous elle ont des numéros répartis uniformément sans remise dans
{1, . . . , r−1}. Au temps T , la carte r est placée aléatoirement et uniformément
dans le paquet à une position entre 1 et r et donc X T suit la loi uniforme.
Comme la probabilité P(X T = σ, T = k) ne dépend pas de σ, on en déduit
que T et X T sont indépendantes. Or comme la loi μ est invariante, on obtient
X T +n ∼ μ pour tout n 0.
Pour bien mélanger le paquet de cartes, on pourrait s’arrêter au temps
T . Malheureusement, on ne connaît pas T en pratique ! Alternativement, on
pourrait chercher à déterminer une valeur de n, aussi petite que possible,
telle que d VT (Loi(X n ), μ) est proche de zéro, où d VT (·, ·) est la distance en
variation totale (section 1.3). Il s’avère que pour r assez grand, la quantité
d VT (Loi(X n ), μ) passe de 1 à 0 de manière abrupte
6 autour de n = r log(r).
Ce phénomène de convergence abrupte est quantifié par le théorème suivant.
Théorème 2.12 (Convergence abrupte en n = r log(r)). Pour tout réel c > 0,
d VT
Loi(X r log(r)+cr ), μ
e
−c+εr
avec 0 ε r < 1/r.
Si c r 0 vérifie lim r→∞ c r = ∞ et r log(r) − rc r > 0 pour tout r 1, alors
lim
r→∞
d VT
Loi(X r log(r)−rcr ), μ
= 1.
Démonstration. Grâce au théorème 2.11, on a, pour tout A ⊂ Σ r ,
P(X n ∈ A) =
n
k=0
P(X n ∈ A, T = k) + P(X n = σ, T > n)
n
k=0
P(X n ∈ A, T = k) + P(T > n)
=
n
k=0
P(X T +n−k ∈ A, T = k) + P(T > n)
=
n
k=0
μ(A)P(T = k) + P(T > n)
= μ(A)P(T n) + P(T > n)
μ(A) + P(T > n).
6. On parle de «cutoff phenomenon» en anglais.
2 Marches aléatoires
Au temps T 1 , la carte r se trouve pour la première fois en position r−1, car
la carte numéro 1 a été glissée sous le paquet. Au temps T 1 + T 2 , la carte r se
trouve pour la première fois en position r−2 car la carte numéro 2 a été glissée
sous ou sur la carte 1. Les numéros des deux cartes sous le paquet sont 1, 2 ou
2, 1 avec probabilité 1/2. Par récurrence, au temps T 1 + · · · + T r−1 = T − 1, la
carte r se trouve au sommet du paquet pour la première fois et les r − 1 cartes
qui sont sous elle ont des numéros répartis uniformément sans remise dans
{1, . . . , r−1}. Au temps T , la carte r est placée aléatoirement et uniformément
dans le paquet à une position entre 1 et r et donc X T suit la loi uniforme.
Comme la probabilité P(X T = σ, T = k) ne dépend pas de σ, on en déduit
que T et X T sont indépendantes. Or comme la loi μ est invariante, on obtient
X T +n ∼ μ pour tout n 0.
Pour bien mélanger le paquet de cartes, on pourrait s’arrêter au temps
T . Malheureusement, on ne connaît pas T en pratique ! Alternativement, on
pourrait chercher à déterminer une valeur de n, aussi petite que possible,
telle que d VT (Loi(X n ), μ) est proche de zéro, où d VT (·, ·) est la distance en
variation totale (section 1.3). Il s’avère que pour r assez grand, la quantité
d VT (Loi(X n ), μ) passe de 1 à 0 de manière abrupte
6 autour de n = r log(r).
Ce phénomène de convergence abrupte est quantifié par le théorème suivant.
Théorème 2.12 (Convergence abrupte en n = r log(r)). Pour tout réel c > 0,
d VT
Loi(X r log(r)+cr ), μ
e
−c+εr
avec 0 ε r < 1/r.
Si c r 0 vérifie lim r→∞ c r = ∞ et r log(r) − rc r > 0 pour tout r 1, alors
lim
r→∞
d VT
Loi(X r log(r)−rcr ), μ
= 1.
Démonstration. Grâce au théorème 2.11, on a, pour tout A ⊂ Σ r ,
P(X n ∈ A) =
n
k=0
P(X n ∈ A, T = k) + P(X n = σ, T > n)
n
k=0
P(X n ∈ A, T = k) + P(T > n)
=
n
k=0
P(X T +n−k ∈ A, T = k) + P(T > n)
=
n
k=0
μ(A)P(T = k) + P(T > n)
= μ(A)P(T n) + P(T > n)
μ(A) + P(T > n).
6. On parle de «cutoff phenomenon» en anglais.