120
9 Urnes d’Ehrenfest
d VT (Loi(Z t | Z 0 = x), Loi(Z t | Z 0 = x
)) P(S d > t).
Pour contrôler la queue de distribution de S d , on recherche une représentation
plus commode. Il y a au départ a − d + 2d = a + d transitions possibles, de
même taux 1/a, dont 2d provoquent une nouvelle coalescence de coordonnée.
Cela donne un taux total de λ = (a + d)/a et une probabilité de coalescence
de coordonnée de p = 2d/(a+d). La construction des trajectoires
5 et une propriété des lois exponentielles
6 font que la première coalescence de coordonnée
a lieu au bout d’une durée aléatoire F d de loi exponentielle de paramètre
pλ =
2d
a + d
a + d
a
=
2
a
d.
Plus généralement, pour tout i ∈ {1, . . . , d}, la i
e coalescence de coordonnée
a lieu au bout d’une durée aléatoire F d−i+1 de loi exponentielle de paramètre
2(d − i + 1)
a + d − i + 1
a + d − i + 1
a
=
2
a
(d − i + 1).
Ces durées sont indépendantes, et le temps de coalescence global
S d := inf{t 0 : Z t = Z
t }
a la même loi que F d +· · ·+F 1 où F d , . . . , F 1 sont des v.a.r. indépendantes avec
F k ∼ Exp(2k/a) pour tout k ∈ {1, . . . , d}. Le lemme de Rényi 11.3 indique
que F d + · · · + F 1 a la même loi que max(E 1 , . . . , E d ) où E 1 , . . . , E d sont des
v.a.r. i.i.d. de loi exponentielle de paramètre 2/a.
S d
loi
= max
1id
E i .
Pour tout t 0, la quantité P(S d > t) croît en d, et atteint son maximum
P(S a > t) pour d = a, ce qui correspond à x = (0, . . . , 0) et x
= (1, . . . , 1).
Le temps aléatoire S a est plus facile à étudier que le temps T a de complétion d’une collection même s’ils ont le même comportement asymptotique
comme le montre le résultat suivant.
Théorème 9.6 (Temps long pour la chaîne à temps continu).
S a − (a/2) log(a)
a/2
loi
−→
a→∞
Gumbel
où la loi de Gumbel a pour fonction de répartition t ∈ R → e
−e
−t .
5. Si Z est une chaîne de Markov à temps continu et à espace d’états discret E
de générateur infinitésimal G = (G(x, y))x,y∈E alors sachant que la chaîne est en x
au temps t, le prochain saut a lieu au bout d’un temps exponentiel de paramètre
−G(x, x) et se fait en y = x avec probabilité −G(x, y)/G(x, x).
6. Le lemme 11.4 affirme que si G, E1, E2, . . . sont des v.a. indépendantes avec G
de loi géométrique de paramètre p et E1, E2, . . . de loi exponentielle de paramètre λ
alors la somme aléatoire E1 + · · · + EG suit la loi exponentielle de paramètre pλ.
9 Urnes d’Ehrenfest
d VT (Loi(Z t | Z 0 = x), Loi(Z t | Z 0 = x
)) P(S d > t).
Pour contrôler la queue de distribution de S d , on recherche une représentation
plus commode. Il y a au départ a − d + 2d = a + d transitions possibles, de
même taux 1/a, dont 2d provoquent une nouvelle coalescence de coordonnée.
Cela donne un taux total de λ = (a + d)/a et une probabilité de coalescence
de coordonnée de p = 2d/(a+d). La construction des trajectoires
5 et une propriété des lois exponentielles
6 font que la première coalescence de coordonnée
a lieu au bout d’une durée aléatoire F d de loi exponentielle de paramètre
pλ =
2d
a + d
a + d
a
=
2
a
d.
Plus généralement, pour tout i ∈ {1, . . . , d}, la i
e coalescence de coordonnée
a lieu au bout d’une durée aléatoire F d−i+1 de loi exponentielle de paramètre
2(d − i + 1)
a + d − i + 1
a + d − i + 1
a
=
2
a
(d − i + 1).
Ces durées sont indépendantes, et le temps de coalescence global
S d := inf{t 0 : Z t = Z
t }
a la même loi que F d +· · ·+F 1 où F d , . . . , F 1 sont des v.a.r. indépendantes avec
F k ∼ Exp(2k/a) pour tout k ∈ {1, . . . , d}. Le lemme de Rényi 11.3 indique
que F d + · · · + F 1 a la même loi que max(E 1 , . . . , E d ) où E 1 , . . . , E d sont des
v.a.r. i.i.d. de loi exponentielle de paramètre 2/a.
S d
loi
= max
1id
E i .
Pour tout t 0, la quantité P(S d > t) croît en d, et atteint son maximum
P(S a > t) pour d = a, ce qui correspond à x = (0, . . . , 0) et x
= (1, . . . , 1).
Le temps aléatoire S a est plus facile à étudier que le temps T a de complétion d’une collection même s’ils ont le même comportement asymptotique
comme le montre le résultat suivant.
Théorème 9.6 (Temps long pour la chaîne à temps continu).
S a − (a/2) log(a)
a/2
loi
−→
a→∞
Gumbel
où la loi de Gumbel a pour fonction de répartition t ∈ R → e
−e
−t .
5. Si Z est une chaîne de Markov à temps continu et à espace d’états discret E
de générateur infinitésimal G = (G(x, y))x,y∈E alors sachant que la chaîne est en x
au temps t, le prochain saut a lieu au bout d’un temps exponentiel de paramètre
−G(x, x) et se fait en y = x avec probabilité −G(x, y)/G(x, x).
6. Le lemme 11.4 affirme que si G, E1, E2, . . . sont des v.a. indépendantes avec G
de loi géométrique de paramètre p et E1, E2, . . . de loi exponentielle de paramètre λ
alors la somme aléatoire E1 + · · · + EG suit la loi exponentielle de paramètre pλ.