Simulations dynamiques

On a étudié, au chapitre précédent, des méthodes qui permettent de construire un modèle comme un champ de Markov sur un graphe décrit par une certaine probabilité . Dans ce chapitre on va construire des algorithmes qui nous permettront d'engendrer des chaînes de Markov sur l'espace de champs de Markov, , qui convergent à la probabilité .

Le problème de la construction de l'algorithme peut être posé de deux manières différentes :

1. La forme fonctionnelle que doit avoir la probabilité sur est connue ; on cherche alors à construire une chaîne de Markov sur dont la matrice de transition admet comme vecteur propre gauche à valeur propre 1. Dans ce cas, l'algorithme décrit une dynamique (qui peut être fictive) sur l'espace et on exige qu'elle aboutisse le plus efficacement possible à .
2. On connaît les détails de la dynamique locale. On construit alors la matrice des transitions correspondante, , et l'on cherche la probabilité qui stabilise la chaîne. Dans ce cas, la dynamique sur l'espace est réelle et l'inconnue est l'état d'équilibre correspondant.

Dans les deux exemples précédents, l'espace est très petit et tous les calculs peuvent être explicitement effectués. Dans des cas plus réalistes, est de l'ordre de et il est donc exclu d'effectuer les calculs à la main. On va donc introduire un algorithme systématique qui permettra de construire une chaîne de Markov avec les propriétés voulues sur un espace arbitraire .