Comportement asymptotique de l'algorithme

Il reste à établir la convergence de cet algorithme vers la probabilité uniforme sur .

1. La matrice est stochastique : En effet,
   
   
   
   
   
   

2. La matrice est apériodique : Il suffit de remarquer que pour une marche fixée et sans recoupement , l'élément diagonal s'annule, si, et seulement si, l'action de cette transformation génère une marche sans recoupement i.e. . Or, la configuration locale autour d'un vertex donné , avec , ne peut être, à un élément du groupe près, que sous une forme particulière qui contredit cette hypothèse. La figure suivante montre les configurations locales d'une marche en dimension 2, autour du vertex à des symétries globales près.
   unit=0.1cm (70,30) (0.1cm,0.1cm) (10,15)1.5 (20,15)1.5 (30,15)1.5 (10,15)(30,15) [tr](12,13) [tr](21,13) [tr](32,13) (50,15)1.5 (60,15)1.5 (60,25)1.5 (50,15)(60,15)(60,25) [tr](52,13) [tr](61,13) [bl](62,25)

   Dans chacune des situations, il existe toujours une transformation telle que si on ait ce qui contredit l'hypothèse .

3. La matrice est irréductible : Si elle était réductible, il y aurait un sous-espace fermé, c'est-à-dire un espace tel que si et alors , pour tout entier . Or, pour toute paire il existe toujours un tel que . Une démonstration formelle de cette affirmation est longue et pénible. Il est cependant simple de s'en convaincre par l'argument intuitif suivant. En supposant que toute marche peut être matérialisée par un fil de fer, il est facile de voir que celle-ci peut toujours être dépliée pour devenir un segment de droite en appliquant une suite d'opérations qui respectent à la fois la contrainte de non recoupement et la condition d'ancrage à l'origine. Il en est de même pour toute autre marche . En appliquant donc successivement les opérations sur on obtient .
4. La matrice est bistochastique : Puisque si alors , on obtient
   
   
   

Les itérées successives de la matrice tendent vers une matrice stable. Par ailleurs, on vérifie que la probabilité est stationnaire pour la matrice , c'est-à-dire

Par normalisation on obtient alors

En conclusion, les marches visitées par la chaîne de Markov fournissent un échantillonnage uniforme de .