Processus aléatoires et applications

Les chaines de Markov sont intuitivement très simples à définir. Un système peut admettre un certain nombre d'états différents. L'état change au cours du temps discret. A chaque changement, le nouvel état est choisi avec une distribution de probabilité fixée au préalable, et ne dépendant que de l'état présent.

Cette manière de faire est toutefois assez compliquée, et devient rapidement impossible à mettre en Å?uvre quand la taille du labyrinthe augmente. Dans la suite, nous allons d´développer une m´méthode plus efficace pour résoudre le problème, basé sur une représentation matricielle.

Une alternative est d'utiliser un algorithme dit de Métropolies. Au lieu de parcourir toutes les configurations possibles de X, on n'en parcourt qu'un nombre limité, de manière bien choisie, à l'aide d'une chaine de Markov. Pour cela, on part dans une configuration initiale Ï?, puis on transforme cette configuration en retournant un spin choisi au hasard.

Plus précisément, on n'opère cette transition qu'avec une certaine probabilité, qui dépend de la différence dâ??énergie entre les configurations de départ et d'arrivée. L'idée est que si les probabilités de transition sont bien choisies, alors la chaine de Markov va échantillonner l'espace de configuration de telle manière qu'il suffira de lui faire parcourir une petite fraction de toutes les configurations possibles pour obtenir une bonne approximation de l'aimantation.

On peut tenter de trouver une solution approchée par approximations successives. Partant d'un circuit initial, on le modifie légèrement, par exemple en échangeant deux villes. Si cette modification raccourcit la longueur du circuit, on continue avec le circuit modifie. Si elle le rallonge, par contre, on rejette la modification et on en essaie une autre.

Le problème avec cette m´méthode est que le système peut se retrouver piège dans un minimum local, qui est très différent du minimum global recherche de la longueur. On peut en effet se retrouver "bloque" dans un circuit plus court que tous ses voisins (obtenus en permutant deux villes), mais une permutation de plus de deux villes pourrait raccourcir le circuit.

Une variante plus efficace de cette méthode est celle du recuit simule. Dans ce cas, on ne rejette pas toutes les modifications qui allongent le circuit, mais on les accepte avec une certaine probabilité, qui décroit avec l'allongement. De cette manière, le processus peut s'´échapper du minimum local et a une chance de trouver un minimum plus profond.