5.2 Algorithme de Metropolis-Hastings
73
où
ρ(x, y) = α
μ β (y)Q(y, x)
μ β (x)Q(x, y)
1 Q(x,y)>0 .
Alors P est un noyau de transition sur E, irréductible récurrent positif, de loi
invariante réversible μ β ; apériodique si α < 1 ou si Q est apériodique.
Les deux choix les plus classiques pour α sont donnés par
α(u) = min(1, u) et α(u) =
u
1 + u
, u ∈ R + .
Le premier possède une interprétation intuitive. Le second assure que α < 1.
Si la mesure μ β est réversible pour le noyau Q, et c’est le cas par exemple
lorsque μ β est la mesure uniforme sur E et Q(x, y) = Q(y, x) pour tous
x, y ∈ E, alors la construction de Metropolis-Hastings revient tout simplement
à prendre P = (1 − ε)Q + εI, où 0 < ε < 1 assure l’apériodicité.
Démonstration du théorème 5.2. On a 0 P(x, y) Q(x, y) pour tous x, y
dans E avec x = y, et donc P est un noyau de transition. Comme α > 0, le
noyau P hérite du squelette de Q, et il est donc irréductible, et apériodique si
Q l’est. Si α < 1 alors P(x, x) > 0 pour tout x ∈ E et donc P est apériodique.
Comme P est irréductible sur E fini, il possède une unique loi invariante. La
propriété de α donne, pour tous x, y ∈ E, x = y, Q(x, y) = 0,
μ β (x)P(x, y) = μ β (x)Q(x, y)α
μ β (y)Q(y, x)
μ β (x)Q(x, y)
= μ β (x)Q(x, y)
μ β (y)Q(y, x)
μ β (x)Q(x, y)
α
μ β (x)Q(x, y)
μ β (y)Q(y, x)
= μ β (y)P(y, x).
Ainsi μ β est réversible pour P, et c’est donc la loi invariante de P.
L’algorithme de Metropolis-Hastings consiste à simuler les trajectoires de
la chaîne (X t ) t∈N de noyau P. Cela se ramène au problème de la simulation de
la loi discrète P(x, ·) pour un x quelconque. Pour ce faire, soit Y une variable
aléatoire sur E de loi Q(x, ·), et U une variable aléatoire de loi uniforme sur
[0, 1], indépendante de Y . Soit Z la variable aléatoire définie par Z = Y si
U < ρ(x, Y ) et Z = x sinon. Alors Z ∼ P(x, ·) car pour tous y = x,
P(Z = y) = P(U < ρ(x, Y ), Y = y) = ρ(x, y)Q(x, y) = P(x, y).
Autrement dit la proposition Y de loi Q(x, ·) est acceptée ou rejetée selon
que U < ρ(x, Y ) ou pas. L’évaluation de P(x, x) n’est pas requise. On dit que
ρ est la fonction d’acceptation-rejet tandis que Q le noyau de proposition ou
d’exploration. Le noyau Q doit être facile à simuler. En pratique, on utilise
souvent le noyau de la marche aléatoire simple aux plus proches voisins sur le
graphe associé à une distance naturelle sur E :
73
où
ρ(x, y) = α
μ β (y)Q(y, x)
μ β (x)Q(x, y)
1 Q(x,y)>0 .
Alors P est un noyau de transition sur E, irréductible récurrent positif, de loi
invariante réversible μ β ; apériodique si α < 1 ou si Q est apériodique.
Les deux choix les plus classiques pour α sont donnés par
α(u) = min(1, u) et α(u) =
u
1 + u
, u ∈ R + .
Le premier possède une interprétation intuitive. Le second assure que α < 1.
Si la mesure μ β est réversible pour le noyau Q, et c’est le cas par exemple
lorsque μ β est la mesure uniforme sur E et Q(x, y) = Q(y, x) pour tous
x, y ∈ E, alors la construction de Metropolis-Hastings revient tout simplement
à prendre P = (1 − ε)Q + εI, où 0 < ε < 1 assure l’apériodicité.
Démonstration du théorème 5.2. On a 0 P(x, y) Q(x, y) pour tous x, y
dans E avec x = y, et donc P est un noyau de transition. Comme α > 0, le
noyau P hérite du squelette de Q, et il est donc irréductible, et apériodique si
Q l’est. Si α < 1 alors P(x, x) > 0 pour tout x ∈ E et donc P est apériodique.
Comme P est irréductible sur E fini, il possède une unique loi invariante. La
propriété de α donne, pour tous x, y ∈ E, x = y, Q(x, y) = 0,
μ β (x)P(x, y) = μ β (x)Q(x, y)α
μ β (y)Q(y, x)
μ β (x)Q(x, y)
= μ β (x)Q(x, y)
μ β (y)Q(y, x)
μ β (x)Q(x, y)
α
μ β (x)Q(x, y)
μ β (y)Q(y, x)
= μ β (y)P(y, x).
Ainsi μ β est réversible pour P, et c’est donc la loi invariante de P.
L’algorithme de Metropolis-Hastings consiste à simuler les trajectoires de
la chaîne (X t ) t∈N de noyau P. Cela se ramène au problème de la simulation de
la loi discrète P(x, ·) pour un x quelconque. Pour ce faire, soit Y une variable
aléatoire sur E de loi Q(x, ·), et U une variable aléatoire de loi uniforme sur
[0, 1], indépendante de Y . Soit Z la variable aléatoire définie par Z = Y si
U < ρ(x, Y ) et Z = x sinon. Alors Z ∼ P(x, ·) car pour tous y = x,
P(Z = y) = P(U < ρ(x, Y ), Y = y) = ρ(x, y)Q(x, y) = P(x, y).
Autrement dit la proposition Y de loi Q(x, ·) est acceptée ou rejetée selon
que U < ρ(x, Y ) ou pas. L’évaluation de P(x, x) n’est pas requise. On dit que
ρ est la fonction d’acceptation-rejet tandis que Q le noyau de proposition ou
d’exploration. Le noyau Q doit être facile à simuler. En pratique, on utilise
souvent le noyau de la marche aléatoire simple aux plus proches voisins sur le
graphe associé à une distance naturelle sur E :