332
11 Optimisation et Combinatoire ´ enum´ erative
L’´ etape de s´ election consiste `
a poser pour chaque i = 1, . . . , N
ξ
i
n =
ξ
i
n avec probabilit´ e e
−(βn−βn−1) 1 E−A (ξ
i
n )
˜
ξ
i
n avec probabilit´ e 1 − e
−(βn−βn−1) 1 E−A (ξ
i
n )
(11.8)
o` u ˜
ξ
i
n d´ esigne une v.a. de ”loi empirique uniforme” sur A n+1
N
j=1
e
−(βn−βn−1)1 E−A (ξ
j
n )
N
k=1
e
−(βn−βn−1)1 E−A (ξ
k
n )
δ ξ
j
n
On pourra noter que les points ξ
i
n ∈ A sont accept´ es
ξ
i
n = ξ
i
n . Pour les points
ξ
i
n ∈ A ` a l’ext´ erieur de A nous avons la r` egle ´ el´ ementaire suivante :
ξ
i
n =
ξ
i
n avec probabilit´ e e
−(βn−βn−1)
˜
ξ
i
n avec probabilit´ e 1 − e
−(βn−βn−1)
11.4 Analyse des performances
Lorsque la taille de la population N tend vers l’infini, les mesures d’occupation du syst` eme convergent vers les mesures de Boltzmann-Gibbs d´ esir´ ees.
En un certain sens, nous avons
η
N
n :=
1
N
N
i=1
δ ξ i
n
−→ N ↑∞ η n
De mˆ eme, lorsque la taille de la population N tend vers l’infini, les mesures
empiriques non normalis´ ees donn´ ees par les formules
γ
N
n (.) := γ
N
n (1) × η
N
n (.) avec γ
N
n (1) :=
n−1
k=0
η
N
k (g k )
sont des estimateurs non biais´ es des mesures de Boltzmann-Gibbs d´ esir´ ees
γ
N
n −→ N ↑∞ γ n avec E
γ
N
n (.)
= γ n (.)
Dans le cas particulier des fonctions potentiel indicatrices
g k = 1 A k+1
et la mesure de comptage μ(x) =
1
Card(E)
sur un ensemble fini E, nous avons
la convergence presque sure suivante :
ˆ