7.4 Explorations al´ eatoires locales
203
x = (x(i)) i=1,...,N ∈ E = {0, 1}
N
On convient que les chiffres 1 et 0 correspondent respectivement ` a la situation
ou l’on fait un test, ou non. `
A titre d’exemple, lorsque N = 4, la s´ equence
suivante
x = (1, 1, 0, 1) ∈ E = {0, 1}
4
correspond `
a la situation o` u l’op´ erateur effectue des tests de qualit´ e sur toutes
les machines, sauf sur la troisi` eme.
On d´ efinit sur l’espace de politiques de test {0, 1}
N une distance naturelle
en comptant simplement le nombre de tests distincts entre deux s´ equences
donn´ ees
d(x, y) =
1
2
N
i=1
|x(i) − y(i)|
On peut `
a nouveau associer ` a cette distance une vari´ et´ e de syst` emes d’exploration de voisinages. Les voisinages entre s´ equences ne diff´ erant que d’un test
correspondent ` a la relation de voisinage suivante
x ∼ y ⇐⇒ d(x, y) ≤ 1
Ces syst` emes de voisinages permettent de passer d’une politique de test ` a
une autre, en au plus N ´ etapes. Plus pr´ ecis´ ement, pour chaque coupe de
configurations x = (x(i)) i=1,...,N et y = (y(i)) i=,...,N , il existe une suite d’´ etats
(x p ) p=1,...,n , avec n ≤ N , telle que
x → x 1 ∼ x → x 2 ∼ x 1 → . . . → x n−1 → x n ∼ x n−1 → x ∼ x n
7.4.2 Marches al´ eatoires
On peut visiter al´ eatoirement l’ensemble des politiques de tests en suivant
ces syst` emes de voisinages. L’explorateur passe d’une configuration x ` a une
autre y en modifiant al´ eatoirement l’une des N coordonn´ ees. Une fa¸ con d’effectuer cette transition x y consiste `
a choisir al´ eatoirement un indice U
dans {1, . . . , N}, et de changer une fois sur deux la coordonn´ ee s´ electionn´ ee
x(U ). On peut ´ ecrire plus formellement ce passage d’une s´ equence x ` a une
configuration voisine y, en posant
x y = θ U (x)
o` u θ d´ esigne l’application de {1, . . . , N} vers lui mˆ eme d´ efinie par
θ U (x)(i) = x(i) pour tous les i ∈ {1, . . . , N} − {U }
et
θ U (x)(U ) =
0 avec probabilit´ e 1/2
1 avec probabilit´ e 1/2