XX
Table des mati` eres
6.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
6.5.2 Algorithme de simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
6.5.3 D´ esint´ egration de mesures restreintes . . . . . . . . . . . . . . . . 177
6.5.4 Mesures de volume sur des espaces produits . . . . . . . . . . 181
6.5.5 Mesures de comptage sur des espaces produits . . . . . . . . 187
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature . 193
7.1 Explosions combinatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
7.2 La notion de voisinage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
7.3 Mod` eles d’aimantation ferromagn´ etique . . . . . . . . . . . . . . . . . . . . 198
7.3.1 M´ etriques et syst` emes de voisinages . . . . . . . . . . . . . . . . . . 198
7.3.2 Explorations al´ eatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
7.3.3 Comportement en temps long . . . . . . . . . . . . . . . . . . . . . . . 199
7.3.4 Fonctions d’´ energie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
7.4 Explorations al´ eatoires locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
7.4.1 Syst` emes de voisinages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
7.4.2 Marches al´ eatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7.4.3 Mesures r´ eversibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
7.4.4 Fonction ´ energie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
7.5 Espaces de permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
7.5.1 Syst` emes de voisinages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
7.5.2 Explorations locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
7.5.3 Reversibilit´ e de l’exploration . . . . . . . . . . . . . . . . . . . . . . . . 210
7.5.4 Quelques variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
7.5.5 Fonctions ´ energie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7.6 L’algorithme du recuit simul´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
7.6.1 Description de la chaˆ ıne de Markov . . . . . . . . . . . . . . . . . . 213
7.6.2 Recuit homog` ene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
7.6.3 Concentration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
7.6.4 R´ eglages de temp´ erature . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
8 Mesures de Feynman-Kac et m´ ethodes particulaires . . . . . . . 219
8.1 Mesures de Feynman-Kac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
8.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
8.1.2 Formules int´ egrales et vraisemblances de chemins . . . . . . 222
8.1.3 Repr´ esentations ´ equivalentes, mesures corrig´ ees . . . . . . . 225
8.1.4 Une formulation markovienne ` a rebours . . . . . . . . . . . . . . 227
8.2 Mod` eles matriciels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
8.2.1 Produits de matrices positives . . . . . . . . . . . . . . . . . . . . . . 229
8.2.2 Mesures de Feynman-Kac . . . . . . . . . . . . . . . . . . . . . . . . . . 230
8.2.3 Recherche de trajectoires optimales . . . . . . . . . . . . . . . . . . 231
8.3 M´ ethodes de simulation particulaires . . . . . . . . . . . . . . . . . . . . . . . 233
8.3.1 Dynamiques de population g´ en´ etiques . . . . . . . . . . . . . . . . 233
8.3.2 Mod` eles d’arbres g´ en´ ealogiques . . . . . . . . . . . . . . . . . . . . . . 236
8.3.3 Estimation des formules `
a rebours . . . . . . . . . . . . . . . . . . . 237
Table des mati` eres
6.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
6.5.2 Algorithme de simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
6.5.3 D´ esint´ egration de mesures restreintes . . . . . . . . . . . . . . . . 177
6.5.4 Mesures de volume sur des espaces produits . . . . . . . . . . 181
6.5.5 Mesures de comptage sur des espaces produits . . . . . . . . 187
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature . 193
7.1 Explosions combinatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
7.2 La notion de voisinage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
7.3 Mod` eles d’aimantation ferromagn´ etique . . . . . . . . . . . . . . . . . . . . 198
7.3.1 M´ etriques et syst` emes de voisinages . . . . . . . . . . . . . . . . . . 198
7.3.2 Explorations al´ eatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
7.3.3 Comportement en temps long . . . . . . . . . . . . . . . . . . . . . . . 199
7.3.4 Fonctions d’´ energie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
7.4 Explorations al´ eatoires locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
7.4.1 Syst` emes de voisinages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
7.4.2 Marches al´ eatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7.4.3 Mesures r´ eversibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
7.4.4 Fonction ´ energie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
7.5 Espaces de permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
7.5.1 Syst` emes de voisinages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
7.5.2 Explorations locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
7.5.3 Reversibilit´ e de l’exploration . . . . . . . . . . . . . . . . . . . . . . . . 210
7.5.4 Quelques variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
7.5.5 Fonctions ´ energie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7.6 L’algorithme du recuit simul´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
7.6.1 Description de la chaˆ ıne de Markov . . . . . . . . . . . . . . . . . . 213
7.6.2 Recuit homog` ene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
7.6.3 Concentration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
7.6.4 R´ eglages de temp´ erature . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
8 Mesures de Feynman-Kac et m´ ethodes particulaires . . . . . . . 219
8.1 Mesures de Feynman-Kac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
8.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
8.1.2 Formules int´ egrales et vraisemblances de chemins . . . . . . 222
8.1.3 Repr´ esentations ´ equivalentes, mesures corrig´ ees . . . . . . . 225
8.1.4 Une formulation markovienne ` a rebours . . . . . . . . . . . . . . 227
8.2 Mod` eles matriciels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
8.2.1 Produits de matrices positives . . . . . . . . . . . . . . . . . . . . . . 229
8.2.2 Mesures de Feynman-Kac . . . . . . . . . . . . . . . . . . . . . . . . . . 230
8.2.3 Recherche de trajectoires optimales . . . . . . . . . . . . . . . . . . 231
8.3 M´ ethodes de simulation particulaires . . . . . . . . . . . . . . . . . . . . . . . 233
8.3.1 Dynamiques de population g´ en´ etiques . . . . . . . . . . . . . . . . 233
8.3.2 Mod` eles d’arbres g´ en´ ealogiques . . . . . . . . . . . . . . . . . . . . . . 236
8.3.3 Estimation des formules `
a rebours . . . . . . . . . . . . . . . . . . . 237