Aspects dynamiques des algorithmes à l'équilibre

On a vu qu'une chaîne de Markov irréductible et apériodique dont la matrice de transition admet comme probabilité stationnaire converge, dans le sens que

Par conséquent, les états , successivement visités par cette chaîne, offrent un échantillonnage de l'espace selon la probabilité . Si est une fonction de , on peut se servir du théorème ergodique pour estimer l'espérance de

par sa moyenne ergodique

Cependant, toute simulation s'effectuant sur ordinateur, la « limite » ne sera qu'un entier « grand . Il est donc très important de connaître de manière théorique et a priori avec quelle précision on a approché cette limite c'est-à-dire connaître la vitesse de convergence de l'algorithme. On a déjà vu au chapitre que la chaîne converge vers la probabilité stationnaire avec une vitesse de l'ordre de où est le coefficient d'ergodicité de Dobrushin pour la chaîne. Dans ce chapitre on va relier la vitesse de convergence à une autre caractéristique de la matrice de transition, à savoir son rayon spectral [#!Sid!#].

Le but de la simulation étant d'estimer certaines grandeurs caractérisant le système que l'on étudie, il est nécessaire par ailleurs de pouvoir estimer leurs intervalles de confiance. On verra dans ce chapitre que l'intervalle de confiance dépend d'une autre caractéristique dynamique de l'algorithme qui est son temps d'auto-corrélation [#!Sok!#].

De manière assez surprenante donc, pour étudier un phénomène statique (c'est-à-dire à l'équilibre) il est nécessaire de connaître certains éléments dynamiques de sa description. Ce chapitre étudie ceux des aspects dynamiques des algorithmes qui permettent de décider du bon usage de l'algorithme pour l'étude des phénomènes statiques. Malgré le fait que les chaînes qui vont nous intéresser sont à espace d'états fini, l'effort supplémentaire demandé pour établir les résultats au cas d'un espace dénombrable est minime. C'est pourquoi les résultats sont présentés dans le cas légèrement plus général que celui exigé stricto sensu pour les simulations numériques.