Chaines de Markov

Master I Modélisation aléatoire 2004-2007 (13\times 2 et 13\times 3 heures de cours et TD)

Les chaînes de Markov sont, après les suites de variables aléatoires indépendantes, les processus les plus simples. Elles sont caractérisées par une propriété : conditionnellement au présent, le passé et le futur sont indépendants. Ce cours aborde uniquement les chaînes de Markov qui vivent sur un espace dénombrable d”états.

En s’appuyant sur les techniques de couplage, le cours caractérisera les chaînes de Markov homogènes qui admettent une “loi invariante”, ou “loi d”équilibre”. On étudiera plus en détail les noyaux Markoviens irréductibles et l”ergodicité d”un point de vue combinatoire et algébrique. On abordera par des méthodes probabilistes les propriétés de récurrence et de transience.Les chaînes de Markov sont importantes pour deux raisons

  • en tant qu”outil de modélisation, en théorie des files d”attente ; en bio-mathématiques ; en épidémiologie ; en théorie de la communication …
  • en tant qu”outil calculatoire.

C’est surtout le deuxième aspect qui nous intéressera. Les problèmes de dénombrement de structures combinatoires, d”estimation de volume sont souvent des problèmes “difficiles” pour lesquels on conjecture qu”il n”existe pas d”algorithme déterministe efficace. Ces problèmes, notamment celui de l”estimation du volume d”un convexe en grande dimension, peuvent cependant être abordés par les méthodes de Monte-Carlo à base de chaînes de Markov (méthodes MCMC).
Les méthodes MCMC construisent une chaîne de Markov dont la distribution invariante est adaptée au problème à résoudre. Pour être dignes d”intérêt, la chaîne de Markov constitutive d”une méthode MCMC doit converger rapidement vers sa distribution d”équilibre. On abordera quelques méthodes d”études quantitatives de cette convergence vers l”équilibre (méthodes de couplage, méthodes spectrales, isopérimétrie sur les graphes).

Références

  • Durrett, Richard. Probability. Theory and examples. Wadsworth & Brooks/Cole. ix, 453 p. (1991).
  • Dacunha-Castelle, Didier; Duflo, Marie . Probabilités et statistiques. Tome 2 . Problèmes à temps mobile. Collection Mathématiques Appliquées pour la Maîtrise. Masson, Paris, 1982.
  • Jerrum, Mark. Mathematical foundations of the Markov chain Monte Carlo method. Habib, Michael (ed.) et al., Probabilistic methods for algorithmic discrete mathematics. Berlin: Springer. Algorithms Comb. 16, 116-165 (1998).
  • Lindvall, Torgny . Lectures on the coupling method. Corrected reprint of the 1992 original. (English) Mineola, NY: Dover Publications. xiv, 257
  • Robert, Christian and Casella, George Monte Carlo statistical methods. Springer Texts in Statistics. New York, NY: Springer. xxi, 507 p. 1999.
  • Norris, James. Markov chains. Cambridge University Press. 1998
  • Baldi, Paolo, Mazliak, Laurent et Priouret, Pierre. Martingales et chaînes de Markov. Hermann. 2001.

Les cours concernant l”espérance conditionnelle, les lois conditionnelles seront utilement complétés par la lecture des chapitres correspondants dans le livre de Durrett.

La présentation des propriétés de Markov fortes et simples pourra être elle aussi travaillée à partir du
livre de Durrett (qui présente des exemples très utiles pour fixer les idées).

Le petit livre de Lindvall propose une série de mises en oeuvre des techniques de couplage très convaincantes. L”usage des coefficients de Dobrushin n”est pas standard dans les livres d”introduction aux chaînes de Markov.

Les notions de transience, récurrence etc sont abordées dans tous les livres traitant des chaînes de Markov. Norris discute un peu plus que les autres l”introduction à la théorie du potentiel.

La dérivation des lois des grands nombres et éventuellement d”un théorème central limite pour les fonctionnelles additives des chaînes de Markov se trouve entre autres dans Durrett ou Dacunha-Castelle et Duflo. Elle est souvent traitée en liaison avec la théorie des martingales ou la théorie ergodique. Dacunha-Castelle et Duflo propose notamment une inégalité exponentielle de type Bennett pour les fonctionnelles additives des chaînes de Markov.

Les méthodes de Monte-Carlo sont introduites et illustrées dans l”ouvrage de Liu (notamment les techniques de Metropolis). Jerrum propose une mise en prespective dans le cadre de la théorie de la complexité calculatoire. Il montre notamment comment les méthodes MCMC permettent d”aborder des problèmes réputés difficiles issus de la physique statistique ou de la géométrie (volume d”un ensemble convexe).

L’étude de vitesse de mélange des chaînes de Markov est introduite de manière très lisible dans Jerrum (1998).

Logiciel R