Algorithmes de Monte Carlo pour chaînes de Markov et méthodes particulaires

B. Jourdain

15h, 5MK

Pour simuler suivant une loi cible $\pi$ sur un espace $E$ muni d’une tribu $\mathcal E$, l’algorithme de Metropolis-Hastings construit une chaine de Markov $(X_n) _{n\geq1}$ qui admet $\pi$ comme mesure réversible. Cet algorithme est l’une des méthode numériques probabilistes les plus largement utilisées en statistique, en physique, en chimie quantique comme en simulation moléculaire si bien qu’une recherche Google sur son nom fournit plus de 350 000 résultats. Lorsque la chaine de Markov est ergodique, la loi de $X_n$ converge vers $\pi$ lorsque $n$ tend vers l’infini et pour $\phi : (E,\mathcal E) \to \mathbb R$ mesurable et telle que $\int_E |\phi(x)|\pi(dx)<\infty$, la loi forte des grands nombres ergodique assure la convergence presque sûre de $\displaystyle \frac1n\sum _{k=1}^n \phi(X_k)$ vers $\displaystyle \int_E \phi(x) \pi(dx)$ lorsque $n\to \infty$.

Dans cette première partie du cours, nous illustrerons sur l’exemple de cet algorithme la condition suffisante d’ergodicité pour une chaine de Markov à valeurs dans un espace général donnée dans [3] et nous établirons sous cette condition la loi forte des grands nombres ergodique. Nous montrerons le théorème de la limite centrale associé sous une condition renforcée qui permet de résoudre l’équation de Poisson. Nous énoncerons le résultat de Peskun [4] qui explique comment minimiser la variance asymptotique. Nous verrons comment guider le choix de la variance des propositions de l’algorithme de Metropolis-Hastings par marche aléatoire à l’aide des résultats de scaling [2]: lorsque la loi cible est une probabilité produit sur un espace dont la dimension tend vers l’infini, la première composante de l’algorithme accelère en temps converge en loi vers une diffusion. Enfin, lorsque la convergence vers l’équilibre est très lente (phénomène de métastabilité), nous étudierons comment l’accélérer par des versions de l’algorithme avec échantillonnage préférentiel adaptatif comme Wang-Landau, SHUS, metadynamics ou well-tempered metadynamics.

Dans un second temps, nous étudierons les algorithmes particulaires génétiques [1] qui en alternant une étape de sélection où les particules interagissent avec une phase de mutation où elles évoluent de facon indépendante suivant un noyau markovien permettent de réduire la variance ou de générer des événements rares.

Bibliographie

  • [1] Del Moral, P.: Feynman-Kac formulae. Genealogical and interacting particle systems with applications. Probability and its Applications (New York). Springer-Verlag, 2004.
  • [2] Gelman, A., Gilks, W. R. and Roberts, G. O., Weak convergence and optimal scaling of random walk Metropolis algorithms, Ann. Appl. Probab. 7(1):110-120, 1997
  • [3] Hairer, M., Mattingly, J. C., Yet another look at Harris’ ergodic theorem for Markov chains. Seminar on Stochastic Analysis, Random Fields and Applications VI, 109-117, Progr. Probab., 63, Birkhauser/Springer Basel AG, Basel, 2011.
  • [4] Peskun, P. H., Optimal Monte-Carlo sampling using Markov chains, Biometrika 60(3):607- 612, 1973.
Avatar
Sorbonne Université Sciences et École Polytechnique
en collaboration avec l’E.S.S.E.C.