on December 10, 2016, at 07:22 PM

Mouvement brownien

Cet article est encore en construction. Désolé.

Robert Brown, biologiste en 1824 observait dans le fluide situé à l’intérieur des grains de pollen de la Clarkia pulchella de très fines particules qui s'agitaient de façon apparemment erratique. Brown décrivait alors un processus qui porte maintenant le nom de mouvement brownien et qui continue à être un sujet d'étude. Norbert Wiener père de la cybernétique en a donné une définition mathématique, presque 100 ans plus tard en 1923 en construisant une mesure de probabilité sur l'espace des fonctions continues réelles, appelée processus de Wiener. Il a montré la continuité et non-dérivabilité des trajectoires du mouvement brownien, cela se traduit sur la trajectoire visible des particules par le fait qu'elle ne comporte pas de saut mais par contre qu'elle est très tortueuse (il n'est pas possible de tracer une tangente en un point quelconque de la trajectoire). La continuité et la non-dérivabilité posent un problème lorsque l'on veut en construire un modèle simulable informatiquement, c'est pourquoi on utilise en général un modèle discret ressemblant à la description d'un homme alcoolisé qui "approche" le phénomène.

Marche aléatoire

Un homme ivre habitant à la campagne, part de sa maison et marche alors dans les champs environnants que l'on va supposer infinis. À chaque pas, il choisit au hasard d'aller dans l'une des directions possibles : nord, nord-est, nord-ouest, sud, sud-est, sud-ouest, est ou ouest. Il a alors une chance sur 8 d'emprunter l'une des directions. Le trajet qu'il réalise est appelé marche aléatoire. Si le mouvement brownien est continu, la marche aléatoire est elle discrète. Notre poivrot se comporte comme une "puce" en parcourant un ensemble de points à coordonnées entières. Cette méthode est intéressante à plus d'un titre, tout d'abord elle peut être simulée facilement à l'aide d'un petit programme informatique, mais en plus en effectuant des changements d'échelle elle approche à la limite le processus de Wiener. De plus, notre homme alcoolisé a une probabilité de 1 de pouvoir rentrer chez lui, malgré une méthode un peu hasardeuse. En effet, le théorème de Polya nous affirme que pour des espaces de dimension 1 ou 2, la marche aléatoire isotrope (on se déplace de la même façon dans les 4 directions) est récurrente, autrement dit, notre marcheur fini toujours par repasser par son point d'origine (ce n'est pas vrai pour un goéland bourré qui tente de rentrer à son nid !).

On peut regarder le problème également sur une grille et observer la couverture de cette grille ainsi que mesure l'efficacité qui diminue à chaque fois que l'on passe sur un lien déjà parcouru.

La structure sur laquelle notre homme ivre se déplace est donc une structure discrète régulière (une grille), mais on peut également considérer le problème sur une structure non régulière représentée par un graphe, un ensemble de sommets reliés par des liens souvent appelés arcs ou arêtes. Ce graphe peut représenter un réseau routier, un plan de ville, ou un réseau social par exemple.

Marche aléatoire dans un graphe

Supposons donc maintenant que notre enivré se déplace maintenant des les rues d'une ville représentée par un graphe. Comme précédemment nous allons considérer que le temps est discrétisé (t = 0, 1, 2, ...., N). À chaque pas de temps t, le marcheur est donc sur un des sommets du graphe et se déplace au pas de temps suivant t+1 vers un sommet choisi au hasard et de façon équiprobable vers un autre sommet (l'un des sommets voisins ou le sommet lui-même). On peut calculer la probabilité {$P_{ij}$} lorsque le marcheur est sur le sommet i pour qu'il atteigne le sommet voisin (incident) j, cela va alors dépendre du degré du sommet (le nombre de voisins) i. {$$ P_{ij} = \frac{1}{d(i)+1} \mbox{ avec } d(i) \mbox{ degré de }i$$} En fixant un sommet de départ , on peut calculer la probabilité que le marcheur se retrouve sur un sommet j après un chemin de longueur "t". {$$ p_{t+1}(j) = \sum_i p_t(i) \frac{a_{ij}}{d(i)+1} \mbox{ avec } a_{ij} = \left\{

    \begin{array}{ll}
        1 & \mbox{si } i \mbox{ est voisin de } j
0 & \mbox{sinon.} \end{array}

\right. $$}

(:netlogo codebase="RandomWalkGraph" code="org.nlogo.lite.Applet" archive="NetLogoLite.jar" width="500" height="500" DefaultModel="RandomWalkInGraph.nlogo":)

  • Layout remet en forme le graphe
  • Update la distance est accrue de 1 à partir du sommet initial.

Cette applet NetLogo montre la dynamique de la marche aléatoire. Notre poivrot part du sommet rouge i valué à 100% et les valeurs reportées sur chacun des sommets j sont les probabilités {$P^t_{ij}$} en pourcentage après t pas.

Propriétés

On peut déterminer des propriétés intéressantes pour une telle marche. Si on considère un graphe G non orienté, connexe (à partir d'un sommet quelconque on peut atteindre n'importe quel autre sommet du graphe) et apériodique (il n'y a pas de boucle (i, i)), il a été montré que toute marche aléatoire à l'infini converge vers la probabilité :

{$$\lim\limits_{t\to +\infty} p_t(i) = \frac{d(i)}{\sum\limits_j d(j)} $$}

Cela se traduit par le fait que si vous réalisez une marche aléatoire "suffisamment" longue, la probabilité de présence sur un sommet donné ne dépend que du nombre de voisins de ce ce sommet.

Marche aléatoire biaisée

Nous présenterons sans doute dans un futur lointain le principes des algorithmes fourmis.

Théorie de la dérive rédigée par le situationniste

Guy-Ernest Debord
Théorie de la dérive
Dans Les lèvres nues n°9
Décembre 1956
texte

Guy Debord était un poète et écrivain situationniste et dans son texte La théorie de la dérive il nous propose de revisiter l'espace urbain en reconsidérant la façon dont on le vit. Pour cela plutôt que nous déplacer de façon quasi automatique emprisonné par nos habitudes, la dérive nous encourage à ressentir des émotions et les suivre. Dériver au Havre, guidé par les odeurs de torréfaction café, puis au détour d'une rue être attiré par les bips des engins de manutention portuaires. La psychogéographie s'approche de ce courant.

Psychogéographie virtuelle avec google
http://www.youtube.com/watch?v=8_5UzPTnawc&feature=related

http://www.youtube.com/watch?v=4kTukct98vA

http://mappemonde.mgm.fr/actualites/M_toulouse2.html

Sources : Photo Clarkia pulchella http://www.robsplants.com/plants/ClarkPulch

Leave a comment

Name (required)
E-mail (required, will not be published)
Website
Comment

Enter value: (:input captcha tabindex=1:)