5.4 Algorithme de Propp-Wilson
77
5.4 Algorithme de Propp-Wilson
L’algorithme de Metropolis-Hastings permet une simulation approchée
d’une mesure de Gibbs μ β sur E fini, au moyen d’une chaîne de Markov
de noyau P qui admet μ β comme loi invariante et réversible (théorème 5.2).
Nous présentons à présent un algorithme de simulation exacte de μ β .
Soit P un noyau markovien irréductible sur E de probabilité invariante
μ β . Adoptons l’interprétation des chaînes de Markov sous forme de suites
récurrentes aléatoires. Soit donc g : E × [0, 1] → E une fonction telle que
g(x, U ) ∼ P(x, ·) pour tout x ∈ E, où U est une variable aléatoire de loi
uniforme sur [0, 1]. On note G : E → E la fonction aléatoire définie par
G(x) = g(x, U ). Soit (G n ) n0 une suite i.i.d. de fonctions aléatoires de E
dans E, de même loi que G, construites à la manière de G en utilisant une
suite (U n ) n0 de variables aléatoires i.i.d. de loi uniforme sur [0, 1]. Pour tout
n, on construit les applications aléatoires A n : E → E et B n : E → E par
composition de la manière suivante :
A n = G n ◦ · · · ◦ G 1 et B n = G 1 ◦ · · · ◦ G n .
On convient que A 0 et B 0 sont égales à l’application identité de E. Pour tout
x ∈ E et tout n, les variables aléatoires A n (x) et B n (x) suivent la loi P
n (x, ·).
Les suites (A n (x)) n0 et (B n (x)) n0 ont les mêmes lois marginales de dimension 1, mais n’ont pas la même loi en tant que suites. La suite (A n (x)) n0 est
une chaîne de Markov sur E de noyau P et de loi initiale δ x . En revanche,
(B n (x)) n0 n’est pas une chaîne de Markov car le temps est «inversé». On
définit les temps de contraction T A et T B à valeurs dans N ∪ {∞} par
T A = inf{n 0 : card(A n (E)) = 1} où A n (E) = {A n (x) : x ∈ E}
et de même,
T B = inf{n 0 : card(B n (E)) = 1} où B n (E) = {B n (x) : x ∈ E}.
On dit que G est contractante lorsque p = P(card(G(E)) = 1) > 0.
Théorème 5.4 (Convergence à la coalescence pour la suite renversée). Si G
est contractante alors P(T B < ∞) = 1, pour tout x ∈ E, B T B (x) ∼ μ β , et
B n (x) = B T B (x) pour tout n T B .
Notons que (A n (x)) n0 converge en loi vers μ tandis que (B n (x)) n0
converge p.s. vers une variable aléatoire de loi μ.
Démonstration. Les événements C n = {card(G n (E)) = 1} sont indépendants
et de même probabilité p = P(card(G(E)) = 1) > 0. Par le lemme de BorelCantelli, presque sûrement, card(G n (E)) = 1 pour une infinité de valeurs de
n, et en particulier P(T B < ∞) = 1. Le temps aléatoire T B définit presque
sûrement un singleton aléatoire {x B } tel que B T B (x) = x B pour tout x ∈ E.
Il en découle que B n (x) = x B pour tout x ∈ E et tout n T B car
77
5.4 Algorithme de Propp-Wilson
L’algorithme de Metropolis-Hastings permet une simulation approchée
d’une mesure de Gibbs μ β sur E fini, au moyen d’une chaîne de Markov
de noyau P qui admet μ β comme loi invariante et réversible (théorème 5.2).
Nous présentons à présent un algorithme de simulation exacte de μ β .
Soit P un noyau markovien irréductible sur E de probabilité invariante
μ β . Adoptons l’interprétation des chaînes de Markov sous forme de suites
récurrentes aléatoires. Soit donc g : E × [0, 1] → E une fonction telle que
g(x, U ) ∼ P(x, ·) pour tout x ∈ E, où U est une variable aléatoire de loi
uniforme sur [0, 1]. On note G : E → E la fonction aléatoire définie par
G(x) = g(x, U ). Soit (G n ) n0 une suite i.i.d. de fonctions aléatoires de E
dans E, de même loi que G, construites à la manière de G en utilisant une
suite (U n ) n0 de variables aléatoires i.i.d. de loi uniforme sur [0, 1]. Pour tout
n, on construit les applications aléatoires A n : E → E et B n : E → E par
composition de la manière suivante :
A n = G n ◦ · · · ◦ G 1 et B n = G 1 ◦ · · · ◦ G n .
On convient que A 0 et B 0 sont égales à l’application identité de E. Pour tout
x ∈ E et tout n, les variables aléatoires A n (x) et B n (x) suivent la loi P
n (x, ·).
Les suites (A n (x)) n0 et (B n (x)) n0 ont les mêmes lois marginales de dimension 1, mais n’ont pas la même loi en tant que suites. La suite (A n (x)) n0 est
une chaîne de Markov sur E de noyau P et de loi initiale δ x . En revanche,
(B n (x)) n0 n’est pas une chaîne de Markov car le temps est «inversé». On
définit les temps de contraction T A et T B à valeurs dans N ∪ {∞} par
T A = inf{n 0 : card(A n (E)) = 1} où A n (E) = {A n (x) : x ∈ E}
et de même,
T B = inf{n 0 : card(B n (E)) = 1} où B n (E) = {B n (x) : x ∈ E}.
On dit que G est contractante lorsque p = P(card(G(E)) = 1) > 0.
Théorème 5.4 (Convergence à la coalescence pour la suite renversée). Si G
est contractante alors P(T B < ∞) = 1, pour tout x ∈ E, B T B (x) ∼ μ β , et
B n (x) = B T B (x) pour tout n T B .
Notons que (A n (x)) n0 converge en loi vers μ tandis que (B n (x)) n0
converge p.s. vers une variable aléatoire de loi μ.
Démonstration. Les événements C n = {card(G n (E)) = 1} sont indépendants
et de même probabilité p = P(card(G(E)) = 1) > 0. Par le lemme de BorelCantelli, presque sûrement, card(G n (E)) = 1 pour une infinité de valeurs de
n, et en particulier P(T B < ∞) = 1. Le temps aléatoire T B définit presque
sûrement un singleton aléatoire {x B } tel que B T B (x) = x B pour tout x ∈ E.
Il en découle que B n (x) = x B pour tout x ∈ E et tout n T B car