Ces notes sont essentiellement basées sur un cours de troisième
cycle donné
a l'université Paul Sabatier , Toulouse III,
depuis 1998 et sur un enseignement
de cinquième année présenté à l'Institut National des Sciences
Appliquées (INSA ) de Toulouse depuis 1999.
Elles ont pour objectif d'introduire les principales méthodes de
simulation de variables aléatoires et la modélisation stochastique
d'une classe assez générale d'algorithmes stochastiques à temps
discret.
Les chapitres sont indépendants les uns des autres. Dans un premier
chapitre introductif
nous rappelons brièvement
les principales notions sur les chaines de Markov et la notion de
martingale. Les deux dernières
sections de ce premier chapitre sont consacrées
à la description de principes généraux probabilistes sur
lesquels
sont basés les algorithmes markoviens présentés dans la suite du
cours.
L'un concerne les régimes stationnaires et les mesures invariantes
d'une chaine de Markov. On introduit à ce titre l'algorithme
universel de Métropolis-Hastings qui donnera lieu plus tard
au recuit simulé. On décrit aussi l'échantillonneur de Gibbs,
la mesure de Boltzmann-Gibbs et une description universelle d'une
mesure invariante due à Bott et Mayberry dans le cadre des espaces
finis. Le second et ultime principe concerne les méthodes dites de
Monte-Carlo et les systèmes de particules en interactions. Ces
techniques récentes d'approximation particulaires de problèmes
d'estimation non linéaires tels le filtrage de signaux sont basées
sur le même principe de construction que celui des systèmes
de particules en interactions utilisés en biologie, en physique
et en mécanique statistique. Dans cette ultime section nous ne ferons
qu'effleurer ces modèles mais nous dégagerons un principe
universel de construction de tels schémas numériques. On
précisera
certaines propriétés et la convergence de tels algorithmes
dans le cadre du filtrage non linéaire et des algorithmes
génétiques.
Le second chapitre décrit en détail les méthodes générales
et universelles de simulation de lois de probabilités classiques.
Ces techniques seront par la suite essentielles à la simulation effective
des algorithmes markoviens sur ordinateur. Nous consacrerons aussi une
partie
de ce chapitre à la simulation de statistiques
d'ordre uniformes par des lois exponentielles. Ces techniques
de simulation seront très utiles pour simuler les
étapes de sélection dans l'évolution des algorithmes
génétiques.
Le troisième chapitre est le corps de ce cours. Nous avons choisi
de présenter en détail les six algorithmes qui nous ont
semblé les plus représentatifs parmi ceux utilisés en pratique:
les fonctions itérées stochastiques, les algorithmes à pas
décroissants de Robbins-Monro, le filtre de Kalman-Bucy,
les algorithmes génétiques et leurs processus historiques ou
généalogiques.
Chacun de ces algorithmes est un outil d'approximation numérique
d'un problème d'estimation spécifique:
approximation d'une mesure invariante, description d'images fractales,
recherche d'une ligne de niveau, inversion
d'une fonction, recherche des extrema globaux,
estimation/filtrage de signaux et lissage/estimation de
trajectoires.
Les conditions d'application, les
modèles markoviens et la simulation de chacun sont décrits dans
tous les détails. La plupart des thèmes et sujets de travaux
pratiques proposés sont issus de rapports techniques et/ou
d'articles récents.
Le chapitre final est consacré à l'analyse de la convergence
des algorithmes
présentés dans le chapitre précédent.
Nous n'aborderons qu'un aspect limité de chaque algorithme
et
nous renvoyons le lecteur aux ouvrages classiques sur chaque thème.
Nous avons choisi de présenter les outils et les preuves complètes
de convergence les plus simples
et ne nécessitant pas l'introduction d'un cadre
mathématique trop spécifique. Chaque section
propose ainsi une analyse simple et séparée de chaque
algorithme et peut ainsi être lue indépendamment des autres.
I Modélisation Stochastique 1 Introduction 2 Chaînes de Markov 3 Martingales 4 Mesures invariantes et régimes stationnaires 4-1 Description de Bott-Mayberry 4-2 Mesure de Gibbs-Boltzmann et Modèle d'Ising 4-3 Transition de Métropolis-Hastings 4-4 Echantillonneur de Gibbs 5 Méthodes particulaires stochastiques 4-1 Méthodes de Monte-Carlo 4-2 Systèmes de particules en interaction
II Méthodes de simulation 1 Lois uniformes 2 Lois discrètes et multinomiales 3 Changement de variables 4 Inversion 5 Acceptation/rejet 6 Inter-temps exponentiels 6-1 Loi de Poisson 6-2 Statistique d'ordre uniforme
III Algorithmes stochastiques 1 Introduction 2 Fonctions itérées stochastiques 2-1 Description du modèle 2-2 Exemples et applications 3 Algorithme de Robbins-Monro 3-1 Algorithmes déterministes à pas décroissants 3-2 Modèle markovien 3-3 Exemples et applications 4 Recuit simulé 4-1 Présentation du recuit simulé 4-2 Modèle markovien 4-3 Mesure de Gibbs-Boltzmann 4-4 Exemples et applications 5 Filtrage linéaire et filtre de Kalman-Bucy 5-1 Variables aléatoires gaussiennes 5-2 Filtre de Kalman-Bucy 5-3 Applications 6 Filtrage non linéaire et algorithme génétique 6-1 Description du modèle 6-2 Equations non linéaires du filtrage 6-3 Description de l'algorithme génétique 6-4 Description de quelques variantes 6-5 Exemples et applications 7 Estimation de chemins et lissage de signaux 7-1 Description du problème 7-2 Description des modèles 7-3 Processus historique et arbre généalogique
IV Convergence d'algorithmes markoviens 1 Convergence de martingales 1-1 Description d'une limite presque sure 1-2 Etude des oscillations d'une martingale 1-3 Théorèmes de convergence 1-4 Convergence de l'algorithme de Robbins-Monro 2 Convergence faible de mesures 2-1 Métrique de Fortet-Mourier 2-2 Critères de tension et compacité 2-3 Métrique de Hutchinson 2-4 Convergence de fonctions itérées stochastiques 3 Convergence en variation totale 3-1 Coefficient de contraction d'un noyau markovien 3-2 Théorème de Dobrushin 3-3 Convergence du recuit simulé 4 Convergence de méthodes particulaires 4-1 Loi forte des grands nombres 4-2 Systèmes de particules en interaction 4-3 Comportement asymptotique 4-4 Formules de Feynman-Kac 4-5 Modèles de champs moyens 4-6 Modèle de McKean de gaz maxwelliens
