72
5 Mesures de Gibbs
5.2 Algorithme de Metropolis-Hastings
On s’intéresse dans cette section au problème de la simulation d’une mesure de Gibbs sur un espace fini E, d’énergie H : E → R et de paramètre
β > 0, définie pour tout x ∈ E par
μ β (x) =
1
Z β
e
−βH(x) , où Z β =
x∈E
e
−βH(x) .
Même si β et H sont connus, il est souvent difficile voire impossible d’évaluer
numériquement la constante de normalisation Z β car E est trop gros ou trop
complexe à parcourir. En revanche, le rapport
μ β (x)
μ β (y)
= e
βH(y)−βH(x)
ne dépend que de la différence d’énergie H(y) − H(x), dont l’évaluation en
pratique est même souvent moins coûteuse que l’évaluation de H(x) et H(y)
séparément. L’algorithme de Metropolis-Hastings permet de construire et de
simuler une chaîne de Markov récurrente apériodique (X t ) t∈N sur E de loi
invariante μ β , dont la matrice de transition ne fait intervenir μ β qu’à travers
les rapports μ β (x)/μ β (y). Comme E est fini, la condition de Doeblin ou le
théorème de Perron-Frobenius fournissent une convergence exponentielle de
l’erreur
3 de la forme : il existe c > 0 et η < 1 tel que, pour tout t ∈ N,
d VT (Loi(X t ), μ β ) cη
t .
On dispose ainsi d’un générateur approché de μ β : pour t 1,
μ β ≈ Loi(X t ).
Le théorème 5.2 fournit une construction du noyau de transition P de (X t ) t∈N .
Théorème 5.2 (Metropolis-Hastings). Soit Q : E × E → [0, 1] un noyau de
transition irréductible sur E, vérifiant, pour tous x, y ∈ E,
Q(x, y) = 0 ssi Q(y, x) = 0.
Soit α : R + → ]0, 1] une fonction vérifiant, pour tout u ∈ R + ,
α(u) = uα
1
u
.
Soit P : E × E → R défini, pour tous x, y ∈ E, par
P(x, y) =
Q(x, y)ρ(x, y)
si x = y,
1 −
z =x P(x, z) si x = y,
3. En pratique ces bornes sont rarement utiles, en dehors de certains cas spéciaux.