340
11 Optimisation et Combinatoire ´ enum´ erative
Par exemple, dans l’exemple du sac ` a dos d´ ecrit dans la section 6.5.5, ces
mesures s’expriment sous la forme suivante
η k (du) :=
1
μ
e β k W 1 {P≤p }
e
β k W(u) 1 {P≤p } (u) μ(du)
=
1
μ
e −β k V 1 {P≤p }
e
−β k V(u) 1 {P≤p } (u) μ(du)
avec
V(u) = V(u 1 , . . . , u d ) = WW − W(u) =
1≤i≤d
(1 − u i )w i ≥ 0
Pour toute transition de Markov M (u, dv) ayant la propri´ et´ e de μ-r´ eversibilit´ e
μ(du) M (u, dv) = μ(dv) M (v, du)
les transitions suivantes
M k (u, dv) := M (u, dv) 1 {P≤p } (v) e
−β k V(u)
+
1 − M
1 {P≤p } e
−β k V
(u)
δ u (dv)
sont η k -invariantes
η k = η k M k
En reprenant la discussion pr´ ec´ edente, on construit ais´ ement un algorithme
d’acceptation-rejet en interaction permettant de simuler les lois cibles η k .
Une autre strat´ egie est d’utiliser une transition de Metropolis-Hastings
associ´ ee ` a la mesure cible suivante
μ k (du) =
1
μ (e β k W )
e
β k W(u) μ(du) =
1
μ (e −β k V )
e
−β k V(u) μ(du)
Par exemple, si K(u, dv) d´ esigne une transition ayant la propri´ et´ e de μr´ eversibilit´ e
μ(du) K(u, dv) = μ(dv) K(v, du)
alors les transitions suivantes
K k (u, dv) : = K(u, dv)
1 ∧ e
−β k (V(v)−V(u))
+
+
1 −
K(u, dw)
1 ∧ e
−β k (V(w)−V(u))
+
δ u (dv)
sont μ k -r´ eversibles. Si K n’est pas μ-r´ eversible, on posera
K k (u, dv) : = K(u, dv)
1 ∧
d(μ k × K) 1
d(μ k × K) 0
(u, v)
+
1 −
K(u, dw)
1 ∧
d(μ k × K) 1
d(μ k × K) 0
(u, w)
δ u (dv)