210
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
7.5.3 Reversibilit´ e de l’exploration
La nature r´ eversible du processus d’explorations locales d´ ecrit ci-dessus est
claire. Il suffit de rappeler que les transpositions d’indices sont des fonctions
involutives
∀(i, j) θ
2
(i,j) = Id
=⇒ (∀n ≥ 1 σ n θ Un = σ n−1 )
On note M (x, y) les probabilit´ es de transitions du processus σ
P(σ n = y | σ n−1 = x) = M (x, y)
et par la lettre μ, la mesure uniforme sur E = G N
∀x ∈ E
μ(x) =
1
N !
D’apr` es la discussion pr´ ec´ edente, nous avons
∀(x, y) ∈ E
2
μ(x) M (y, x) = μ(y) M (y, x)
Supposons que le marcheur soit initialis´ e en un point X 0 , choisi au hasard et uniform´ ement dans E = G N . Autrement dit, pour toute permutation
d’indices x ∈ G N
P(X 0 = x) = μ(x)
Pour calculer la distribution de l’´ etat suivant X 1 , on utilise ` a nouveau la
d´ ecomposition suivante :
P(X 0 = x , X 1 = y) = P(X 1 = y | X 0 = x) × P(X 0 = x) =
1
N !
M (x, y)
D’apr` es les propri´ et´ es de r´ eversibilit´ e, on en conclut que
P(X 1 = y) =
x∈E
P(X 0 = x , X 1 = y) =
x∈E
P(X 1 = y | X 0 = x) P(X 0 = x)
=
1
N !
x∈E
M (y, x) =
1
N !
= μ(y)
On a donc `
a nouveau montr´ e que la mesure uniforme μ est une mesure
r´ eversible du mouvement, et a fortiori une mesure invariante de l’exploration.
7.5.4 Quelques variantes
Il existe d’autres strat´ egies pour explorer le paysage. On peut par exemple,
remplacer les transpositions d’indices θ (i,j) par les inversions de suite d’indices
θ (i,j) , d´ efinies par la formule suivante