7.6 L’algorithme du recuit simul´ e
215
M T (x, y) = d´ ef. P(X
T
n+1 = y | X
T
n = x)
= M (x, y) g T (x, y) +
1 −
z∈E
M (x, z)g T (x, z)
1 x (y)
Supposons que le noyau de proposition M (x, y) soit r´ eversible par rapport `
a une mesure de probabilit´ e not´ ee μ(x). Pour des exemples de mesures
r´ eversibles, nous renvoyons le lecteur `
a la section pr´ ec´ edente. Rappelons que
dans ce cas nous avons
μ(x) M (x, y) = μ(y) M (y, x)
La mesure μ correspond souvent `
a la distribution asymptotique en temps long
du processus d’exploration ayant pour transitions locales les fonctions M (x, y).
On peut ` a nouveau observer qu’un tel processus repr´ esente l’´ evolution d’un
recuit thermique dans un bain `
a temp´ erature infinie
lim
T ↑∞
g T (x, y) = 1 =⇒ lim
T ↑∞
M T (x, y) = M (x, y)
Nous allons voir que la r´ eversibilit´ e de μ par rapport `
a M implique celle
de μ(x)e
−
1
T V (x) par rapport `
a M T
μ(x)e
−
1
T V (x)
× M T (x, y) =
μ(y)e
−
1
T V (y)
× M T (y, x).
Notons simplement que
e
−
1
T V (x) g T (x, y) = e
−
1
T [V (x)+(V (y)−V (x))+]
= e
−
1
T max (V (x),V (y)) = e
−
1
T V (y) g T (y, x).
Cette simple observation entraˆ ıne que
μ(x)e
−
1
T V (x)
M (x, y) g T (x, y) = (μ(x) M (x, y)) e
−
1
T V (x) g T (x, y)
= (μ(y) M (y, x)) e
−
1
T V (y) g T (y, x)
=
μ(y)e
−
1
T V (y)
M (y, x) g T (y, x)
La fin de la d´ emonstration r´ esulte simplement du fait ´ el´ ementaire suivant :
μ(x)e
−
1
T V (x)
1 −
z∈E M (x, z)g T (x, z)
1 x (y)
=
μ(y)e
−
1
T V (y)
1 −
z∈E M (x, z)g T (y, z)
1 y (x)
7.6.3 Concentration
Nous avons donc montr´ e que la mesure de probabilit´ e