9.1 Modèle microscopique
117
À présent, pour contrôler la queue de distribution de T d , on observe tout
d’abord que T d coïncide avec le premier instant où toutes les coordonnées
dans I := {i ∈ {1, . . . , a} : x i = x
i } ont été mises à jour au moins une fois. On
a card(I) = d. Supposons pour simplifier la notation que I = {1, . . . , d}. Si les
variables aléatoires (τ i ) 1횿i횿d désignent les temps successifs de modification
d’une nouvelle coordonnée alors T d = τ d et les variables aléatoires (G i ) 1id
définies par G 1 = 1 et G i = τ i − τ i−1 pour 2 i d sont indépendantes et
de lois géométriques de paramètres respectifs (d + 1 − i)/d. On retrouve ici le
collectionneur de coupons de la section 1.5. Il ne reste plus qu’à observer que
P(T d > n) croît en d, et atteint son maximum pour d = a, ce qui revient à
prendre x = (0, . . . , 0) et x
= (1, . . . , 1).
Le théorème 1.14 assure que pour tout réel c 0,
P(T a a log(a) + ca) e
−c+1/a .
Le théorème suivant raffine cette estimation de max x∈F d VT (R
n (x, ·), π).
Théorème 9.4 (Temps long). Si
n =
a log(a)
2
+ ca avec c 0
alors
max
x∈F
d VT (R
n (x, ·), π)
e
−c
√
2
.
Démonstration. On munit R
F
≡ R
2
a du produit scalaire usuel noté ·, ··. La
matrice stochastique R est symétrique
3 , son spectre est réel et inclus dans
[−1, 1] = R ∩ {z ∈ C : |z| 1}.
De plus, il existe une base orthonormée de R
F formée de vecteurs propres
(f j ) 1j2 a de R associés aux valeurs propres (λ j ) 1j2 a classées par ordre
décroissant. En particulier, λ 1 vaut 1 et f 1 est la fonction constante égale
à 2
−a/2 . Rappelons que π est la loi uniforme sur F de cardinal 2
a et donc
π(x) = 2
−a pour tout x ∈ F . Pour toute fonction f de F dans R et x de F ,
R
n (f )(x) =
2
a
j=1
f, f j f j (x)λ
n
j = π(f ) +
2
a
j=2
f, f j f j (x)λ
n
j .
Pour la fonction z ∈ F → f (z) = 1 y (z), on obtient la décomposition spectrale
3. Pour toute matrice de transition sur un espace d’états fini, la loi uniforme est
invariante (respectivement réversible) si et seulement si la matrice est doublement
stochastique (respectivement symétrique).
117
À présent, pour contrôler la queue de distribution de T d , on observe tout
d’abord que T d coïncide avec le premier instant où toutes les coordonnées
dans I := {i ∈ {1, . . . , a} : x i = x
i } ont été mises à jour au moins une fois. On
a card(I) = d. Supposons pour simplifier la notation que I = {1, . . . , d}. Si les
variables aléatoires (τ i ) 1횿i횿d désignent les temps successifs de modification
d’une nouvelle coordonnée alors T d = τ d et les variables aléatoires (G i ) 1id
définies par G 1 = 1 et G i = τ i − τ i−1 pour 2 i d sont indépendantes et
de lois géométriques de paramètres respectifs (d + 1 − i)/d. On retrouve ici le
collectionneur de coupons de la section 1.5. Il ne reste plus qu’à observer que
P(T d > n) croît en d, et atteint son maximum pour d = a, ce qui revient à
prendre x = (0, . . . , 0) et x
= (1, . . . , 1).
Le théorème 1.14 assure que pour tout réel c 0,
P(T a a log(a) + ca) e
−c+1/a .
Le théorème suivant raffine cette estimation de max x∈F d VT (R
n (x, ·), π).
Théorème 9.4 (Temps long). Si
n =
a log(a)
2
+ ca avec c 0
alors
max
x∈F
d VT (R
n (x, ·), π)
e
−c
√
2
.
Démonstration. On munit R
F
≡ R
2
a du produit scalaire usuel noté ·, ··. La
matrice stochastique R est symétrique
3 , son spectre est réel et inclus dans
[−1, 1] = R ∩ {z ∈ C : |z| 1}.
De plus, il existe une base orthonormée de R
F formée de vecteurs propres
(f j ) 1j2 a de R associés aux valeurs propres (λ j ) 1j2 a classées par ordre
décroissant. En particulier, λ 1 vaut 1 et f 1 est la fonction constante égale
à 2
−a/2 . Rappelons que π est la loi uniforme sur F de cardinal 2
a et donc
π(x) = 2
−a pour tout x ∈ F . Pour toute fonction f de F dans R et x de F ,
R
n (f )(x) =
2
a
j=1
f, f j f j (x)λ
n
j = π(f ) +
2
a
j=2
f, f j f j (x)λ
n
j .
Pour la fonction z ∈ F → f (z) = 1 y (z), on obtient la décomposition spectrale
3. Pour toute matrice de transition sur un espace d’états fini, la loi uniforme est
invariante (respectivement réversible) si et seulement si la matrice est doublement
stochastique (respectivement symétrique).