6.5 L’´ echantillonneur de Gibbs
191
Les sous ensembles
A m :=
u ∈ S
d : W(u) ≥ m et P(u) ≤ p
repr´ esentent les remplissages de sac admissibles ayant une valeur minimale
fix´ ee m. Lorsque m = 0, l’ensemble A 0 est l’ensemble des configurations ne
d´ epassant pas la capacit´ e du sac ` a dos.
Notons enfin que ces collections d’ensembles sont d´ ecroissantes
m 2 ≥ m 1 =⇒ A m2 ⊂ A m1
Les sous ensembles A m,k et A
k
m (u 1 , . . . , u k−1 , u k+1 , . . . , u d ) associ´ es aux d´ esint´ egrations de la loi cible
π(u 1 , . . . , u d )
:=
1
Card(A m )
1 Am (u 1 , . . . , u d )
=
Card
A
k
m (u 1 , . . . , u k−1 , u k+1 , . . . , u d )
Card(A m )
1 A m,k (u 1 , . . . , u k−1 , u k+1 , . . . , u d )
×
1
Card (A k
m (u 1 , . . . , u k−1 , u k+1 , . . . , u d ))
1 A k
m (u1,...,u k−1 ,u k+1 ,...,u d ) (u k )
avec 1 ≤ k ≤ d, sont ici donn´ es par les formules suivantes
A m,k :=
(u 1 , . . . , u k−1 , u k+1 , . . . , u d ) ∈ {0, 1}
d−1 :
∃u k ∈ {0, 1} t.q.
d
i=1
p i u i ≤ p
et
d
i=1
w i u i ≥ m
et pour chaque s´ equence admissible (u 1 , . . . , u k−1 , u k+1 , . . . , u d ) ∈ A m,k
A
k
m (u 1 , . . . , u k−1 , u k+1 , . . . , u d )
:= {u k ∈ {0, 1} t.q.
p k u k ≤ p
−
1≤i≤d, i =k (p i u i ) et w k u k ≥ m −
1≤i≤d, i =k (v i u i )
On notera que
(u 1 , . . . , u k−1 , u k+1 , . . . , u d ) ∈ A m,k ⇐⇒ A
k
m (u 1 , . . . , u k−1 , u k+1 , . . . , u d ) = ∅