marche aléatoire

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

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

Pour définir formellement cette marche, considérons des variables aléatoires indépendantes, où chaque variable vaut soit 1, soit −1, avec une probabilité de 50 % pour chaque valeur, et définiretLa sérieest appelée marche aléatoire simple surCette série (la somme des suites de −1 et de 1) donne la distance totale parcourue, si chaque segment du trajet a une longueur de un. L' espérancedeest zéro. Autrement dit, la moyenne de tous les lancers de pièce tend vers zéro lorsque le nombre de lancers augmente. Ceci 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 laisse entendre que, la distance de translation attendue après n étapes, devrait être de l'ordre deEn fait,

Pour répondre à la question du nombre de fois qu'une marche aléatoire franchira une ligne frontière si elle est autorisée à continuer indéfiniment, considérons une simple marche aléatoire surLe jeu traversera chaque point une infinité de fois. Ce phénomène porte plusieurs noms : le passage par niveau , la récurrence ou encore la ruine du joueur . L’origine de ce dernier nom est la suivante : un joueur disposant d’une somme d’argent finie finira par perdre à un jeu équitable contre une banque aux ressources illimitées. L’argent du joueur suivra une trajectoire aléatoire et atteindra zéro à un moment donné, mettant ainsi fin à la partie.

Si a et b sont des entiers positifs, alors le nombre moyen d'étapes avant qu'une marche aléatoire simple unidimensionnelle partant de 0 n'atteigne pour la première fois b ou −a est ab . La probabilité que cette marche atteigne b avant −a est, ce qui peut être déduit du fait qu'une marche aléatoire simple est une martingale . Et ces espérances et probabilités d'atteinte peuvent être calculées dansdans la chaîne de Markov de marche aléatoire unidimensionnelle générale.

Certains des résultats mentionnés ci-dessus peuvent être déduits des propriétés du triangle de Pascal . Le nombre de marches aléatoires différentes de n étapes où chaque étape vaut +1 ou −1 est 2ⁿ ^. Pour une marche aléatoire simple, chacune de ces marches est équiprobable. Pour que Sₙ soit égal à un nombre k, _il est nécessaire et suffisant que le nombre de +1 dans la marche dépasse celui des −1 de k . Il s'ensuit que +1 doit apparaître ( n + k )/2 fois parmi les n étapes d'une marche, d'où le nombre de marches qui satisfont cette condition.égal au nombre de façons de choisir ( n + k )/2 éléments parmi 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 deux pairs, soit tous deux impairs. Par conséquent, la probabilité queest égal àEn représentant les éléments du triangle de Pascal en fonction des factorielles et en utilisant la formule de Stirling , on peut obtenir de bonnes estimations de ces probabilités pour de grandes valeurs de.

Cette relation avec le triangle de Pascal est démontrée pour de petites valeurs de n . Sans changement de position, la seule possibilité est de rester à zéro. En revanche, après un changement de position, il y a une chance sur -1 ou une chance sur 1. Après deux changements de position, un marqueur en 1 peut aller à 2 ou revenir à zéro. Un marqueur en -1 peut aller à -2 ou revenir à zéro. Par conséquent, il y a une chance sur -2, deux chances sur zéro et une chance 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 dans chaque ligne) se rapprochent d'une distribution normale .

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

Correction de la mise à l'échelle, pourfixe, et en utilisant l'expansionquanddisparaît, il suit

en prenant la limite (et en observant que(correspondant à l'espacement de la grille d'échelle), on trouve la densité gaussienneEn effet, pour une variable aléatoire absolument continueavec densitéil contient, aveccorrespondant à un espacement infinitésimal.

Par généralisation directe, on peut considérer les marches aléatoires sur les réseaux cristallins (graphes de recouvrement abéliens infinis sur des graphes finis). Il est en effet possible d'établir le théorème central limite et le théorème des grandes déviations dans ce cadre.

En dimensions supérieures, l'ensemble des points parcourus aléatoirement présente des propriétés géométriques intéressantes. On obtient en effet une fractale discrète , c'est-à-dire un ensemble qui présente une autosimilarité stochastique à grande échelle. À petite échelle, on observe un aspect irrégulier dû à la grille sur laquelle le parcours est effectué. La trajectoire d'une marche aléatoire est l'ensemble des points visités, indépendamment de l'instant où la marche atteint chaque point. En une dimension, la trajectoire correspond simplement à l'ensemble des points compris entre la hauteur minimale et la hauteur maximale atteintes par la marche (ces deux hauteurs étant, en moyenne, de l'ordre de grandeur de 10⁻⁵ m).).

Pour visualiser le cas bidimensionnel, on peut imaginer une personne se promenant aléatoirement dans une ville. Cette ville est considérée comme infinie et organisée selon un quadrillage de trottoirs. À chaque intersection, la personne choisit aléatoirement l'un des quatre itinéraires possibles (y compris celui emprunté initialement). Formellement, il s'agit d'une marche aléatoire sur l'ensemble des points du plan dont les coordonnées sont des entiers .

Pour répondre à la question de savoir si une personne retourne un jour à son point de départ, il s'agit de l'équivalent bidimensionnel du problème du passage à niveau évoqué précédemment. En 1921, George Pólya a démontré que, dans une marche aléatoire bidimensionnelle, la personne y retournerait presque certainement. Cependant, en trois dimensions ou plus, la probabilité de retour à l'origine diminue avec l'augmentation du nombre de dimensions. En trois dimensions, cette probabilité chute à environ 34 % . Le mathématicien Shizuo Kakutani avait coutume de commenter ce résultat par la citation suivante : « Un homme ivre retrouvera son chemin, mais un oiseau ivre risque de se perdre à jamais. »

La probabilité de récidive est en général, qui peut être dérivée par des fonctions génératrices 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 un jour ? » On peut démontrer que la différence entre leurs positions (deux marches aléatoires indépendantes) correspond également à une marche aléatoire simple. Elles se rencontreront donc presque sûrement à nouveau dans un espace bidimensionnel, mais pour trois 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 une dimension inférieure ou égale à 4, deux marches aléatoires indépendantes partant de deux points donnés quelconques s’intersectent presque sûrement une infinité de fois, tandis que pour une dimension supérieure à 5, elles ne s’intersectent presque sûrement qu’un nombre fini de fois.

La fonction asymptotique d'une marche aléatoire bidimensionnelle, lorsque le nombre de pas augmente, suit une loi de Rayleigh . La distribution de probabilité est fonction du rayon à partir de l'origine, et la longueur du pas est constante. Ici, la longueur du pas est supposée égale à 1, N est le nombre total de pas 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 particule minuscule dans un fluide. (On parle parfois de « mouvement brownien » pour désigner le processus de Wiener , bien qu'il s'agisse à proprement parler d'une confusion entre le modèle et le phénomène qu'il modélise.)

Un processus de Wiener est la limite d'échelle d'une marche aléatoire en dimension 1. Autrement dit, toute marche aléatoire à très petits pas s'approche d'un processus de Wiener (et, de façon moins précise, d'un mouvement brownien). Plus précisément, pour un pas de longueur ε, une marche de longueur L /ε² ^est nécessaire pour approcher une longueur de Wiener L. Lorsque le pas tend vers 0 (et que le nombre de pas augmente proportionnellement), la marche aléatoire converge vers un processus de Wiener au sens approprié. Formellement, si B est l'espace des chemins de longueur L muni de la topologie maximale, et si M est l'espace de mesure sur B muni de la topologie de norme, alors la convergence a lieu 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 dimension entière ; 1, 2, ...), tandis qu'une trajectoire de processus de Wiener est une véritable fractale, et il existe un lien entre les deux. Par exemple, considérons une marche aléatoire jusqu'à ce qu'elle atteigne un cercle de rayon r fois la longueur du pas. Le nombre moyen de pas effectués est alors ^de r² . Ce résultat correspond à la version discrète du fait qu'une marche aléatoire de processus de Wiener est une fractale de dimension de Hausdorff 2.Mandelbrot à l'aide de simulations mais prouvé seulement en 2000 par Lawler , Schramm et Werner .

Un processus de Wiener possède de nombreuses symétries qu'une marche aléatoire ne possède pas. Par exemple, une marche de Wiener est invariante par rotation, contrairement à une marche aléatoire, car la grille sous-jacente ne l'est pas (une marche aléatoire est invariante par rotation de 90 degrés, tandis qu'un processus de Wiener l'est également par rotation de 17 degrés, par exemple). Cela signifie que, dans de nombreux cas, les problèmes définis sur une marche aléatoire sont plus faciles à résoudre en les traduisant en un processus de Wiener, en les résolvant, puis en effectuant la traduction inverse. Par ailleurs, 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 se manifester sur le même espace de probabilité de manière dépendante, ce qui les rend très proches. Le couplage le plus simple est l' injection 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 régie 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 indique qu'après un grand nombre d' étapes indépendantes de la marche aléatoire, la position de la particule suit une loi normale de variance totale :

où t représente le temps écoulé depuis le début de la marche aléatoire,est la taille d'un pas de la marche aléatoire, etest 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 égalant cette quantité à la variance associée à la position du marcheur aléatoire, on obtient le coefficient de diffusion équivalent à considérer pour le processus de Wiener asymptotique 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 vecteurqui relie les deux extrémités de la marche aléatoire, en 3D. La variance associée à chaque composante,oune représente qu'un tiers de cette valeur (toujours en 3D).

Pour la 2D :

Pour 1D :