338
11 Optimisation et Combinatoire ´ enum´ erative
avec
M (u, A m k+1 ) := M (1 Am k+1 )(u)
La simulation d’une transition selon M k+1 ne n´ ecessite pas le calcul
de M (u, A m k+1 ). Simuler une variable de loi M k+1 (u, v) partant d’une
s´ equence u revient ` a proposer tout d’abord une transition u v de loi
M (u, v). On accepte ensuite cette transition si v ∈ A m k+1 . Dans le cas
contraire, on reste au point de d´ epart u.
2. Au lieu de modifier une seule composante u I (1 − u I ) comme nous
l’avons fait dans (11.12), on peut choisir de modifier les composantes associ´ ees `
a un couple d’indices I 1 = i 1 et I 2 = i 2 au hasard dans {1, . . . , d}
2
puis on remplace la coordonn´ ee u i1 et u i2 par (1 − u i1 ) et (1 − u i1 ). On
peut aussi v´ erifier dans ce cas que la transition correspondante M (u, v)
est r´ eversible par rapport ` a la mesure uniforme sur E.
3. Au lieu d’effectuer une seule transition d’acceptation rejet M k+1 comme
indiqu´ e en (11.13), on peut choisir d’effectuer un nombre r ≥ 1 de telles
transitions. Plus formellement, on peut remplacer M k+1 par M
r
k+1 o` u
r ≥ 1.
4. On peut aussi choisir l’indice r de fa¸ con adaptative en attendant par
exemple qu’il y aient au moins la moiti´ e des propositions qui aient ´ et´ e
accept´ ees.
5. On peut aussi utiliser l’´ echantillonneur de Gibbs d´ ecrit dans la section 6.5.5. On rappelle que cette transition dans l’espace des configurations
A m k+1 est la compos´ ee de d transitions ´ el´ ementaires :
M k+1 =
K
(k+1)
1
K
(k+1)
2
. . . K
(k+1)
d−1
K
(k+1)
d
Cette transition peut s’exprimer de fa¸ con synth´ etique par le diagramme
suivant.
⎛
⎜
⎜
⎜
⎜
⎜
⎝
u 1
u 2
u 3
. . .
u d
⎞
⎟
⎟
⎟
⎟
⎟
⎠
K
(k+1)
1
−→
⎛
⎜
⎜
⎜
⎜
⎜
⎝
v 1
u 2
u 3
. . .
u d
⎞
⎟
⎟
⎟
⎟
⎟
⎠
K
(k+1)
2
−→
⎛
⎜
⎜
⎜
⎜
⎜
⎝
v 1
v 2
u 3
. . .
u d
⎞
⎟
⎟
⎟
⎟
⎟
⎠
K
(k+1)
3
−→
⎛
⎜
⎜
⎜
⎜
⎜
⎝
v 1
v 2
v 3
. . .
u d
⎞
⎟
⎟
⎟
⎟
⎟
⎠
K
(k+1)
4
−→ . . .
K
(k+1)
d
−→
⎛
⎜
⎜
⎜
⎜
⎜
⎝
v 1
v 2
v 3
. . .
v d
⎞
⎟
⎟
⎟
⎟
⎟
⎠
(11.14)
La l-i` eme transition K
(k+1)
l
de l’´ echantillonneur de Gibbs (11.14) associ´ e
` a ces formules de d´ esint´ egrations est clairement donn´ ee par la formule
suivante
11 Optimisation et Combinatoire ´ enum´ erative
avec
M (u, A m k+1 ) := M (1 Am k+1 )(u)
La simulation d’une transition selon M k+1 ne n´ ecessite pas le calcul
de M (u, A m k+1 ). Simuler une variable de loi M k+1 (u, v) partant d’une
s´ equence u revient ` a proposer tout d’abord une transition u v de loi
M (u, v). On accepte ensuite cette transition si v ∈ A m k+1 . Dans le cas
contraire, on reste au point de d´ epart u.
2. Au lieu de modifier une seule composante u I (1 − u I ) comme nous
l’avons fait dans (11.12), on peut choisir de modifier les composantes associ´ ees `
a un couple d’indices I 1 = i 1 et I 2 = i 2 au hasard dans {1, . . . , d}
2
puis on remplace la coordonn´ ee u i1 et u i2 par (1 − u i1 ) et (1 − u i1 ). On
peut aussi v´ erifier dans ce cas que la transition correspondante M (u, v)
est r´ eversible par rapport ` a la mesure uniforme sur E.
3. Au lieu d’effectuer une seule transition d’acceptation rejet M k+1 comme
indiqu´ e en (11.13), on peut choisir d’effectuer un nombre r ≥ 1 de telles
transitions. Plus formellement, on peut remplacer M k+1 par M
r
k+1 o` u
r ≥ 1.
4. On peut aussi choisir l’indice r de fa¸ con adaptative en attendant par
exemple qu’il y aient au moins la moiti´ e des propositions qui aient ´ et´ e
accept´ ees.
5. On peut aussi utiliser l’´ echantillonneur de Gibbs d´ ecrit dans la section 6.5.5. On rappelle que cette transition dans l’espace des configurations
A m k+1 est la compos´ ee de d transitions ´ el´ ementaires :
M k+1 =
K
(k+1)
1
K
(k+1)
2
. . . K
(k+1)
d−1
K
(k+1)
d
Cette transition peut s’exprimer de fa¸ con synth´ etique par le diagramme
suivant.
⎛
⎜
⎜
⎜
⎜
⎜
⎝
u 1
u 2
u 3
. . .
u d
⎞
⎟
⎟
⎟
⎟
⎟
⎠
K
(k+1)
1
−→
⎛
⎜
⎜
⎜
⎜
⎜
⎝
v 1
u 2
u 3
. . .
u d
⎞
⎟
⎟
⎟
⎟
⎟
⎠
K
(k+1)
2
−→
⎛
⎜
⎜
⎜
⎜
⎜
⎝
v 1
v 2
u 3
. . .
u d
⎞
⎟
⎟
⎟
⎟
⎟
⎠
K
(k+1)
3
−→
⎛
⎜
⎜
⎜
⎜
⎜
⎝
v 1
v 2
v 3
. . .
u d
⎞
⎟
⎟
⎟
⎟
⎟
⎠
K
(k+1)
4
−→ . . .
K
(k+1)
d
−→
⎛
⎜
⎜
⎜
⎜
⎜
⎝
v 1
v 2
v 3
. . .
v d
⎞
⎟
⎟
⎟
⎟
⎟
⎠
(11.14)
La l-i` eme transition K
(k+1)
l
de l’´ echantillonneur de Gibbs (11.14) associ´ e
` a ces formules de d´ esint´ egrations est clairement donn´ ee par la formule
suivante