Promenade aléatoire

En mathématiques , une marche aléatoire , parfois appelée marche de l'ivrogne , est un processus stochastique qui décrit un chemin constitué d'une succession d' étapes aléatoires sur un espace mathématique .

Un exemple élémentaire de marche aléatoire est la marche aléatoire sur la droite des nombres entiers qui démarre à 0 et se déplace à chaque étape de +1 ou −1 avec une probabilité égale . D'autres exemples incluent le chemin tracé par une molécule lorsqu'elle se déplace dans un liquide ou un gaz (voir mouvement brownien ), le chemin de recherche d'un animal en quête de nourriture , ou le prix d'une action fluctuante et la situation financière d'un joueur . Les marches aléatoires ont des applications en ingénierie et dans de nombreux domaines scientifiques, notamment l'écologie , la psychologie , l'informatique , la physique , la chimie , la biologie , l'économie et la sociologie . Le terme marche aléatoire a été introduit pour la première fois par Karl Pearson en 1905.

Des réalisations de marches aléatoires peuvent être obtenues par simulation de Monte Carlo .

Un modèle de marche aléatoire populaire est celui d'une marche aléatoire sur un réseau régulier, où à chaque étape, l'emplacement saute vers un autre site selon une distribution de probabilité. Dans une marche aléatoire simple , l'emplacement ne peut sauter que vers les sites voisins du réseau, formant ainsi un chemin de réseau . Dans une marche aléatoire symétrique simple sur un réseau localement fini, les probabilités que l'emplacement saute vers chacun de ses voisins immédiats sont les mêmes. L'exemple le mieux étudié est la marche aléatoire sur le réseau entier d -dimensionnel (parfois appelé réseau hypercubique) .

Si l'espace d'état est limité à des dimensions finies, le modèle de marche aléatoire est appelé marche aléatoire symétrique bordée simple , et les probabilités de transition dépendent de l'emplacement de l'état car sur les états de marge et de coin, le mouvement est limité.

Un exemple élémentaire de marche aléatoire est la marche aléatoire sur la droite des nombres entiers , qui commence à 0 et à chaque étape se déplace de +1 ou −1 avec une probabilité égale.

Cette marche peut être illustrée comme suit. Un marqueur est placé à zéro sur la droite numérique et une pièce de monnaie est lancée. Si elle tombe sur pile, le marqueur est déplacé d'une unité vers la droite. Si elle tombe sur face, le marqueur est déplacé d'une unité vers la gauche. Après cinq lancers, le marqueur peut maintenant être sur -5, -3, -1, 1, 3, 5. Avec cinq lancers, trois faces et deux piles, dans n'importe quel ordre, il tombera sur 1. Il y a 10 façons d'atterrir sur 1 (en lançant trois faces et deux piles), 10 façons d'atterrir sur −1 (en lançant trois piles et deux faces), 5 façons d'atterrir sur 3 (en lançant quatre faces et une pile), 5 façons d'atterrir sur −3 (en lançant quatre piles et une face), 1 façon d'atterrir sur 5 (en lançant cinq faces) et 1 façon d'atterrir sur −5 (en lançant cinq piles). Voir la figure ci-dessous pour une illustration des résultats possibles de 5 lancers.

Pour définir formellement cette marche, prenons des variables aléatoires indépendantes , où chaque variable est soit 1 soit −1, avec une probabilité de 50 % pour l'une ou l'autre valeur, et posons et La série est appelée marche aléatoire simple sur . Cette série (la somme de la séquence de −1 et de 1) donne la distance nette parcourue, si chaque partie de la marche est de longueur un. L' espérance de est nulle. C'est-à-dire que la moyenne de tous les lancers de pièces s'approche de zéro lorsque le nombre de lancers augmente. Cela découle de la propriété d'additivité finie de l'espérance :

Un calcul similaire, utilisant l'indépendance des variables aléatoires et le fait que , montre que :

Cela suggère que la distance de translation attendue après n étapes devrait être de l'ordre de . En fait,

Pour répondre à la question de savoir combien de fois une marche aléatoire franchira une ligne de démarcation si on lui permet de continuer à marcher indéfiniment, une simple marche aléatoire traversera chaque point un nombre infini de fois. Ce résultat a plusieurs noms : le phénomène de franchissement de niveau , la récurrence ou la ruine du joueur . La raison du dernier nom est la suivante : un joueur avec une somme d'argent finie finira par perdre lorsqu'il jouera à un jeu équitable contre une banque avec une somme d'argent infinie. L'argent du joueur effectuera une marche aléatoire, et il atteindra zéro à un moment donné, et le jeu sera terminé.

Si a et b sont des entiers positifs, alors le nombre attendu d'étapes jusqu'à ce qu'une marche aléatoire simple unidimensionnelle commençant à 0 atteigne d'abord b ou − a est ab . La probabilité que cette marche atteigne b avant − a est , ce qui peut être déduit du fait que la marche aléatoire simple est une martingale . Et ces espérances et probabilités d'atteindre b peuvent être calculées dans la chaîne de Markov générale de la marche aléatoire unidimensionnelle.

Certains des résultats mentionnés ci-dessus peuvent être dérivés des propriétés du triangle de Pascal . Le nombre de marches différentes de n étapes où chaque étape est +1 ou −1 est 2 ⁿ . Pour la marche aléatoire simple, chacune de ces marches est également probable. Pour que S _n soit égal à un nombre k, il est nécessaire et suffisant que le nombre de +1 dans la marche dépasse de k ceux de −1 . Il s'ensuit que +1 doit apparaître ( n + k )/2 fois parmi les n étapes d'une marche, donc le nombre de marches qui satisfont est égal au nombre de façons de choisir ( n + k )/2 éléments d'un ensemble de n éléments, noté . Pour que cela ait un sens, il est nécessaire que n + k soit un nombre pair, ce qui implique que n et k sont soit tous les deux pairs, soit tous les deux impairs. Par conséquent, la probabilité que soit égale à . En représentant les entrées du triangle de Pascal en termes de factorielles et en utilisant la formule de Stirling , on peut obtenir de bonnes estimations de ces probabilités pour de grandes valeurs de .

Si l'espace est limité à + pour plus de concision, le nombre de façons dont une marche aléatoire atterrira sur un nombre donné ayant cinq lancers peut être affiché comme {0,5,0,4,0,1}.

Cette relation avec le triangle de Pascal est démontrée pour de petites valeurs de n . À zéro tour, la seule possibilité sera de rester à zéro. Cependant, à un tour, il y a une chance d'atterrir sur −1 ou une chance d'atterrir sur 1. À deux tours, un marqueur à 1 pourrait se déplacer vers 2 ou revenir à zéro. Un marqueur à −1 pourrait se déplacer vers −2 ou revenir à zéro. Il y a donc une chance d'atterrir sur −2, deux chances d'atterrir sur zéro et une chance d'atterrir sur 2.

Le théorème central limite et la loi du logarithme itéré décrivent des aspects importants du comportement des marches aléatoires simples sur . En particulier, le premier implique que lorsque n augmente, les probabilités (proportionnelles aux nombres de chaque ligne) se rapprochent d'une distribution normale .

Pour être précis, sachant que , et en utilisant la formule de Stirling, on a

En fixant l'échelle , pour fixe, et en utilisant l'expansion lorsque s'annule, il s'ensuit

en prenant la limite (et en observant que cela correspond à l'espacement de la grille d'échelle) on trouve la densité gaussienne . En effet, pour une variable aléatoire absolument continue de densité elle a , avec correspondant à un espacement infinitésimal.

En généralisation directe, on peut considérer les marches aléatoires sur les réseaux cristallins (graphes abéliens à nombre infini de couches recouvrant des graphes finis). En fait, il est possible d'établir le théorème central limite et le théorème des grandes déviations dans ce cadre.

Une marche aléatoire unidimensionnelle peut également être considérée comme une chaîne de Markov dont l'espace d'état est donné par les entiers Pour un certain nombre p satisfaisant , les probabilités de transition (la probabilité P _i,j de passer de l'état i à l'état j ) sont données par

La marche aléatoire hétérogène tire à chaque pas de temps un nombre aléatoire qui détermine les probabilités de saut locales puis un nombre aléatoire qui détermine la direction réelle du saut. La question principale est la probabilité de rester dans chacun des différents sites après les sauts, et dans la limite de cette probabilité lorsque celle-ci est très grande.

En dimension supérieure, l'ensemble des points parcourus aléatoirement possède des propriétés géométriques intéressantes. En fait, on obtient une fractale discrète , c'est-à-dire un ensemble qui présente une auto-similarité stochastique à grande échelle. À petite échelle, on peut observer une "irrégularité" résultant de la grille sur laquelle la marche est effectuée. La trajectoire d'une marche aléatoire est l'ensemble des points parcourus, considérés comme un ensemble sans tenir compte du moment où la marche est arrivée au point. En une dimension, la trajectoire est simplement l'ensemble des points compris entre la hauteur minimale et la hauteur maximale atteinte par la marche (les deux sont, en moyenne, de l'ordre de ).

Pour visualiser le cas bidimensionnel, on peut imaginer une personne marchant au hasard dans une ville. La ville est effectivement infinie et disposée dans une grille carrée de trottoirs. À chaque intersection, la personne choisit au hasard l'un des quatre itinéraires possibles (y compris celui d'origine). Formellement, il s'agit d'une marche aléatoire sur l'ensemble de tous les points du plan de coordonnées entières .

Pour répondre à la question de savoir si une personne revient un jour au point de départ de sa marche, il s'agit de l'équivalent bidimensionnel du problème du passage à niveau évoqué ci-dessus. En 1921, George Pólya a prouvé que la personne y parviendrait presque sûrement dans une marche aléatoire bidimensionnelle, mais pour 3 dimensions ou plus, la probabilité de revenir au point d'origine diminue à mesure que le nombre de dimensions augmente. En 3 dimensions, la probabilité diminue à environ 34 %. Le mathématicien Shizuo Kakutani était connu pour faire référence à ce résultat avec la citation suivante : « Un homme ivre retrouvera son chemin vers la maison, mais un oiseau ivre peut se perdre à jamais ».

La probabilité de récurrence est en général , qui peut être dérivée en générant des fonctions ou un processus de Poisson.

Une autre variante de cette question, également posée par Pólya, est la suivante : « Si deux personnes partent du même point de départ, se rencontreront-elles à nouveau ? » On peut montrer que la différence entre leurs emplacements (deux marches aléatoires indépendantes) est également une marche aléatoire simple, de sorte qu'elles se rencontrent presque sûrement à nouveau dans une marche à 2 dimensions, mais pour 3 dimensions et plus, la probabilité diminue avec le nombre de dimensions. Paul Erdős et Samuel James Taylor ont également montré en 1960 que pour des dimensions inférieures ou égales à 4, deux marches aléatoires indépendantes partant de deux points donnés ont presque sûrement une infinité d'intersections, mais pour des dimensions supérieures à 5, elles ne se croisent presque sûrement qu'un nombre fini de fois.

La fonction asymptotique d'une marche aléatoire bidimensionnelle lorsque le nombre d'étapes augmente est donnée par une distribution de Rayleigh . La distribution de probabilité est une fonction du rayon à partir de l'origine et la longueur de l'étape est constante pour chaque étape. Ici, la longueur de l'étape est supposée être de 1, N est le nombre total d'étapes et r est le rayon à partir de l'origine.

Un processus de Wiener est un processus stochastique dont le comportement est similaire à celui du mouvement brownien , phénomène physique de diffusion d'une minuscule particule dans un fluide. (Le processus de Wiener est parfois appelé « mouvement brownien », bien qu'il s'agisse à proprement parler d'une confusion entre un modèle et le phénomène modélisé.)

Un processus de Wiener est la limite d'échelle d'une marche aléatoire en dimension 1. Cela signifie que s'il existe une marche aléatoire avec de très petits pas, il existe une approximation d'un processus de Wiener (et, moins précisément, d'un mouvement brownien). Pour être plus précis, si la taille du pas est ε, il faut effectuer une marche de longueur L /ε ² pour approcher une longueur de Wiener de L . Lorsque la taille du pas tend vers 0 (et que le nombre de pas augmente proportionnellement), la marche aléatoire converge vers un processus de Wiener dans un sens approprié. Formellement, si B est l'espace de tous les chemins de longueur L avec la topologie maximale, et si M est l'espace de mesure sur B avec la topologie de norme, alors la convergence est dans l'espace M . De même, un processus de Wiener en plusieurs dimensions est la limite d'échelle d'une marche aléatoire dans le même nombre de dimensions.

Une marche aléatoire est une fractale discrète (une fonction de dimensions entières ; 1, 2, ...), mais une trajectoire de processus de Wiener est une véritable fractale, et il existe un lien entre les deux. Par exemple, faites une marche aléatoire jusqu'à ce qu'elle atteigne un cercle de rayon r fois la longueur du pas. Le nombre moyen de pas qu'elle effectue est r ² . Ce fait est la version discrète du fait qu'une marche de processus de Wiener est une fractale de dimension Hausdorff 2.

En deux dimensions, le nombre moyen de points que la même marche aléatoire possède sur la frontière de sa trajectoire est r ^4/3 . Cela correspond au fait que la frontière de la trajectoire d'un processus de Wiener est une fractale de dimension 4/3, un fait prédit par Mandelbrot à l'aide de simulations mais prouvé seulement en 2000 par Lawler , Schramm et Werner .

Un processus de Wiener présente de nombreuses symétries qui ne sont pas présentes dans une marche aléatoire. Par exemple, une marche de processus de Wiener est invariante aux rotations, mais la marche aléatoire ne l'est pas, puisque la grille sous-jacente ne l'est pas (la marche aléatoire est invariante aux rotations de 90 degrés, mais les processus de Wiener sont également invariants aux rotations de 17 degrés, par exemple). Cela signifie que dans de nombreux cas, les problèmes sur une marche aléatoire sont plus faciles à résoudre en les traduisant en un processus de Wiener, en résolvant le problème à cet endroit, puis en le traduisant en arrière. D'un autre côté, certains problèmes sont plus faciles à résoudre avec des marches aléatoires en raison de leur nature discrète.

La marche aléatoire et le processus de Wiener peuvent être couplés , c'est-à-dire manifestés sur le même espace de probabilités de manière dépendante qui les oblige à être assez proches. Le couplage le plus simple est le plongement de Skorokhod , mais il existe des couplages plus précis, comme le théorème d'approximation de Komlós–Major–Tusnády .

La convergence d'une marche aléatoire vers le processus de Wiener est contrôlée par le théorème central limite et par le théorème de Donsker . Pour une particule en position fixe connue à t = 0, le théorème central limite nous indique qu'après un grand nombre d' étapes indépendantes dans la marche aléatoire, la position du marcheur est distribuée selon une distribution normale de variance totale :

où t est le temps écoulé depuis le début de la marche aléatoire, est la taille d'une étape de la marche aléatoire et est le temps écoulé entre deux étapes successives.

Cela correspond à la fonction de Green de l' équation de diffusion qui contrôle le processus de Wiener, ce qui suggère qu'après un grand nombre d'étapes, la marche aléatoire converge vers un processus de Wiener.

En 3D, la variance correspondant à la fonction de Green de l'équation de diffusion est :

En égalisant cette quantité avec la variance associée à la position du marcheur aléatoire, on obtient le coefficient de diffusion équivalent à considérer pour le processus asymptotique de Wiener vers lequel la marche aléatoire converge après un grand nombre d'étapes : (valable uniquement en 3D).

Les deux expressions de la variance ci-dessus correspondent à la distribution associée au vecteur qui relie les deux extrémités de la marche aléatoire, en 3D. La variance associée à chaque composante , ou n'est que le tiers de cette valeur (toujours en 3D).

Pour 2D :

Pour 1D :

Une marche aléatoire dont la taille du pas varie selon une distribution normale est utilisée comme modèle pour les données de séries chronologiques du monde réel telles que les marchés financiers.

Ici, la taille du pas est la distribution normale cumulative inverse où 0 ≤ z ≤ 1 est un nombre aléatoire uniformément distribué, et μ et σ sont respectivement la moyenne et les écarts types de la distribution normale.

Si μ est différent de zéro, la marche aléatoire variera autour d'une tendance linéaire. Si v _s est la valeur de départ de la marche aléatoire, la valeur attendue après n étapes sera v _s + n μ.

Pour le cas particulier où μ est égal à zéro, après n étapes, la distribution de probabilité de la distance de translation est donnée par N (0, n σ ² ), où N () est la notation de la distribution normale, n est le nombre d'étapes et σ provient de la distribution normale cumulative inverse comme indiqué ci-dessus.

Preuve : La marche aléatoire gaussienne peut être considérée comme la somme d'une séquence de variables aléatoires indépendantes et identiquement distribuées, X _i de la distribution normale cumulative inverse avec une moyenne égale à zéro et σ de la distribution normale cumulative inverse d'origine :

mais nous avons la distribution pour la somme de deux variables aléatoires normalement distribuées indépendantes, Z = X + Y , est donnée par (voir ici) .

Dans notre cas, μ _X = μ _Y = 0 et σ ² _X = σ ² _Y = σ ² donnent Par récurrence, pour n étapes nous avons Pour des étapes distribuées selon une distribution quelconque de moyenne nulle et de variance finie (pas nécessairement juste une distribution normale), la distance de translation quadratique moyenne après n étapes est (voir l'identité de Bienaymé )

Mais pour la marche aléatoire gaussienne, il s'agit simplement de l'écart type de la distribution de la distance de translation après n étapes. Par conséquent, si μ est égal à zéro et que la distance de translation quadratique moyenne (RMS) est d'un écart type, il y a 68,27 % de probabilité que la distance de translation RMS après n étapes soit comprise entre . De même, il y a 50 % de probabilité que la distance de translation après n étapes soit comprise entre .

Le nombre de sites distincts visités par un seul marcheur aléatoire a été étudié de manière approfondie pour les réseaux carrés et cubiques et pour les fractales. Cette quantité est utile pour l'analyse des problèmes de piégeage et de réactions cinétiques. Elle est également liée à la densité d'états vibrationnelle, aux processus de réactions de diffusion et à la propagation des populations en écologie.

Le taux d'information d'une marche aléatoire gaussienne par rapport à la distance d'erreur au carré, c'est-à-dire sa fonction de distorsion quadratique , est donné paramétriquement par où . Par conséquent, il est impossible de coder en utilisant un code binaire de moins de bits et de le récupérer avec une erreur quadratique moyenne attendue inférieure à . D'autre part, pour tout , il existe un suffisamment grand et un code binaire de pas plus de éléments distincts tels que l'erreur quadratique moyenne attendue en récupérant à partir de ce code soit au plus . $0\epsilon >0$0}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e04ec3670b50384a3ce48aca42e7cc5131a06b12">

Comme mentionné précédemment, la gamme des phénomènes naturels qui ont fait l'objet de tentatives de description par une sorte de marche aléatoire est considérable, en particulier en physique et en chimie, en science des matériaux , et en biologie. Voici quelques applications spécifiques des marches aléatoires :

• En économie financière , l' hypothèse de marche aléatoire est utilisée pour modéliser les prix des actions et d'autres facteurs. Des études empiriques ont révélé quelques écarts par rapport à ce modèle théorique, notamment dans les corrélations à court et à long terme. Voir cours des actions .
• En génétique des populations , la marche aléatoire décrit les propriétés statistiques de la dérive génétique.
• En physique , les marches aléatoires sont utilisées comme modèles simplifiés du mouvement brownien physique et de la diffusion tels que le mouvement aléatoire des molécules dans les liquides et les gaz. Voir par exemple l'agrégation limitée par diffusion. En physique également, les marches aléatoires et certaines des marches auto-interactives jouent un rôle dans la théorie quantique des champs .
• Dans la fabrication de semi-conducteurs , les marches aléatoires sont utilisées pour analyser les effets du traitement thermique sur des nœuds plus petits. Elles sont appliquées pour comprendre la diffusion des dopants , des défauts , des impuretés , etc., au cours des étapes critiques de fabrication. Les traitements par marche aléatoire sont également utilisés pour étudier la diffusion des réactifs, des produits et du plasma au cours des processus de dépôt chimique en phase vapeur . La diffusion continue a été utilisée pour étudier l'écoulement des gaz, à l'échelle macroscopique, dans les réacteurs CVD. Cependant, des dimensions plus petites et une complexité accrue nous ont obligés à les traiter par marche aléatoire. Cela permet une analyse précise des processus stochastiques, au niveau moléculaire et plus petit, dans la fabrication de semi-conducteurs.
• En écologie mathématique , les marches aléatoires sont utilisées pour décrire les mouvements individuels des animaux, pour soutenir empiriquement les processus de biodiffusion et parfois pour modéliser la dynamique des populations .
• En physique des polymères , la marche aléatoire décrit une chaîne idéale . C'est le modèle le plus simple pour étudier les polymères .
• Dans d'autres domaines des mathématiques, la marche aléatoire est utilisée pour calculer les solutions de l'équation de Laplace , pour estimer la mesure harmonique et pour diverses constructions en analyse et en combinatoire .
• En informatique , les marches aléatoires sont utilisées pour estimer la taille du Web .
• Dans la segmentation d'image , des marches aléatoires sont utilisées pour déterminer les étiquettes (c'est-à-dire « objet » ou « arrière-plan ») à associer à chaque pixel. Cet algorithme est généralement appelé algorithme de segmentation par marcheur aléatoire .

• Dans la recherche sur le cerveau , les marches aléatoires et les marches aléatoires renforcées sont utilisées pour modéliser les cascades de déclenchements de neurones dans le cerveau.
• En science de la vision , la dérive oculaire a tendance à se comporter comme une marche aléatoire. Selon certains auteurs, les mouvements oculaires fixationnistes en général sont également bien décrits par une marche aléatoire.
• En psychologie , les marches aléatoires expliquent avec précision la relation entre le temps nécessaire pour prendre une décision et la probabilité qu'une certaine décision soit prise.
• Les marches aléatoires peuvent être utilisées pour échantillonner à partir d'un espace d'état inconnu ou très grand, par exemple pour sélectionner une page aléatoire sur Internet. En informatique , cette méthode est connue sous le nom de Markov Chain Monte Carlo (MCMC).

• Dans les réseaux sans fil , une marche aléatoire est utilisée pour modéliser le mouvement des nœuds.
• Les bactéries mobiles participent à des marches aléatoires biaisées .
• En physique, les marches aléatoires sont à la base de la méthode d' estimation de Fermi .
• Sur le Web, le site Twitter utilise des promenades aléatoires pour suggérer des personnes à suivre
• Dave Bayer et Persi Diaconis ont prouvé que 7 mélanges de cartes suffisent pour mélanger un jeu de cartes (voir plus de détails sous mélanger ). Ce résultat se traduit par une affirmation sur la marche aléatoire sur le groupe symétrique, ce qu'ils prouvent, avec une utilisation cruciale de la structure du groupe via l'analyse de Fourier.

Plusieurs types de processus stochastiques ont été envisagés, qui sont similaires aux marches aléatoires pures, mais où la structure simple peut être plus généralisée. La structure pure peut être caractérisée par des étapes définies par des variables aléatoires indépendantes et identiquement distribuées . Les marches aléatoires peuvent se dérouler sur une variété d'espaces, tels que les graphes , les entiers, la droite réelle, le plan ou les espaces vectoriels de dimension supérieure, sur des surfaces courbes ou des variétés riemanniennes de dimension supérieure , et sur des groupes . Il est également possible de définir des marches aléatoires qui effectuent leurs étapes à des moments aléatoires, et dans ce cas, la position X
_tdoit être défini pour tous les instants t ∈ [0, +∞) . Les cas ou limites spécifiques de marches aléatoires incluent les modèles de vol et de diffusion de Lévy tels que le mouvement brownien .

Une marche aléatoire de longueur k sur un graphe éventuellement infini G de racine 0 est un processus stochastique à variables aléatoires tel que et est un sommet choisi uniformément au hasard parmi les voisins de . Alors le nombre est la probabilité qu'une marche aléatoire de longueur k commençant à v se termine à w . En particulier, si G est un graphe de racine 0 , est la probabilité qu'une marche aléatoire en étapes revienne à 0 .

En nous appuyant sur l'analogie de la section précédente sur les dimensions supérieures, supposons maintenant que notre ville ne soit plus une grille carrée parfaite. Lorsque notre personne atteint un certain carrefour, elle choisit entre les différentes routes disponibles avec une probabilité égale. Ainsi, si le carrefour a sept sorties, la personne ira à chacune d'elles avec une probabilité d'un septième. Il s'agit d'une marche aléatoire sur un graphique. Notre personne atteindra-t-elle son domicile ? Il s'avère que dans des conditions plutôt douces, la réponse est toujours oui, mais selon le graphique, la réponse à la question variante « Deux personnes se rencontreront-elles à nouveau ? » peut ne pas être qu'elles se rencontrent infiniment souvent, presque sûrement.

Un exemple de cas où la personne atteindra presque sûrement sa maison est celui où les longueurs de tous les blocs sont comprises entre a et b (où a et b sont deux nombres positifs finis). Notez que nous ne supposons pas que le graphique est plan , c'est-à-dire que la ville peut contenir des tunnels et des ponts. Une façon de prouver ce résultat est d'utiliser la connexion aux réseaux électriques . Prenez une carte de la ville et placez une résistance d'un ohm sur chaque bloc. Mesurez maintenant la « résistance entre un point et l'infini ». En d'autres termes, choisissez un nombre R et prenez tous les points du réseau électrique dont la distance est supérieure à R de notre point et reliez-les ensemble. Il s'agit maintenant d'un réseau électrique fini, et nous pouvons mesurer la résistance de notre point aux points reliés. Portez R à l'infini. La limite est appelée la résistance entre un point et l'infini . Il s'avère que ce qui suit est vrai (une preuve élémentaire peut être trouvée dans le livre de Doyle et Snell) :

Théorème : un graphe est transitoire si et seulement si la résistance entre un point et l'infini est finie. Le choix du point n'a pas d'importance si le graphe est connexe.

En d'autres termes, dans un système transitoire, il suffit de vaincre une résistance finie pour atteindre l'infini à partir de n'importe quel point. Dans un système récurrent, la résistance de n'importe quel point à l'infini est infinie.

Cette caractérisation de la fugacité et de la récurrence est très utile, et permet notamment d'analyser le cas d'une ville dessinée dans le plan avec les distances délimitées.

Une marche aléatoire sur un graphe est un cas très particulier de chaîne de Markov . Contrairement à une chaîne de Markov générale, la marche aléatoire sur un graphe bénéficie d'une propriété appelée symétrie temporelle ou réversibilité . Grosso modo, cette propriété, aussi appelée principe d' équilibre détaillé , signifie que les probabilités de parcourir un chemin donné dans un sens ou dans l'autre ont un lien très simple entre elles (si le graphe est régulier , elles sont simplement égales). Cette propriété a des conséquences importantes.

Depuis les années 1980, de nombreuses recherches ont été consacrées à relier les propriétés du graphe aux marches aléatoires. En plus du lien avec le réseau électrique décrit ci-dessus, il existe des liens importants avec les inégalités isopérimétriques , voir plus ici , les inégalités fonctionnelles telles que les inégalités de Sobolev et de Poincaré et les propriétés des solutions de l'équation de Laplace . Une partie importante de ces recherches s'est concentrée sur les graphes de Cayley de groupes de type fini . Dans de nombreux cas, ces résultats discrets sont transposés ou dérivés des variétés et des groupes de Lie .

Dans le contexte des graphes aléatoires , en particulier celui du modèle Erdős–Rényi , des résultats analytiques sur certaines propriétés des marcheurs aléatoires ont été obtenus. Il s'agit notamment de la distribution des premiers et derniers temps d'impact du marcheur, où le premier temps d'impact est donné par la première fois que le marcheur entre dans un site précédemment visité du graphe, et le dernier temps d'impact correspond à la première fois que le marcheur ne peut pas effectuer de mouvement supplémentaire sans revisiter un site précédemment visité.

Une bonne référence pour la marche aléatoire sur les graphes est le livre en ligne d'Aldous et Fill. Pour les groupes, voir le livre de Woess. Si le noyau de transition est lui-même aléatoire (basé sur un environnement ), alors la marche aléatoire est appelée « marche aléatoire dans un environnement aléatoire ». Lorsque la loi de la marche aléatoire inclut le caractère aléatoire de , la loi est appelée loi recuite ; en revanche, si est considérée comme fixe, la loi est appelée loi éteinte. Voir le livre de Hughes, le livre de Revesz ou les notes de cours de Zeitouni.

Nous pouvons envisager de choisir chaque arête possible avec la même probabilité afin de maximiser l’incertitude (entropie) localement. Nous pourrions également le faire globalement – ​​dans la marche aléatoire à entropie maximale (MERW), nous voulons que tous les chemins soient également probables, ou en d’autres termes : pour chaque paire de sommets, chaque chemin de longueur donnée est également probable. Cette marche aléatoire a des propriétés de localisation beaucoup plus fortes.

Il existe un certain nombre de modèles intéressants de chemins aléatoires dans lesquels chaque étape dépend du passé de manière complexe. Tous sont plus complexes à résoudre analytiquement que la marche aléatoire habituelle ; néanmoins, le comportement de tout modèle de marcheur aléatoire peut être obtenu à l'aide d'ordinateurs. En voici quelques exemples :

• La marche auto-évitante .

La marche auto-évitante de longueur n sur est le chemin aléatoire en n étapes qui démarre à l'origine, effectue des transitions uniquement entre des sites adjacents dans , ne revisite jamais un site et est choisi uniformément parmi tous ces chemins. En deux dimensions, en raison de l'auto-piégeage, une marche auto-évitante typique est très courte, tandis qu'en dimension supérieure, elle s'étend au-delà de toutes les limites. Ce modèle a souvent été utilisé en physique des polymères (depuis les années 1960).

• La marche aléatoire à boucle effacée .
• La marche aléatoire renforcée.
• Le processus d'exploration.
• La marche aléatoire multiagent.

La marche aléatoire choisie pour maximiser le taux d'entropie a des propriétés de localisation beaucoup plus fortes.

Marches aléatoires où la direction du mouvement à un moment donné est corrélée à la direction du mouvement à l'instant suivant. Elle est utilisée pour modéliser les mouvements des animaux.