Introduction

Quelques rares cas d'école mis à part, on ne sait pas résoudre analytiquement la plupart des problèmes mathématiques posés par la vie de tous les jours, que ce soit en science fondamentale, en ingénierie, en économie, en sociologie ou en théorie de la décision. Or des résultats quantitatifs de plus en plus précis sont exigés par nos sociétés post-industrielles ; ceci nous a conduit à introduire des modèles -- parfois simplifiés -- et des méthodes numériques pour répondre aux impératifs de la science appliquée, de l'industrie et de la société. Ces méthodes, inventées pour la plupart dans la décennie de 1950, n'ont pris d'essor considérable ni été appliquées à une multitude de problèmes pratiques que durant les dernières années, lorsque, avec l'amélioration des performances des ordinateurs, il est devenu plus efficace de simuler numériquement le comportement d'un système complexe que de l'observer expérimentalement.

Parmi les méthodes d'étude numérique, on va étudier uniquement celle que l'on appelle « simulation stochastique » ou « simulation Monte Carlo » [#!MetRosRosTelTel!#]. Une définition vague de cette méthode est : « méthode numérique de résolution des problèmes qui fait usage de nombres aléatoires »^1.1. Cette définition se précisera au fil du cours, signalons cependant une distinction entre les méthodes Monte Carlo et les autres méthodes numériques comme les méthodes de Newton pour la résolution des équations algébriques, Runge-Kutta pour la résolution d'équations différentielles, élimination de Gauss-Seidel pour la diagonalisation des matrices etc. ; celles-ci sont des méthodes déterministes tandis que la méthode Monte Carlo est intrinsèquement stochastique, même lorsqu'il s'agit de résoudre un problème déterministe. L'aspect stochastique de la méthode Monte Carlo peut être uniquement une astuce pour traiter un problème purement déterministe ou bien provenir vraiment d'une modélisation stochastique d'un problème sur lequel on dispose d'une information lacunaire. Par exemple, on peut utiliser une approche Monte Carlo pour calculer une intégrale du type

avec  ; il s'agit, dans ce cas, d'un moyen de calcul adapté à un problème déterministe. Mais une approche Monte Carlo est nécessaire pour étudier le comportement d'une file d'attente ; dans ce cas, la stochasticité est intrinsèque au problème puisqu'il est impossible de connaître a priori le temps pendant lequel chaque client occupera le serveur.

L'aléa inhérent à la méthode Monte Carlo lui confère toutes les caractéristiques d'une science expérimentale. Ainsi, toute réponse donnée par une méthode Monte Carlo est assortie d'une incertitude de nature statistique : on peut énoncer des résultats seulement sous la forme « avec une probabilité donnée -- que l'on calcule -- le résultat exact se trouve dans un certain intervalle de confiance -- que l'on détermine ». De la même façon que l'on exige que les expériences physiques soient reproductibles pour être homologuées, les expériences Monte Carlo doivent remplir certaines conditions de reproductibilité.

Une des caractéristiques du problème qui dicte le choix de la méthode est sa complexité. La complexité algorithmique peut être définie comme le nombre minimal d'opérations élémentaires nécessaires pour la résolution exhaustive du problème. Ainsi, selon la complexité du problème à étudier, on verra que l'on doit utiliser des méthodes Monte Carlo adaptées. On distingue ainsi deux grandes familles de simulations, les simulations statiques (ou directes ou indépendantes) pour des problèmes d'une complexité réduite et les simulations dynamiques (ou corrélées) pour des problèmes de grande complexité. Traditionnellement, la résolution par simulation Monte Carlo dynamique est réservée aux problèmes appelés NP-complets (le nombre d'opérations croît plus vite que tout polynôme du nombre des constituants élémentaires). Le nombre de degrés de liberté du système -- c'est à dire le nombre de coordonnées nécessaires pour décrire complètement l'état du système -- dépend à son tour de la dimension du problème.

Il existe plusieurs variantes de la méthode Monte Carlo qui doivent être choisies d'après les caractéristiques fondamentales du système à étudier. En définitive, il y a autant de variantes que de problèmes à étudier ; on peut cependant distinguer certains critères qui servent à choisir la variante adaptée :

• Caractère stationnaire ou transitoire : selon que l'état du système reste constant ou évolue avec le temps on doit utiliser une méthode à l'équilibre ou hors équilibre.
• Caractère déterministe ou aléatoire de l'environnement : le système que l'on doit décrire dépend de certains paramètres externes, souvent ajustables, dont les valeurs déterminent son état. Ces paramètres jouent le rôle de l'environnement. Quand les valeurs de ces paramètres sont fixées une fois pour toutes, on parle d'environnement déterministe. La situation où l'environnement est décrit par un aléa, indépendant ou dépendant de l'aléa intrinsèque à la méthode Monte Carlo, peut aussi se présenter dans des cas concrets ; on parle alors de système désordonné.
• Caractère discret ou continu : si l'état du système est indexé par un ensemble discret, le codage sur ordinateur est presque immédiat, si, par contre, il est indexé par un ensemble continu, une discrétisation est, le plus souvent, nécessaire préalablement à sa simulation. La procédure de discrétisation est une procédure conventionnelle pour les systèmes à environnement déterministe ; elle nécessite parfois certaines finesses dans le cas de l'environnement aléatoire (comme, par exemple, dans le cadre de l'intégration stochastique).

Dans la suite, on donne un aperçu (ni orthogonal, ni exhaustif) des problèmes-type qui peuvent être traités par simulation Monte Carlo directe : Simulation de fonctionnement (rayonnement cosmique, radioactivité, files d'attente, diffusion neutronique dans des centrales nucléaires) ; anticipation (bourse, modèles sociologiques, démoscopie) ; test d'hypothèses extrêmes (fissures dans des structures architecturales, cascade des pannes) ; cryptographie (codes asymétriques, signature électronique); calcul numérique (calcul d'intégrales multidimensionnelles, intégration stochastique, équations différentielles stochastiques).

Il est à noter que, malgré l'intérêt pratique énorme que présentent ces problèmes, la simulation et l'analyse des résultats ne présentent pas de difficulté particulière ; leur traitement théorique est assez simple. Il en va autrement des simulations dynamiques, utilisées pour des systèmes complexes. Qu'il s'agisse d'un système en équilibre ou en évolution, s'il est complexe, il admet une multitude d'états microscopiques de telle sorte qu'il est impossible d'explorer toutes les éventualités. On introduit alors une description probabiliste du système à l'aide d'une fonction coût sur l'espace des configurations qui tend à raréfier les configurations à coût élevé. Finalement, on se contente souvent des solutions proches de l'optimale. Quelques problèmes-type sont donnés ici : quasi-totalité des problèmes en physique (coût = énergie), optimisation combinatoire, macro-économie, restauration d'images numérisées brouillées, neurophysiologie et processus d'apprentissage, propagation des épidémies et des MST.

Il y a deux idées fondamentales sous-jacentes à toute simulation stochastique. La première idée est que le système, aussi complexe soit-il, peut être décrit par un petit nombre de variables qui sont les espérances par rapport à une probabilité sur ses états microscopiques. Cette idée nous vient de la physique et plus précisement de la mécanique statistique où l'on sait que l'état microscopique d'un volume de 1 cm d'eau est décrit par la donnée d'environ variables (composantes de positions et de vitesses des molécules d'eau qui sont contenues dans un volume de 1 cm) mais la description macroscopique de ce système nécessite quelques variables, telles la température ou la pression, et cette description nous fournit toute l'information essentielle sur le système. Il s'avère que ces variables macroscopiques peuvent être calculées comme des espérances par rapport à une probabilité sur l'ensemble des états microscopiques connue sous le nom de mesure de Gibbs. Le formalisme qui permet de décrire précisement ces notions est le formalisme de Gibbs.

La deuxième idée-clè est que le calcul des espérances qui vont nous intéresser peut être effectué par une moyenne ergodique^1.2.

L'expression la plus simple de la théorie ergodique est le théorème de grands nombres mais elle va bien au-delà des suites de variables aléatoires indépendantes.

On voit donc que l'étude numérique d'un système passe par une étape de modélisation stochastique qui fait intervenir, si le système est complexe, le formalisme de Gibbs et par une étape de simulation stochastique où les espérances sont exprimées en termes de moyennes ergodiques.

Il se trouve que le formalisme de Gibbs et la mécanique statistique sont, de nos jours, à leur tour obtenus comme un résultat de la théorie ergodique. D'un autre côté, la génération de suites de variables aléatoires, nécessaires pour la simulation stochastique et le calcul des moyennes ergodiques, est faite aujourd'hui à partir de systèmes dynamiques dont les mesures invariantes sont décrites en théorie ergodique par des mesures de Gibbs. Finalement, la théorie probabiliste de l'information est reliée au formalisme de Gibbs et aux systèmes dynamiques.

L'objet de ce cours est donc le formalisme de Gibbs et la théorie ergodique et leurs applications en modélisation et simulation stochastiques. Une approche unificatrice sera tentée où les différentes interconnexions entre diverses disciplines -- qui sont habituellement présentées comme étant très éloignées -- telles que la mécanique statistique, la théorie ergodique, la théorie probabiliste de l'information, la modélisation de grands systèmes, les processus markoviens, le traitement du signal, l'optimisation combinatoire, etc., seront abordées par le formalisme de Gibbs.