Marche au hasard

Marche aléatoire

Trois marches aléatoires (indépendantes) isotropes sur le réseau $\mathbb{Z}^2$ ; 10 000 pas.

En mathématiques et en physique théorique, une marche au hasard est un modèle mathématique d'un système possédant une dynamique discrète composée d'une succession de pas aléatoires, ou effectués « au hasard ». On emploie également fréquemment les expressions marche aléatoire, promenade aléatoire ou random walk en anglais. Ces pas aléatoires sont de plus totalement décorrélés les uns des autres ; cette dernière propriété, fondamentale, est appelée caractère markovien du processus, du nom du mathématicien Markov. Elle signifie intuitivement qu'à chaque instant, le futur du système dépend de son état présent, mais pas de son passé, même le plus proche. Autrement dit, le système « perd la mémoire » à mesure qu'il évolue dans le temps. Pour cette raison, une marche aléatoire est parfois aussi appelée « marche de l'ivrogne ».

Cette modélisation mathématique permet de rendre compte de certains phénomènes naturels, dont l'exemple le plus fameux est le mouvement brownien, correspondant aux mouvements en apparence aléatoires de grains de pollens immergés dans l'eau.

En mathématiques ou en informatique, on étudie souvent des marches au hasard sur des réseaux réguliers ou sur des graphes plus complexes. C'est par exemple la méthode utilisée par le moteur de recherche Google pour parcourir, identifier et classer les pages du réseau internet.

Techniquement, les marches aléatoires sont du domaine de la théorie des probabilités. Une marche aléatoire est en effet un processus stochastique du type chaîne de Markov. Elle se décompose en unités élémentaires appelées pas, dont la longueur peut être elle-même constante, aléatoire ou fixée par le réseau ou le graphe sur lequel on circule. À chaque pas, on a donc un éventail de possibilités pour choisir au hasard la direction et la grandeur du pas. Cet éventail de possibilités peut être discret (choix parmi un nombre fini de valeurs), ou continu.

Historique

L'idée de marche aléatoire a été introduite (sans le nom) en 1905 par le biostatisticien Karl Pearson pour rendre compte des migrations d'une population de moustiques dans une forêt. Pearson y pose la question suivante^[1] :

« Un homme part d'un point $O$ et parcours $l$ yards (0,914 m) en ligne droite ; il tourne d'un angle quelconque, et marche de nouveau $l$ yards en ligne droite. Il répète ce processus $n$ fois. Je demande la probabilité qu'après $n$ de ces trajets, il soit à une distance située entre $r$ et $r + d r$ de son point de départ. »

La réponse à cette question est fournie une semaine plus tard par Lord Rayleigh dans la livraison suivante de Nature : lorsque $n$ est suffisamment grand, cette probabilité vaut :

$dP(r) \ \sim \ \frac{1}{n \, l^2} \quad \mathrm{e}^{- \ \frac{\displaystyle r^2}{\displaystyle 2 \, n \, l^2}} \quad r \ dr$

Si Rayleigh fournit si rapidement la réponse, c'est qu'il a lui-même étudié en 1880 un problème connexe : le comportement d'une superposition d'ondes acoustiques toutes de même amplitude, mais de phases aléatoires. Pearson répond à Rayleigh le 10 août^[2] :

« J'aurais dû le savoir, mais mes lectures ces dernières années se sont déplacées vers d'autres centres d'intérêt, et on ne s'attend pas à trouver la première étape d'un problème de biométrie dans un mémoire sur l'acoustique. »

Pearson poursuit ensuite :

« La leçon de la solution de Lord Rayleigh est que, dans un pays ouvert, l'endroit le plus probable pour trouver un ivrogne encore capable de tenir sur ses pieds se trouve quelque part dans le voisinage de son point de départ. »

L'expression « marche aléatoire » n'a été introduite que vers 1919-1921 par le mathématicien hongrois George Pólya, qui utilisait le mot allemand « Irrfahrt ».

Marche aléatoire discrète à une dimension

Définition

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 $\mathbb{Z}$ . 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 choix possibles : sur cet exemple, un pas en avant ou un pas en arrière. Le seul paramètre libre du problème est un nombre réel p tel que : 0 < p < 1. L'interprétation physique de ce paramètre est la suivante :

p représente la probabilité que la particule fasse un saut en avant à chaque instant.

q = 1 - p représente la probabilité que la particule fasse un saut en arrière à chaque instant.

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é :

$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.

Marche aléatoire isotrope

Trois marches aléatoires (indépendantes) isotropes sur le réseau $\mathbb{Z}$ ; 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, le nombre X de fois où on a tiré "pile" suit la loi binomiale $B (n,1 / 2)$ , telle que la probabilité vaut :

$P(X=k) \ = \ \frac1{2^n} \ C_n^k$

où $C_n^k$ est le nombre de combinaisons de k éléments pris parmi n.

On peut relever la position en prenant la valeur 0 pour la marche initiale, en ajoutant 1 pour chaque pas en avant (pile), en retranchant 1 pour chaque pas en arrière (face). Alors la position Y est donnée par : Y = X - (n-X) = 2X - n. Par rapport à la loi binomiale classique il suffit donc de décaler les résultats de n/2 et de multiplier par 2, ainsi :

l'espérance est nulle ;
la variance vaut $n$ et l'écart type $\sqrt 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 \gg 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\sqrt{100}$ ).

Spécimens

La galerie ci-dessous contient quatre spécimens de marches aléatoires isotropes sur le réseau $\mathbb{Z}$ 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 1000 pas).

Marche aléatoire isotrope sur un réseau à x dimensions

Deux dimensions

Trois marches aléatoires (indépendantes) isotropes sur le réseau $\mathbb{Z}^2$ ; 10 000 pas.

On considère une marche aléatoire sur le réseau plan $\mathbb{Z}^2$ . 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

Spécimens

La galerie ci-dessous contient quatre spécimens de marches aléatoires isotropes sur le réseau $\mathbb{Z}^2$ après 10 000 pas, partant de l'origine.

Trois dimensions

On considère une marche aléatoire sur le réseau cubique $\mathbb{Z}^3$ . 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 $\mathbb{Z}^3$ ; 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.

Spécimens

La galerie ci-dessous contient quatre spécimens de marches aléatoires isotropes sur le réseau $\mathbb{Z}^3$ après 10 000 pas, partant de l'origine.

Projections bidimensionnelles

La trajectoire tridimensionnelle en violet est associée à ses trois projections orthogonales sur les plans (x,y) (courbe bleue), (x,z) (courbe grise) et (y,z) (courbe rouge).

Marche aléatoire isotrope sur un continuum à x dimensions

Deux dimensions

On considère la marche aléatoire sur le plan $\mathbb{R}^2$ définie par le processus suivant :

Trois marches aléatoires (indépendantes) isotropes sur le plan $\mathbb{R}^2$ ; 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 : $- \pi \le \alpha < + \pi$ .

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 :

$f(\alpha) \ = \ \frac{1}{2 \pi}$

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.

Spécimens

La galerie ci-dessous contient quatre spécimens de marches aléatoires isotropes sur le plan $\mathbb{R}^2$ après 10 000 pas, partant de l'origine.

Récurrence et dimensionnalité

Récurrence

Considérons une marche aléatoire isotrope sur le réseau $\mathbb{Z}^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^[3] 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.

Théorème de Pólya (1921)

Cette propriété de récurrence dépend fortement de la dimensionnalité de l'espace ; on peut en effet démontrer le théorème^[4] (Pólya - 1921)^[5] :

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] !

Probabilité de retour à l'origine en dimension supérieure ou égale à trois

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 (Montroll - 1956)^[7] :

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

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

$u(d) \ = \ \frac{d}{(2\pi)^d} \ \int_{-\pi}^{+\pi} \dots \int_{-\pi}^{+\pi} \ \frac{dx_1 \ \dots \ dx_d}{d \ - \ \cos x_1 \ - \ \dots \ - \ \cos x_d}$

Le cas particulier d = 3 avait en fait déjà été obtenu précédemment par Watson^[8], Mc Crea et Whipple^[9], et Domb^[10]. L'expression analytique de l'intégrale n'a été obtenue qu'en 1977 par Glasser et Zucker^[11] :

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

où $Γ(z)$ est la fonction Gamma d'Euler. On obtient donc en trois dimension une probabilité de retour à l'origine : $p(3) \simeq 0.3405373296$ , voisine de 34 pour cent.

Les expressions analytiques de u(d) ne sont pas connues en dimension d supérieure à trois. On obtient les valeurs numériques suivantes :

$p(4) \simeq 0.193206$

$p(5) \simeq 0.135178$

$p(6) \simeq 0.104715$

$p(7) \simeq 0.0858449$

$p(8) \simeq 0.0729126$

Marche aléatoire sur un graphe

Marche aléatoire continue

Très utilisée dans la modélisation de séries temporelles continues, une marche aléatoire peut s'écrire:

$X_{t}=X_{t-1} + \epsilon_{t} \qquad \mbox{avec le bruit blanc} \ \epsilon_{t} \ \sim \mathcal{N} (0,1)$

Il s'agit d'un cas particulier d'un processus autorégressif (c'est-à-dire « regressé sur lui-même ») avec $ρ = 1$ . La valeur du paramètre $ρ$ est très importante car elle change fondamentalement la propriété de la série :

$X t = ρ X t - 1 + ε t$

$|\rho| = \begin{cases} <1 & \textrm{Le \ processus \ est \ stationnaire}\\ =1 & \textrm{Marche \ aleatoire: \ le \ processus \ est \ donc \ non \ stationnaire}\\ >1 & \textrm{Le \ processus \ est \ explosif}\end{cases}$

De manière récursive, une marche aléatoire est simplement la somme de bruit blancs. On l'écrit:

$X_{t}= X_{0}+ \sum_{i=1}^{t} \epsilon_{i}$

Pour simuler une marche aléatoire, un petit exemple avec le logiciel de statistique R est montré:

a<-rnorm(100)# crée un vecteur "a" de 100 réalisation d'une loi normale (0,1).

b<-cumsum(a) # Crée un vecteur "b" dont chaque élément correspond à la somme cumulée des éléments de a.

plot.ts(b) #Crée un graphe (le ".ts" est utilisé pour "time series")

Marche aléatoire sur une variété riemannienne

Annexes

Bibliographie

Ouvrages de références

Joseph Rudnick & George Gaspari ; Elements of the Random Walk - An introduction for Advanced Students and Researchers, Cambridge University Press (2004), ISBN 0521828910.
Frank Spitzer, Principles of the Random Walk, Princeton University Press (1964). Réédité par Springer-Verlag (1970), ISBN 0-387-90139-6 ; 2^e édition dans la série Graduate Texts in Mathematics 34 (2001), ISBN 0-387-95154-7.
Daniel W. Stroock ; An Introduction to Markov Processes, Springer-Verlag (2005), ISBN 3-540-23451-9.
William Feller ; An Introduction to Probability Theory and its Applications (Volume 1), John Wiley & Sons(1968), ISBN 047125708-7.

Articles classiques

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 Publishing, Inc. (1954). Réédité dans la collection Phoenix (2003), ASIN 0486495353.
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 Publishing, Inc. (1954). Réédité dans la collection Phoenix (2003), ASIN 0486495353.

Bibliothèque virtuelle

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.

Marche aléatoire sur une variété riemannienne

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.

Notes et références

↑ Karl Pearson, [[Nature (revue)|]], 27 juillet 1905.
↑ Karl Pearson ; Nature (10 août 1905).
↑ S'il en existe un, il en existera en général une infinité. Le plus petit de tous ces instants finis est appelé instant de premier retour à l'origine. Cf. e.g. le chapitre 1 du livre de Daniel W. Stroock.
↑ Cf. e.g. le chapitre 1 du livre de Daniel W. Stroock
↑ Georg Pólya, Über eine Aufgabe der Wahrscheinlichkeitsrechnung betref-. fend die Irrfahrt im Straßennetz, Mathematische Annalen 83 (1921), 149–160.
↑ Yakov G. Sinaï ; Probability Theory - An Introductory Course, Springer-Verlag (1992), ISBN 3-540-53348-6, p. 71.
↑ E.W. Montroll ; Random Walks in Multidimensional Spaces, Especially on Periodic Lattices, Journal of the SIAM 4 (1956), 241-260.
↑ G.N. Watson ; Three Triple Integrals, Quarterly Journal of Mathematics, Oxford Series 2 10 (1939), 266-276.
↑ W. H. McCrea & F.J.W. Whipple ; Random Paths in Two and Three Dimensions, Proceedings of the Royal Society of Edinburgh 60 (1940), 281-298.
↑ C. Domb ; On Multiple Returns in the Random-Walk Problem, Proceedings of the Cambridge Philosophical Society 50 (1954), 586-591.
↑ M. L. Glasser & I.J. Zucker ; Extended Watson Integrals for the Cubic Lattices, Proceedings of the National Academie of Science U.S.A. 74 (1977),1800-1801.

Voir aussi

Liens externes

Expérience de marche aléatoire grandeur nature, dans une ville

Portail des probabilités et des statistiques
Portail de la physique

Ce document provient de « Marche al%C3%A9atoire ».

Catégories : Hasard et aléatoire | Probabilités | Physique statistique

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Marche au hasard de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

Marche Au Hasard — Marche aléatoire Trois marches aléatoires (indépendantes) isotropes sur le réseau ; 10 000 pas. En mathématiques et en physique théorique, une marche au hasard est un modèle mathématique d un système possédant une dynamique… … Wikipédia en Français
Marche aléatoire — Trois marches aléatoires (indépendantes) isotropes sur le réseau ; 10 000 pas. En mathématiques, en économie, et en physique théorique, une marche au hasard est un modèle mathématique d un système possédant une dynamique discrète… … Wikipédia en Français
hasard — (ha zar ; le d ne se prononce pas et ne se lie pas : un ha zar heureux ; au pluriel, l s ne se lie pas : des ha zar heureux ; cependant quelques personnes la lient : des ha zar z heureux) s. m. 1° Sorte de jeu de dés (sens propre et ancien,… … Dictionnaire de la Langue Française d'Émile Littré
Marché organisé — Bourse (économie) Pour les articles homonymes, voir Bourse. La Bourse de Bruxelles, terminée en 1873. Un … Wikipédia en Français
HASARD — Le hasard, que le calcul des probabilités a permis de maîtriser partiellement, apparaît d’abord comme un caractère fondamental de l’existence. Dans la mesure où l’incertitude enveloppe l’idée de risque, on a tenté de la réduire, dans le domaine… … Encyclopédie Universelle
Hasard — Cet article possède des paronymes, voir : Hazard et Azhar. Cet article concerne le concept de hasard. Pour le roman de J. M. G. Le Clézio, voir Hasard (roman). Le hasard exprime un manque de caus … Wikipédia en Français
HASARD — s. m. (H s aspire.) Fortune, sort ; cas fortuit, imprévu. S en remettre au hasard. S abandonner au hasard. Donner, mettre quelque chose au hasard. C est un pur effet du hasard. Le hasard voulut que... Coup de hasard. Ce sera un grand hasard si… … Dictionnaire de l'Academie Francaise, 7eme edition (1835)
Marche baissier — Tendance (économie) Pour les articles homonymes, voir tendance. La recherche de tendances statistiques est pratiquée en économie, où l on parle de tendance conjoncturelle et en finance pour les prix, les volumes, les rendements, etc. (ex: marché… … Wikipédia en Français
Marche haussier — Tendance (économie) Pour les articles homonymes, voir tendance. La recherche de tendances statistiques est pratiquée en économie, où l on parle de tendance conjoncturelle et en finance pour les prix, les volumes, les rendements, etc. (ex: marché… … Wikipédia en Français
Marché Baissier — Tendance (économie) Pour les articles homonymes, voir tendance. La recherche de tendances statistiques est pratiquée en économie, où l on parle de tendance conjoncturelle et en finance pour les prix, les volumes, les rendements, etc. (ex: marché… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Marche au hasard

Marche aléatoire

Sommaire

Historique