Des marches aléatoires pas comme les autres
Piste verte Le 12 décembre 2011 Voir les commentaires (3)
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.
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é).
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).
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].
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].
Référence
[CaPe-03] M. Campanino et D. Petritis, Random walks on randomly oriented lattices, Markov Process. Related Fields 9 (2003), 391—412.
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é.
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.
[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...
Partager cet article
Pour citer cet article :
Bruno Schapira — «Des marches aléatoires pas comme les autres» — Images des Mathématiques, CNRS, 2011
Laisser un commentaire
Actualités des maths
-
6 février 2023Journées nationales de l’APMEP, appel à ateliers (9/4)
-
20 janvier 2023Le vote électronique - les défis du secret et de la transparence (Nancy, 26/1)
-
17 novembre 2022Du café aux mathématiques : conférence de Hugo Duminil-Copin (Nancy et streaming, 24/11)
-
16 septembre 2022Modélisation et simulation numérique d’instruments de musique (Nancy & streaming, 22/9)
-
11 mai 2022Printemps des cimetières
-
3 mai 2022Comment les mathématiques se sont historiquement installées dans l’analyse économique (streaming, 5/5)
Commentaire sur l'article
Des marches aléatoires pas comme les autres
le 15 décembre 2011 à 22:56, par Julien
Des marches aléatoires pas comme les autres
le 16 décembre 2011 à 14:33, par Bruno Schapira
Des marches aléatoires pas comme les autres
le 24 février 2021 à 01:57, par MS1729