Construction d'algorithmes à l'équilibre

On veut pouvoir construire une matrice de taille , stochastique et apériodique, vérifiant les conditions :

1. d'irréductibilité, c'est-à-dire
   
   
   

2. et de stationnarité de , c'est-à-dire
   
   
   
   et ceci à chaque étape de l'itération mais sans être obligé de la stocker. En général, la probabilité sera une mesure de Gibbs.

À la place de la condition de stationnarité, on exige parfois une condition plus forte, dite de bilan détaillé

qui est plus facile à vérifier [BINDER].

Afin de construire , on commence par une matrice stochastique irréductible arbitraire telle que si alors .

Pour tout ,

Évidente puisque entraîne que .

Pour tout fixé et tout on a

Or, si alors nécessairement

En écrivant

on constate que

ou bien

Il est à noter que l'expression pour la matrice d'acceptation donnée par le lemme précédent fait intervenir le rapport des mesures de Gibbs et non les mesures de Gibbs individuellement. Étant donné que , le dénominateur de normalisation disparaît dans le rapport. Ceci est très herexu parce que le dénominateur, nécessitant une somme sur toutes le configurations, est incalculable numériquement.

Il reste à montrer qu'il existe une fonction vérifiant . Or, en choisissant, par exemple, ou , on constate trivialement que de telles fonctions existent.

Il est facile de voir que si vérifie déjà la condition de bilan détaillé, alors . Dans le cas général, où ne vérifie pas la condition de balance détaillée, le coefficient d'acceptation est la modification minimale qu'il faut apporter à cette matrice stochastique pour obtenir une matrice admettant comme probabilité stationnaire.

On a

Étant donné que (pile) = (face) = , en appliquant la construction du lemme avec , on obtient

qui admet comme vecteur propre gauche correspondante à la valeur propre 1 le vecteur

On est donc sûr que