Échos de la recherche Retour à la rubrique

Des marches aléatoires pas comme les autres

Piste verte Le 12 décembre 2011 - Ecrit par Bruno Schapira Voir les commentaires (2)

Où l’on ne parle pas seulement de marcheur ivre, mais aussi de conducteur ivre. L’histoire se passe en grande partie à Manhattan, un quartier aux caractéristiques encore bien mystérieuses...

Pour commencer : le modèle du marcheur ivre

Le problème est le suivant. Supposons qu’un promeneur complètement ivre
se déplace dans une rue bordée de lampadaires à intervalles réguliers.
À chaque fois que le marcheur arrive au niveau d’un lampadaire il s’agrippe à
celui-ci pour reprendre son souffle. Toutefois, comme il est complètement ivre, au moment de repartir, il ne se souvient plus de l’endroit d’où il vient.
Il repart donc dans un sens ou dans l’autre de manière aléatoire ; il a alors une chance sur deux de revenir sur ses pas, et une sur deux de continuer dans la même direction. En supposant que la rue est de longueur infinie la question est de savoir si « à coup sûr » [1], il finira par revenir à son point de départ.

La réponse est oui, et l’on dit dans ce cas que la marche aléatoire est récurrente. Une preuve de ce résultat se trouve à la fin de l’article.


Le marcheur ivre: La figure représente les 1000 premiers pas d’une trajectoire typique du marcheur ivre
(1 pas = 1 lampadaire rencontré). En abcisse le temps. En ordonnée, la localisation du marcheur.

: Une autre simulation de 8 trajectoires du marcheur ivre.

On peut maintenant imaginer que notre marcheur se trouve à Manhattan, New-York (U.S.A.). Ce quartier de la ville est quadrillé par de longues avenues du nord au sud, et rues d’est en ouest, un peu comme les feuilles de mon bloc notes. Cette fois à chaque croisement notre marcheur fait une pause, et comme il est vraiment ivre, il repart aléatoirement dans une des quatre directions possibles, avec une chance sur quatre pour chacune d’elle. En supposant que Manhattan s’étende sur une surface infinie, la question que l’on se pose est la même que dans le problème précédent....

....et la réponse également, mais la preuve est plus compliquée [2]. En effet, le marcheur a une plus grande marge de manœuvre pour « s’enfuir à l’infini ». Par exemple il pourrait par hasard tourner en rond autour de son point de départ, sans jamais y repasser.


Marcheur ivre à Manhattan: Les 1000 premiers pas d’une trajectoire simulée du marcheur ivre à Manhattan (1 pas = 1 croisement visité).

: Une autre simulation de trajectoire avec plus de pas...


Marcheur ivre à Manhattan bis: Encore une nouvelle trajectoire après 25 000 pas.

Après ces exemples en dimension un et deux, on peut être tenté, tout-à-fait légitimement, de vouloir généraliser le problème en dimension supérieure. Comme plus la dimension augmente, plus le marcheur a une grande liberté de mouvement, la question se pose naturellement de savoir s’il n’existerait pas une dimension critique au-delà de laquelle, le marcheur aurait une probabilité non nulle de ne jamais revenir à son point de départ, auquel cas nous dirons que la marche aléatoire est transiente. Bien sûr la réponse est oui [3] (sinon ce serait moins drôle), et la dimension critique est la dimension trois. Moralité : ne pas laisser ses enfants se déplacer sans surveillance dans un centre commercial à plusieurs niveaux (sauf si vous souhaitez avoir une chance de vous en débarrasser).


Marcheur ivre dans un monde en 3D

L’exemple moins connu du conducteur ivre

Cet exemple est en effet beaucoup moins connu, y compris des spécialistes de la théorie des probabilités, mais ce n’est là qu’une injustice flagrante, que nous nous proposons modestement par cet article de combattre. En effet tout le monde sait bien que les New-yorkais ne se déplacent à pied qu’en dernier recours, et utilisent plus volontiers, soit leur propre voiture, soit un taxi !

Il est donc bien plus vraisemblable que notre marcheur ivre se déplace en voiture. Or il faut savoir qu’à Manhattan les rues et avenues sont toutes [4] à sens unique, et orientées alternativement dans un sens puis dans l’autre. Ainsi une avenue sur deux n’est empruntable que du nord au sud (on dira aussi qu’elle est orientée vers le sud), et une sur deux du sud vers le nord (on dira qu’elle est orientée vers le nord). Idem pour les rues. Par ailleurs, notre conducteur, tout ivre qu’il soit, n’en respecte pas moins scrupuleusement le code de la route [5].
À chaque carrefour, il n’a donc que deux possibilités pour continuer, qu’il choisit chacune avec une chance sur deux. On peut encore montrer que cette marche aléatoire est récurrente [6].

Une idée de preuve

Appelons avenues paires les avenues situées à une distance paire de l’avenue d’où part notre conducteur. On peut définir de même la notion de rue paire. Alors si l’on ne regarde la position du conducteur que tous les deux carrefours rencontrés, et si l’on identifie tout carrefour situé à l’intersection d’une avenue paire et d’une rue paire avec ceux situés immédiatement à sa droite et au dessus, on s’aperçoit que la trajectoire observée est équivalente à la trajectoire du marcheur en dimension deux vu dans la partie précédente, dont on sait qu’il revient à coup sûr à son point de départ. Ce n’est ensuite pas difficile d’en déduire la propriété de récurrence pour le conducteur ivre.

Il existe une variante intéressante de ce modèle.
Dans l’exemple précédent les rues et avenues étaient orientées suivant un ordre déterministe, à savoir alternativement dans un sens puis dans l’autre. Supposons maintenant qu’elles le soient de manière aléatoire, avec une chance sur deux pour chaque orientation possible, et supposons par ailleurs que les choix de toutes ces orientations soient fait indépendamment les uns des autres.
Une fois ces choix faits, laissons alors notre conducteur ivre effectuer sa promenade aléatoire dans ce nouvel environnement, qui est donc lui-même aléatoire. Eh bien cette fois-ci on ne sait pas montrer s’il reviendra à coup sûr ou pas à son point de départ. On dit que l’on est face à un problème ouvert [7].

Il faut savoir que ce cas de figure - une question élémentaire non résolue portant sur un modèle relativement simple - a de quoi frustrer beaucoup de mathématiciens.

Dans ce type de situation plusieurs solutions s’offrent à eux. L’une d’elle consiste à passer rapidement à un autre problème, en espérant éventuellement qu’une nouvelle idée vienne plus tard. Une autre est d’essayer de voir si en simplifiant le modèle, ils ne pourraient pas répondre à la question posée (ici savoir si la marche est récurrente ou transiente). Ceci pas seulement dans le but de sauver la face, mais aussi parce que cela permet parfois de reconsidérer les choses sous un nouvel angle, ce qui peut s’avérer très utile y compris pour le modèle initial.

Ici il existe une façon assez naturelle de simplifier les choses : il suffit tout bêtement de supposer que seules les avenues sont à sens unique. Autrement dit à chaque croisement le conducteur peut choisir parmi trois directions possibles, chacune avec une chance sur trois. Alors là, un petit miracle se produit et l’on peut montrer que la marche est récurrente [8].

Un dernier exemple pour finir

Terminons cette rapide intrusion dans le monde des marches aléatoires par un
exemple de marche « avec mémoire ». En termes mathématiques, on dit de ce type de processus qu’il ne possède pas la propriété de Markov [9].

Un exemple parmi d’autres est le suivant [10] : supposons que notre marcheur de Manhattan soit un peu joueur en plus d’être ivre. Pour une raison bien mystérieuse, il décide à chaque croisement qu’il découvre pour la première fois, de ne continuer son chemin que dans l’avenue (orientée Nord/Sud) qui passe par ce croisement, mais toujours dans un sens ou dans l’autre avec une chance sur deux. Inversement lorsqu’il arrive à un croisement par lequel il est déjà passé, il ne s’autorise à continuer que dans la rue (orientée Est/Ouest) qui coupe ce croisement, et toujours dans un sens ou dans l’autre avec une chance sur deux.

On ne sait toujours pas à l’heure actuelle si cette marche aléatoire est récurrente ou non [11].

Preuve de la récurrence en dimension 1 et une petite énigme.

Montrons que le marcheur ivre en dimension un (celui qui se déplace dans une rue infinie) revient à coup sûr à son point de départ. Pour aller plus vite nous noterons $0$ ce point.
Nous appellerons également distance entre la position du marcheur et $0$, le nombre de lampadaires qui séparent le marcheur de $0$. Remarquons maintenant qu’à chaque pas, le marcheur a autant de chance de se rapprocher de $0$ que de s’en éloigner. On en déduit que si celui-ci se trouve à un moment à une distance $d$ de $0$, alors il a autant de chance de repasser par $0$ avant de s’éloigner d’une distance $2d$ de $0$, plutôt que l’inverse (i.e. arriver à une distance $2d$ de $0$ avant de repasser par $0$).
On peut alors raisonner comme suit. Après avoir atteint pour la première fois un nouveau lampadaire, il est à distance $1$ de son point de départ. Il a donc une chance sur deux de revenir en $0$ avant d’arriver à distance $2$ de $0$, et une chance sur deux de faire l’inverse. Dans le deuxième cas, il est donc arrivé à distance deux avant de revenir en $0$. Mais ensuite il a encore une chance sur deux de revenir en $0$ avant d’arriver à une distance $4$ de celui-ci. Donc, après son premier pas, il n’a qu’une chance sur quatre d’arriver à une distance $4$ de $0$ avant de repasser par $0$, et trois chances sur quatre de faire l’inverse. Mais on peut continuer ce raisonnement à l’infini. Par exemple après son premier pas il n’a qu’une chance sur $8$ d’arriver à une distance $8$ de $0$ avant de repasser par $0$, et sept chances sur huit de faire l’inverse. En général, pour tout entier $n\ge 1$, après son premier pas, il n’a qu’une chance sur $2^n$ de s’éloigner d’une distance $2^n$ de $0$ avant de repasser en $0$.
Comme $1/2^n$ devient infiniment petit, lorsque $n$ tend vers l’infini, on en déduit qu’il n’a aucune chance de ne jamais revenir en $0$ après son premier pas, ce qui démontre le résultat voulu. $\square$

En fait cette preuve est incomplète. On a en effet implicitement admis que lorsque le marcheur se trouve à une distance $d$ de $0$, il finira nécessairement à un certain moment soit par revenir en $0$, soit par arriver à une distance $2d$ de $0$. Pouvez-vous démontrer ce fait ?

Un indice pour résoudre l’énigme.

On pourra utiliser (et démontrer) le résultat suivant : pour tout nombre $p\in ]0,1]$, si je joue une infinité de fois à un jeu où j’ai à chaque fois une
probabilité égale à $p$ de gagner, alors je suis sûr de gagner au moins une fois.

Il ne reste plus qu’à trouver un jeu qui soit bien adapté au problème...(il existe plusieurs solutions !)

Référence

[CaPe-03] M. Campanino et D. Petritis, Random walks on randomly oriented lattices, Markov Process. Related Fields 9 (2003), 391—412.

Post-scriptum :

Je remercie, pour leur relecture attentive, les relecteurs dont le pseudonyme est le suivant : projetmbc, Daniel Massart et Robin Jamet. Merci également à Frédéric Le Roux pour m’avoir proposé d’écrire cet article et pour ses conseils, et à Nadine Guillotin-Plantard pour m’avoir montré sa preuve de la récurrence sur le réseau Manhattan orienté.

Article édité par Frédéric Le Roux

Notes

[1] Cette expression, ainsi que toutes celles qui vont suivre entre guillemets, mériterait quelques précisions, mais cela nécessiterait de se placer à un niveau de technicité qui dépasserait le cadre fixé dans cet article. Nous nous en tiendrons donc à l’idée intuitive qu’elle évoque. Toutefois le lecteur prendra garde au fait que « à coup sûr » ne veut pas dire que toutes les trajectoires possibles repassent par le point de départ. En effet il n’est pas interdit au marcheur de continuer toujours dans la même direction. Mais le point important ici est qu’il a en fait une probabilité nulle de faire une infinité de choix prédéterminés (comme aller toujours à droite à chaque coup).

[2] On trouvera une autre présentation de ces deux modèles dans l’article de Françoise Pène.

[3] Ce résultat est attribué à Pólya (1921).

[4] du moins nous ferons comme si pour les besoins de l’exposition.

[5] Il est ainsi des personnes qui n’ont qu’un sens partiel des responsabilités.

[6] Ce résultat est dû à Nadine Guillotin-Plantard.

[7] On conjecture qu’il a en fait une probabilité non nulle de ne jamais revenir à son point de départ.

[8] Voir le très bel article de
Campanino et Petritis [CaPe-03].

[9] C’était en fait déjà le cas des exemples vus dans la partie précédente, lorsque les orientations sont choisies aléatoirement.

[10] Cet exemple est dû à Itai Benjamini.

[11] Toutes les suggestions pour résoudre ce problème sont les bienvenues...

Commentaire sur l'article

Des marches aléatoires pas comme les autres

le 15 décembre 2011 à 22:56, par Julien

Pour la partie concernant le conducteur ivre avec orientation aléatoire, ne faut-il pas supposer que le graphe est fortement connexe ? Il y en a avec des puits desquels l’on ne pourrait plus sortir.
Répondre à ce message

Des marches aléatoires pas comme les autres

le 16 décembre 2011 à 14:33, par Bruno Schapira

je ne suis pas sûr de comprendre l’objection, mais tu as peut-être en tête le cas des graphes orientés aléatoirement ? ici il faut bien garder en tête que chaque avenue (et même chose pour les rues) est orientée dans la même direction d’un bout à l’autre. On ne peut donc pas créer de circuit fermé fini dont on ne pourrait pas s’échapper...

Sinon je signale un point ambigu dans le texte, juste avant la note [8]. Lorsque seules les avenues sont à sens unique, deux cas sont possibles : si les orientations sont choisies suivant un ordre déterministe (une sur deux orientée vers le nord, et une sur deux vers le sud), alors la marche aléatoire est bien récurrente. Si en revanche les orientations de ces avenues sont choisies aléatoirement, alors on peut montrer que la marche aléatoire est transiente.
Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexion | s’inscrire | mot de passe oublié ?

L'auteur

Bruno Schapira

Maître de conférences a l’université d’Orsay