Marche aléatoire sur un graphe. Étude asymptotique

Une puce se trouve à l'instant t=0 en un point appelé origine. Chaque seconde, elle peut faire un pas vers la gauche, ou vers la droite, ou vers le haut ou vers le bas, avec une égale probabilité. La puce décrit ce que l'on appelle une marche aléatoire dans le plan. Il y a beaucoup d'autres marches aléatoires possibles : dans l'espace, sur un graphe, avec des probabilités non identiques….

Les marches aléatoires modélisent de nombreux phénomènes physiques. Ainsi, Brown en 1820, puis Einstein en 1905, ont décrit de cette façon le mouvement d'une particule dans un fluide, soumis au choc de ses voisines. Cette étude a mené au mouvement brownien, la plus célèbre et la plus utilisée des marches aléatoires (il sert notamment pour décrire le cours d'une action).

Un célèbre théorème de Polya assure que, avec une probabilité 1, la marche aléatoire finit par repasser par l'origine avec une probabilité 1 : on dit que la marche aléatoire est récurrente. Ceci n'est plus vrai si la marche aléatoire se déroule dans l'espace!