Marche aléatoire de longueur indéterminée

On se propose d'étudier un algorithme dynamique et local permettant de générer un échantillon statistique de marches au hasard sur un réseau régulier , .

Comme d'habitude, pour , on définit:  : les chemins de longueur ancrés à l'origine. L'espace des configurations pour ce problème sera l'ensemble qui représente l'ensemble de chemins de longueur indéterminée ancrés à l'origine. On parle de simulation dans un ensemble grand canonique

Pour tout chemin , le point est appelé point final du chemin. Pour , on note par l'ensemble de sites visités au cours de premiers mouvements .

Un sous-ensemble de à deux éléments, , , s'appelle lien du réseau si, et seulement si, ; représente l'ensemble de liens du réseau . Pour chaque marche , on définit l'ensemble de liens contigus au point final par

Pour et , on note par l'élément de obtenu par juxtaposition de et de .

Pour , , on note par le lien terminal, c'est à dire et par l'élément de obtenu par amputation du dernier lien.

Finalement, pour on note par la longueur du chemin .

Algorithme

COMMENCER par le chemin vide .
FIXER les constantes , (avec entier positif) et .

RÉPÉTER	fois
	CHOISIR	selon la loi uniforme.
	SI	ALORS
		CHOISIR	un lien selon la loi uniforme;
		CHOISIR	selon la loi uniforme;
		SI	ALORS
			SINON
		SINON
		CHOISIR	selon la loi uniforme;
		SI ET	ALORS
			SINON .

Questions

1. Calculer la cardinalité, , de l'ensemble .
2. L'algorithme précédent définit une chaîne de Markov sur dont la matrice de transition a comme éléments
   
   
   
   Déterminer les expressions pour , et , en termes de et .
3. Montrer que est une matrice stochastique.
4. Donner un argument qui permet de conclure sur l'irréductibilité de .
5. Montrer que la chaîne de Markov correspondante à la matrice est apériodique.
6. Pour tout chemin de longueur finie, montrer que , avec un facteur de normalisation, vérifie la condition de stationnarité .
7. Le facteur de normalisation s'écrit formellement où . Calculer explicitement. Que peut-on en conclure sur ? Discuter l'utilité de l'algorithme.
8. Proposer une modification minimale de la matrice de transition qui permet de générer un échantillon des marches faiblement sans recoupement (marches d'Edwards) [KOUKIOU ET AL. 1989, DE FORCRAND ET AL 1988], c'est à dire distribués selon , où est un facteur de normalisation et représente le nombre d'auto-intersections de .
9. Programmer l'algorithme de simulation des marches d'Edwards.
10. Faire une simulation pour estimer l'exposant critique .
11. Estimer l'intervalle de confiance de votre résultat.