204
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
La marche al´ eatoire repr´ esentant l’exploration al´ eatoire des politiques de
tests {0, 1}
N ` a partir d’une configuration initiale X 0 ∈ {0, 1}
N est donn´ ee par
la formule r´ ecursive suivante
X n = θ Un (X n−1 )
o` u U n d´ esigne une suite de variables al´ eatoires ind´ ependantes, et de mˆ eme loi
que U .
7.4.3 Mesures r´ eversibles
Essayons `
a nouveau d’approfondir l’´ etude des explorations al´ eatoires. Les
probabilit´ es de transitions de ce processus al´ eatoire sont donn´ ees par la formule synth´ etique suivante :
P(X n = y | X n−1 = x) = M (x, y)
=: d´ ef.
1
2 N
u∈{1,...,N }
1
2
1 θ 0
u (x) (y) +
1
2
1 θ 1
u (x) (y)
avec le couple d’applications (θ
0
u , θ
1
u ) de {−1, +1}
S vers lui mˆ eme d´ efinies par
θ
0
u (x)(i) = θ
1
u (x)(i) = x(i) pour tous les indices i ∈ {1, . . . , N} − {U }
et
θ
0
u (x)(u) = 0 et θ
1
u (x)(u) = 1
Avec ces notations, on peut noter que l’on a
θ
0
u θ
0
u = θ
0
u θ
1
u = θ
0
u
θ
1
u θ
1
u = θ
1
u θ
0
u = θ
1
u
et par cons´ equent
M (x, θ
0
u (x)) =
1
2 2 N =
1
2 N
1
2
1 θ 0
u (x) (x) +
1
2
1 θ 1
u (x) (x)
=
1
2 N
1
2
1 θ 0
u (θ 0
u (x)) (x) +
1
2
1 θ 1
u (θ 0
u (x)) (x)
= M (θ
0
u (x), x)
De mˆ eme on obtient
M (x, θ
1
u (x)) = M (θ
1
u (x), x)
On en conclut que la transition M (x, y) est sym´ etrique (ou r´ eversible par
rapport ` a la mesure de comptage λ(x) =
1
2 N sur E = {0, 1}
N ) en ce sens o` u
∀(x, y) ∈ E
2
M (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 = {0, 1}
N . Autrement dit, pour toute s´ equence de
tests x ∈ {0, 1}
N