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

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.