Marche aléatoire

Le modèle de marche aléatoire le plus simple est celui de la marche aléatoire discrète à une dimension sur le réseau périodique ℤ. Pour en former un exemple concret, on peut imaginer un individu (ou « particule ») sur un escalier, qui tire à pile ou face pour décider si le prochain pas sera vers le haut ou vers le bas. À chaque étape, il n'y a que deux possibilités : sur cet exemple, un pas en avant ou un pas en arrière. Le seul paramètre libre du problème est la probabilité que la particule fasse un saut en avant (plutôt qu'un saut en arrière).

Si on nomme cette probabilité par le nombre réel p tel que : 0 < p < 1, alors q = 1 – p représente la probabilité que la particule fasse un saut en arrière.

Le cas le plus simple, qui correspond par exemple au mouvement brownien, consiste à faire l'hypothèse d'isotropie spatiale. Les directions « avant / arrière » de l'espace physique étant a priori équivalentes, on pose l'équiprobabilité :

${\displaystyle p=q={\frac {1}{2}}}$

Il est remarquable que les lois mises en évidence dans ce cas s'étendent à des problèmes de marches aléatoires beaucoup plus complexes.

Trois marches aléatoires (indépendantes) isotropes sur le réseau ℤ ; 1000 pas.

Chacun des tirs au hasard pour choisir le mouvement constitue une épreuve de Bernoulli avec issues équiprobables : ici la probabilité de montée ou de descente est 1/2.

La figure ci-contre montre un échantillon de trois simulations numériques indépendantes de marches aléatoires pour une particule : on a tracé les positions successives x(t) de la particule aux instants t = 1, 2,..., partant de la condition initiale x(0)=0.

Après n pas au total, le nombre ${\displaystyle N_{n}}$de fois où on a tiré « pile » suit la loi binomiale B(n,1/2), de sorte que la probabilité vaut :

${\displaystyle P(N_{n}=k)\ =\ {\frac {1}{2^{n}}}\ {n \choose k}}$

où ${\displaystyle {n \choose k}}$ est le nombre de combinaisons de k éléments pris parmi n.

On peut déterminer la position ${\displaystyle X_{n}}$après n itérations, en prenant la valeur 0 pour le départ, en ajoutant 1 pour chaque pas en avant (pile), en retranchant 1 pour chaque pas en arrière (face). Alors la position ${\displaystyle X_{n}}$ est donnée par : ${\displaystyle X_{n}=N_{n}-(n-N_{n})=2N_{n}-n}$. Par rapport à la loi binomiale classique, il suffit donc de décaler les résultats de ⁿ⁄₂ et de multiplier par 2, ainsi :

• ${\displaystyle P(X_{n}=k)={1 \over {2^{n}}}{\binom {n}{\frac {n+k}{2}}}}$ si n et k ont même parité, = 0 sinon ;
• l'espérance est nulle ;
• la variance vaut n et l'écart type √n ;
• on a toujours l'inégalité de Bienaymé-Tchebychev ;
• et la loi des grands nombres.

Concrètement, si on renouvelle l'expérience avec un grand nombre de participants, et si on les laisse évoluer pendant un nombre de pas assez important (de l'ordre de n = 100 par exemple) on s'attend à ce que le nuage des positions finales soit en gros centré sur la marche initiale. Ceci peut être rendu quantitatif : en se plaçant dans le régime asymptotique n >> 1, on démontre en utilisant la formule de Stirling que la loi binomiale se comporte asymptotiquement comme une distribution gaussienne. On obtient notamment un ordre de grandeur de l'étalement du nuage de participants : par exemple on s'attend à ce que 95 % environ des participants soient restés à 20 pas ou moins de la position initiale (20=2√100).

La galerie ci-dessous contient quatre spécimens de marches aléatoires isotropes sur le réseau ℤ après 1 000 pas, partant de l'origine. Les lignes en pointillés indiquent respectivement les valeurs maximum et minimum de la position atteintes (après 1 000 pas).

D'après la formule ci-dessus, la probabilité de revenir à l'origine au bout de 2n pas vaut ${\displaystyle p_{n}=P(X_{2n}=0)={1 \over {2^{2n}}}{\binom {2n}{n}}}$ (elle est bien sûr nulle après un nombre impair de pas).

L'équivalent obtenu par la formule de Stirling ${\displaystyle p_{n}\sim {1 \over {\sqrt {\pi n}}}}$ montre que cette probabilité tend lentement vers 0 ce qui signifie intuitivement que plus le temps passe, moins on a de chance de se trouver au point de départ. Cependant nous allons voir que toute marche revient au moins une fois à l'origine, tout en sachant que la moyenne des temps de premier retour à l'origine est infinie.

On se demande quelle est la probabilité ${\displaystyle q_{n}}$ d'être revenu au moins une fois à l'origine lors d'un parcours de longueur 2n ; il est remarquable que l'évènement contraire ${\displaystyle \{X_{k}\neq 0,1\leqslant k\leqslant 2n\}}$ a aussi pour probabilité ${\displaystyle p_{n}={1 \over {2^{2n}}}{\binom {2n}{n}}}$ et que donc ${\displaystyle q_{n}=1-p_{n}}$ tend vers 1 lorsque n tend vers l'infini : une marche aléatoire isotrope sur la droite repasse presque surement au moins une fois à son point de départ (donc en fait y repasse une infinité de fois), et ceci vaut même pour tout point par lequel elle passe. On verra plus loin que ceci reste vrai en dimension 2, mais devient faux en dimension supérieure.

Démonstration de la formule précédente :

Pour raison de symétrie, le nombre de marches aléatoires de longueur ${\displaystyle 2n}$ ne repassant pas par ${\displaystyle 0}$ est le double du nombre de celles qui restent ${\displaystyle >0}$.

Notre problème est de dénombrer les marches allant de ${\displaystyle 0}$ à ${\displaystyle 2k}$ en ${\displaystyle 2n}$ coups et se situant, à part ${\displaystyle 0}$, strictement à droite de ${\displaystyle 0}$.

Le premier segment d'une telle marche allant forcément de ${\displaystyle 0}$ à ${\displaystyle 1}$, il suffit de compter le nombre de chemins qui vont de ${\displaystyle 1}$ à ${\displaystyle \ 2k}$ en ${\displaystyle 2n-1}$ coups sans passer par ${\displaystyle 0}$.

D'une façon générale, le nombre de chemins qui vont de ${\displaystyle a}$ à ${\displaystyle b}$ en ${\displaystyle m}$ coups vaut ${\displaystyle \left({\begin{array}{c}m\\{\frac {m+b-a}{2}}\end{array}}\right)=}$ ${\displaystyle \left({\begin{array}{c}m\\{\frac {m-b+a}{2}}\end{array}}\right)}$(le chemin est entièrement déterminé par les ${\displaystyle {\frac {m+b-a}{2}}}$ déplacements vers la droite (ou les ${\displaystyle {\frac {m-b+a}{2}}}$ déplacements vers la gauche)), à choisir parmi les ${\displaystyle m}$ déplacements totaux. Donc déjà, le nombre total de marches qui vont de ${\displaystyle 1}$ à ${\displaystyle 2k}$ vaut ${\displaystyle \left({\begin{array}{c}2n-1\\n+k-1\end{array}}\right).}$

La partie délicate est de déterminer le nombre de marches de ${\displaystyle 1}$ à ${\displaystyle 2k}$ en ${\displaystyle 2n-1}$ coups qui passent par 0. On utilise pour cela le principe de réflexion, (voir l'article sur le problème du scrutin).

Pour une telle marche, on peut remplacer bijectivement la partie entre le ${\displaystyle 0}$ de départ et le premier retour en ${\displaystyle 0}$ par son symétrique par rapport à ${\displaystyle 0}$: ce nombre est donc le même que celui des marches allant de ${\displaystyle -1}$ à ${\displaystyle 2k}$ en ${\displaystyle 2n-1}$ coups soit ${\displaystyle \left({\begin{array}{c}2n-1\\n+k\end{array}}\right).}$

.Le nombre de marches allant de ${\displaystyle 0}$ à ${\displaystyle 2k}$ de longueur ${\displaystyle 2n}$ sans passer par l'axe vaut donc ${\displaystyle \left({\begin{array}{c}2n-1\\n+k-1\end{array}}\right)-\left({\begin{array}{c}2n-1\\n+k\end{array}}\right)}$. Notons que ce résultat est équivalent à celui du théorème du scrutin.

On en déduit le nombre de marches évitant ${\displaystyle 0}$ : ${\displaystyle 2^{2n}(1-q_{n})=2{\underset {k=1}{\overset {n}{\sum }}}\left(\left({\begin{array}{c}2n-1\\n+k-1\end{array}}\right)-\left({\begin{array}{c}2n-1\\n+k\end{array}}\right)\right)}$ ; somme télescopique donnant ${\displaystyle 2^{2n}(1-q_{n})=2\left({\begin{array}{c}2n-1\\n\end{array}}\right)=\left({\begin{array}{c}2n\\n\end{array}}\right)}$, ce qu'il fallait démontrer.

Autre interprétation du même résultat : le nombre de mots binaires de longueur ${\displaystyle 2n}$ dont tous les sous-mots commençant par la gauche (resp. par la droite) présentent strictement plus de 1 que de 0 (resp. l'inverse) vaut ${\displaystyle \left({\begin{array}{c}2n\\n\end{array}}\right)}$ (ne pas confondre avec les mots de Dyck).

Un calcul similaire montre que dans le cas impair, la probabilité de retour à l'origine lors d'un parcours de longueur ${\displaystyle 2n+1}$ vaut aussi ${\displaystyle 1-p_{n}}$ (voir la suite A063886 de l'OEIS et la suite A307768 de l'OEIS).

En utilisant des résultats précédents, on peut obtenir la probabilité ${\displaystyle r_{2n}}$que la marche revienne à l'origine pour la première fois au temps ${\displaystyle 2n}$ : ${\displaystyle r_{2n}={p_{n} \over {2n-1}}}$. On en déduit que l'espérance du temps de premier retour à l'origine ${\displaystyle {\underset {n=1}{\overset {\infty }{\sum }}}}{2nr_{2n}}$ est infinie puisque ${\displaystyle 2nr_{2n}\sim {1 \over {\sqrt {\pi n}}}}$.

Démonstration de la formule précédente :

Une marche qui revient à l'origine au temps ${\displaystyle 2n}$ passe forcément par 1 ou par -1 au temps précédent et, toujours par symétrie, il y a autant de marches arrivant en 1 qu'en -1 ; le nombre de marches revenant à l'origine pour la première fois au temps ${\displaystyle 2n}$ vaut donc le double du nombre de marches de longueur ${\displaystyle 2n-1}$ aboutissant en 1 et restant >0 ; on peut refaire un raisonnement du type précédent ou appliquer directement la formule du scrutin ${\displaystyle 2^{2n}r_{2n}=2{{p-q} \over {p+q}}\left({\begin{array}{c}p+q\\p\end{array}}\right)}$ avec ${\displaystyle p+q=2n-1,p-q=1}$, d'où ${\displaystyle 2^{2n}r_{2n}=2{{1} \over {2n-1}}\left({\begin{array}{c}2n-1\\n\end{array}}\right)={{1} \over {2n-1}}\left({\begin{array}{c}2n\\n\end{array}}\right)}$, ce que nous voulions.

Notons que ${\displaystyle {{1} \over {2n-1}}\left({\begin{array}{c}2n\\n\end{array}}\right)={{2} \over {n}}\left({\begin{array}{c}2(n-1)\\n-1\end{array}}\right)}$ est le double du nombre de Catalan d'ordre ${\displaystyle n-1}$.

Trois marches aléatoires (indépendantes) isotropes sur le réseau ℤ² ; 10 000 pas.

On considère une marche aléatoire sur le réseau plan ℤ². Il y a ici quatre mouvements possibles à chaque site : en avant, en arrière, à droite, à gauche. La figure ci-contre montre un échantillon de trois simulations numériques indépendantes de marches aléatoires pour une particule : on a tracé les trois trajectoires obtenues.

Pour des longues marches, la distribution de la position finale du marcheur se comporte asymptotiquement comme une distribution gaussienne. Cette convergence est illustrée ci-dessous : on trace les répartitions des probabilités de présence sur le réseau après 10 pas, puis après 60 pas :

Après 10 pas.

Après 60 pas.

La galerie ci-dessous contient quatre spécimens de marches aléatoires isotropes sur le réseau ℤ² après 10 000 pas, partant de l'origine.

On considère une marche aléatoire sur le réseau cubique ℤ³. Il y a ici six mouvements possibles à chaque site : en avant, en arrière, à droite, à gauche, en haut, en bas.

Trois marches aléatoires (indépendantes) isotropes sur le réseau ℤ³ ; 10 000 pas.

La figure ci-contre montre un échantillon de trois simulations numériques indépendantes de marches aléatoires pour une particule : on a tracé les trois trajectoires obtenues.

La galerie ci-dessous contient quatre spécimens de marches aléatoires isotropes sur le réseau ℤ³ après 10 000 pas, partant de l'origine.

On considère la marche aléatoire sur le plan ℝ² définie par le processus suivant :

Trois marches aléatoires (indépendantes) isotropes sur le plan ℝ² ; 10 000 pas.

• la particule est initialement à l'origine : x(0) = 0, y(0) = 0 et se déplace sur le plan par des sauts successifs effectués toutes les secondes.

• à chaque saut, la particule avance d'une longueur unité dans une direction caractérisée par un angle polaire α défini par rapport à l'axe (Ox). On choisit par exemple : –π ≤ α < +π.

• Cet angle polaire α est une variable aléatoire, caractérisée par une densité de probabilité f (α). Le processus est isotrope lorsque toutes les directions sont équiprobables, ce qui correspond au choix d'une densité uniforme :

${\displaystyle f(\alpha )\ =\ {\frac {1}{2\pi }}1\!\!1_{[-\pi ,\pi [}(\alpha )}$

Chaque direction de saut est totalement indépendante de la direction du saut précédent.

La figure ci-contre montre un échantillon de trois simulations numériques indépendantes de marches aléatoires pour une particule : on a tracé les trois trajectoires obtenues.

La galerie ci-dessous contient quatre spécimens de marches aléatoires isotropes sur le plan ℝ² après 10 000 pas, partant de l'origine.

Considérons une marche aléatoire isotrope sur le réseau ℤ^d à d dimensions spatiales. On peut toujours choisir de prendre le point de départ de cette marche comme origine O du système de coordonnées cartésiennes. La question de la récurrence consiste alors à se demander si on peut trouver au moins un[4] instant t positif fini pour lequel la particule repasse par l'origine O.

La marche aléatoire sera dite récurrente si et seulement si la probabilité que la particule repasse à l'origine O pour un certain instant t ultérieur fini vaut un.

Cette propriété de récurrence dépend fortement de la dimension de l'espace ; on peut en effet démontrer que[5] - [6] - [7] - [8] - [9] (Pólya - 1921)[10] :

• pour d = 1 et d = 2, la marche aléatoire isotrope est récurrente.
• pour d = 3 et au-delà, la marche aléatoire isotrope n'est pas récurrente ; on dit alors qu'elle est transitoire (en bon « franglais », certains auteurs utilisent parfois le mot anglais transient).

Certains disent parfois en plaisantant que ce théorème est au fondement du proverbe : « Tous les chemins mènent à Rome ». Le lecteur notera que si l'on inclut les chemins « cosmiques », alors le proverbe est faux[6].

On sait en fait calculer la probabilité que le marcheur, parti initialement de l'origine, revienne à l'origine, et ce pour toutes les dimensions d > 2. Cette probabilité p(d) admet l'expression suivante[11] :

${\displaystyle p(d)\ =\ 1\ -\ {\frac {1}{u(d)}}}$

où u(d) est une intégrale à d dimensions :

${\displaystyle u(d)\ =\ {\frac {d}{(2\pi )^{d}}}\ \int _{-\pi }^{\pi }\dots \int _{-\pi }^{\pi }{\frac {\mathrm {d} x_{1}\dots \mathrm {d} x_{d}}{d\ -\ \cos x_{1}\ -\ \dots \ -\ \cos x_{d}}}}$, pouvant s'exprimer à l'aide de la fonction de Bessel de première espèce :

${\displaystyle u(d)=\int _{0}^{\infty }(I_{0}(t/d))^{d}e^{-t}dt}$.

Le nombre ${\displaystyle u(d)={\frac {1}{1-p(d)}}}$ représente le nombre moyen de retours à l'origine avant d'aller à l'infini (voir à loi géométrique).

Le cas particulier d = 3 avait en fait déjà été obtenu précédemment par Watson[12], Mc Crea et Whipple[13], et Domb[14]. Une expression analytique de l'intégrale n'a été obtenue qu'en 1977 par Glasser et Zucker[15] - [16] :

${\displaystyle u(3)\ =\ {\frac {\sqrt {6}}{32\,\pi ^{3}}}\,\Gamma \left({\frac {1}{24}}\right)\,\Gamma \left({\frac {5}{24}}\right)\,\Gamma \left({\frac {7}{24}}\right)\,\Gamma \left({\frac {11}{24}}\right)\ }$

où Γ est la fonction gamma. Les expressions analytiques de u(d) ne sont pas connues en dimension d supérieure ou égale à 4[16].

On obtient les valeurs numériques suivantes[17] :

• ${\displaystyle u(3)\approx 1,516386059}$ , suite A086231 de l'OEIS, ${\displaystyle p(3)\approx 0,3405373296}$, suite A086230 de l'OEIS ;
• ${\displaystyle u(4)\approx 1,239467122}$ , suite A242812 de l'OEIS, ${\displaystyle p(4)\approx 0,1932016732}$, suite A086232 de l'OEIS ;
• ${\displaystyle u(5)\approx 1,156308125}$ , suite A242813 de l'OEIS, ${\displaystyle p(5)\approx 0,1351786098}$, suite A086233 de l'OEIS ;
• ${\displaystyle u(6)\approx 1,116963373}$ , suite A242814 de l'OEIS, ${\displaystyle p(6)\approx 0,1047154954}$, suite A086234 de l'OEIS ;
• ${\displaystyle u(7)\approx 1,093906316}$ , suite A242815 de l'OEIS, ${\displaystyle p(7)\approx 0,0858449341}$, suite A086235 de l'OEIS ;
• ${\displaystyle u(8)\approx 1,078647012}$ , suite A242816 de l'OEIS, ${\displaystyle p(8)\approx 0,0729126500}$, suite A086236 de l'OEIS .

• (en) Joseph Rudnick et George Gaspari, Elements of the Random Walk : An introduction for Advanced Students and Researchers, Cambridge University Press, 2004, 346 p. (ISBN 0-521-82891-0)
• (en) Frank Spitzer, Principles of the Random Walk, Princeton University Press, 1964 (lire en ligne)
  Réédité par Springer (1970) (ISBN 0-387-90139-6) ; 2^e édition dans la collection Graduate Texts in Mathematics 34 (2001) (ISBN 0-387-95154-7)
• (en) Daniel W. Stroock, An Introduction to Markov Processes, Springer, coll. « Graduate Texts in Mathematics », 2005, 178 p. (ISBN 978-3-540-23451-7, lire en ligne)
• (en) William Feller, An Introduction to Probability Theory and Its Applications, volume 1, John Wiley & Sons, coll. « Wiley Series in Probability and Statistics », 1968, 528 p. (ISBN 978-0-471-25708-0)

• (en) Mark Kac, Random Walk and the Theory of Brownian Motion, American Mathematical Monthly 54(7) (1947), 369-391. (en) Texte au format [PDF] Cet article est l'un des six contenus dans : Selected Papers on Noise & Stochastic Processes, Charles Proteus Steinmetz & Nelson Wax (eds.), Dover, 1954. Réédité dans la collection Phoenix (2003), ASIN 0486495353.
• (en) Subramaniam Chandrashekhar, Stochastic Problems in Physics & Astronomy, Review of Modern Physics 15 (1943), 1-89. Cet article est l'un des six contenus dans : Selected Papers on Noise & Stochastic Processes, Charles Proteus Steinmetz & Nelson Wax (eds.), Dover, 1954. Réédité dans la collection Phoenix (2003), ASIN 0486495353.

• (en) Martin Z. Bazant, Random Walks and Diffusion ; cours de mathématiques appliquées donné au MIT, avec des applications à la physique et à la finance.
  • (en) Notes de cours 2003.
  • (en) Notes de cours 2001.

• (en) Mark A. Pinsky, Isotropic transport process on a Riemannian manifold, Transaction of the American Mathematical Society 218 (1976), 353-360.
• (en) Nicolas Th. Varopoulos, Brownian motion and random walks on manifolds [PDF], Annales de l'Institut Fourier 34(2) (1984), 243-269.

• Chaîne de Markov
• Processus stochastique
• Mouvement brownien
• Modèle des urnes d'Ehrenfest
• Loi de Rayleigh
• Comportement adaptatif
• Chemin auto-évitant

• Expérience de marche aléatoire grandeur nature, dans une ville
• (en) Random walks chapter in American Mathematical Society's introductory probability book [PDF]