Marche aléatoire sur un groupe finiment engendré

par Xavier Bressaud (Institut de Mathématiques de Luminy)


On va manipuler trois groupes.Ou plutot trois familles de groupes, indexees par un entier. Ils ont chacun leur lettre : Zn, Fn et Bn. On peut les definir de maniere unifiée à travers leur présentation en générateurs/relations.

Zn = < a1, ..., an ; aiaj = ajai>

Fn= < a1, ..., an>

Bn = < a1, ..., an ; aiaj = ajai, |i-j|>1 ; aiai+1ai=ai+1aiai+1>

Bon, Zn n'est rien d'autre que ce a quoi on s'attend. Ça passe par l'isomorphisme w <-> (|w|a - |w|a)a=1,...,n. Ca se demontre s'il le faut. (On pourrait aussi causer de Zn, pour avoir un groupe fini). Avant de penser au groupe libre, on peut penser au monoide libre, dans lequel l'absence de relations est encore plus frappante. Fn est l'ensemble des mots finis qu'on peut ecrire, sans annulations. On peut le voir comme l'ensemble des chemins dans Zn. Nous avons deja vu une representation "geometrique" de Bn. On peut visualiser les generateurs (et aussi les relations) a l'aide d'une projection. On peut les voir de bien d'autres manieres.

Une marche aléatoire sur un groupe G est caracterisée par la donnée d'une mesure de probabilité m sur le groupe (appelée loi des saut). L'idée est la suivante. On demarre quelque part. Par exemple  à l'origine (element neutre), ou en un point choisi au hasard avec une (autre) mesure de probabilité, la mesure initiale.  Soit g0 ce point. On appelle gn la position de la marche a l'instant n. Connaissant gn, on choisit gn+1 en tirant au hasard un element sn  du groupe (le saut) dans G avec la probabilité m et en posant gn+1=gn sn (marche a droite) ou gn+1= sn gn (marche a gauche). La marche est dite symetrique si m(s)=m(s). Une marche aléatoire est un processus de Markov sur G. Il peut etre commode de la presenter d'autres manieres. Elle est isomorphe dans un sens a Gn muni de la loi des sauts. On peut aussi la  voir comme le shift sur l'espace des chemins dans G. Pour y penser "graphiquement", dans le cas d'un groupe discret, on peut la "regarder" sur le graphe de Cayley de G. 

Si le groupe est presenté en generateurs/relations, il est naturel de se limiter a une mesure m supportee sur l'ensemble des generateurs (et leurs inverse). On dit que la marche est uniforme si la probabilité de chacun des générateurs est la même (soit 1/2|S|). C'est de celle la qu'on parle quand on parle de "la" marche aléatoire sur un groupe G dont on a une presentation G/R.

Exemples

Les entiers

La marche aléatoire sur Z est un grand classique. Elle est recurente. Elle repasse une infinité de fois a l'origine (et d'ailleurs une infinité de fois partout) avec probabilité 1. Mais elle est recurente nulle. C'est à dire que la probabilité de se trouver en 0 décroit avec le temps. Ou encore que l'espérance du temps de retour en 0 est infinie. Les excursions hors de l'origine sont "independantes". On a un theoreme de limite centrale. La marche  se "renormalise" en un mouvement Brownien sur R.

Sur Z, on peut s'interesser aussi aux marches non symetriques. Choisissons par exemple m(+1) = 3/4 et m(-1) = 1/4. Cette marche est transciente. Elle part vers l'infini (a droite, + l'infini), avec proba 1. On peut meme calculer sa vitesse de fuite qui est la limite de Xn/n et qui vaut 1/2. Si on regarde la marche - n/2, on recupere un objet assez proche de la marche symetrique.

La marche aléatoire sur Z2 a sensiblement les memes proprietés. On peut aussi lui imposer une derive.

Les choses se corsent sur Zn. Les marches uniformes sont transcientes. Elles ne passent qu'un nombre fini de fois a l'origine (avec probabilité 1). La probabilité que le temps de retour a 0 soit infinie est strictement positive.  Mais, ici, elles "s'en vont" a vitesse nulle (|Xn|/n tend vers 0).

Les groupes libres

F1 = Z. Mais la marche sur F2 a un comportement radicalement opposé. Que se passe-t-il ? On ecrit un mot en chaoisissant a chaque etape une lettre aléatoirement parmi 4 lettres. En general, le mot se rallonge d'une lettre, suaf si on tire justement l'inverse de la lettre qui terminait le mot à l'étape précédente. Dans ce cas, au contraire, on efface une lettre. (Si on est a l'origine, chacun des choix de generateur nous pousse a une distance 1 de l'origine, mais c'est le seul cas). Si on regarde la "longueur" du mot ecrit, on voit que c'est elle meme une marche aléatoire sur Z+ , reflechie a l'origine, et avec une loi de sauts m(+1) = 3/4 et m(-1) = 1/4 ailleurs. Comme la marche asymetrique sur Z, elle file a l'infini. Mais, la elle laisse des traces. C'est a dire que le mot qui reste ecrit a la fin des temps depend de ce qui s'est passé. (C'est clair que le mot ecrit converge. Dans quel sens d'ailleurs).

Un objet qui nous interesse "hautement" est l'ensemble des mots infinis qui peuvent etre ecrit, "muni de leur probabilité". C'est, disons, l'ensemble des comportement asymptotique de la marche. C'est aussi une compactification du groupe. Derriere ca il y a l'idée de "frontière", de "bord" du groupe. Notion a priori un peu floue a laquelle on peut donner différents sens précis, selon les contextes.

Ici un objet naturel s'impose (assez universellement). C'est le sous shift (de type fini) des mots infinis ne contenant pas les mots aa, aa, bb, ni bb, muni de la mesure d'entropie maximale. On conçoit que les mots ecrits soient ceux la et qu'aucun ne soit privilegié par rapport aux autres (non ?).

Ce qui se passe ici est typique d'une situation hyperbolique. On classifie un peu les groupes en fonction des proprietés des marches. Croissance exponentielle, Moyennabilité sont reliées a des comportement des marches.


Les groupes de tresses

La marche aléatoire sur un groupe de tresses, même B3, est d'analyse combinatoire beaucoup moins directe. Cela tient d'une certaine maniere a la difficulté d'identifier deux mots comme même élément du groupe. Il existe bien des formes normales. Mais justement, a priori, aucune ne s'impose. Prenez votre forme normale préférée. Et essayez. Sauf si vous avez des gouts baroques, le phénomène suivant devrait se produire. Vous commencez a observer la marche, c'est a dire que vous voyez des generateurs. A chaque etape, vous recuperez un element du groupe. Pour l'identifier, vous essayez de l'ecrire sous sa forme normale (sinon, vous risquez de voir ababab et de ne pas réaliser que vous etes revenu a l'origine). Jusque la tout va bien. Avec un peu de chance (et encore, avec certaines formes normales ca n'arrive meme pas), vous allez voir un mot assez long se former. La fin du mot change (et pas seulement la toute dernière lettre) mais le debut se stabilise. Et pof, a un moment, vous ajoutez un generateur, et quand vous essayez d'ecrire la forme normale de l'element obtenu vous realisez que le mot ecrit n'a rien a voir avec le précédent. Ou du moins que des changements se produisent au début du mot. Bon, vous continuez... Mais le meme phenomene se reproduit regulierement (ou du moins assez souvent) pour que vous ne puissiez identifier de mot "limite". Par exemple.

D'ou l'idee de chercher une forme normale stable. Comment donner une definition precise. Il faut eviter les trivialités. Puis definir formellement ce que veut dire qu'elle donne une information complete sur la frontiere dans un sens plus abstrait. Ensuite, il y a des questions de vitesse de convergence.

Mais, pour ces marches, il y a des choses simples qu'on peut dire avant de disposer d'une telle forme normale.

Tout d'abord, la marche est transciente (A part B2 =Z). Argument.
La vitesse est positive. On peut la calculer.
Ensuite la frontiere n'est pas triviale.

Nous allons maintenant nous concentrer sur les groupes de tresses. Evidement, les deux autres exemples seront toujours présents (comme outils). L'analyse suivante si elle est motivée par les questions soulevées par les marches aléatoires, a du sens independament.

Action des tresses sur le groupe libre et sur les feuilletages.

On peut presenter l'action sur le groupe libre de maniere directe. Mais l'interpretation géometrique nous interesse aussi beaucoup.

Definition

Considerons la famille de morphismes du groupe libre Fn definie comme suit:

gi :   (a1, ..., ai, ai+1, ...,an) -> (a1, ..., ai+1, ai+1aiai+1, ...,an)
et leurs inverses,
gi :   (a1, ..., ai, ai+1, ...,an) -> (a1, ..., aiai+1ai, ai, ...,an)

On peut verifier que le sous groupe engendré par ces générateurs est exactement le groupe des tresses. Une maniere de voir est de s'assurer qu'il satisfait les relations (facile) mais ne satisfait que ces relations (voir la preuve).  Un morphisme est completement determiné par les images des générateurs. Une tresse peut donc etre vue comme la donnee de 3 (ou n)  mots correspondant a ces images. Attention, tous les mots ne sont pas des images de lacets.

Premieres evidences. L'image d'un lacet est de la forme  hah, ou h est un mot et a une lettre. La lettre est relie par une permutation au lacet dont c'est l'image. L'autre contrainte est que le lacet doit etre simple (sans auto intersection). Cela est nettement plus difficile a voir symboliquement.

Interpretation géometrique

Comment voir ca ? Prenons un disque. perçons 3 (ou n) trous. Le groupe fondamental de cette surface est le groupe libre a 3 (ou n) éléments. Chaque lettre correspond a a un lacet orienté. On voit les choses facilement si on  trace trois segments (reliant les points au bord du disque). Ce qui reste est un disque topologique. Toutes les lacets y sont homotopes a un point. Ce qui compte dans le disque initial est donc decrit par les traversees (orientees) des segments.... Faire des dessins.

Recodage d'un lacet

On va s'interesser un moment aux lacets simples contenant un point. Ce sont des images par une tresse d'un lacet de base. On va jouer un peu avec. Plusieurs actions. Prolongation, raccourcissement par ouverture. Tresse. Codage au plus proche. Si vous voulez des details.

Deloopage

Un point important est d'arriver a delooper un lacet. On entend par la donner une suite de générateurs (du groupe de tresse) qui produise ce lacet. Une etape supplementaire consiste a delooper simultanement 3 (ou n) lacets de maniere a retrouver l'unique (a permutation pres) tresse qui ait pu le produire. Une remarque importante est qu'on peut retrouver la tresse complete en deloopant un lacet suffisament long (contenant suffisament d'information).

Stabilisation dans B3

Nous avons assez d'elements intuitifs pour prouver notre resultat dans B3.

Definition

On definit B3 par une présentation générateurs/relations:

B3 = < a,b ; aba=bab>

On considère la marche aléatoire uniforme sur ce groupe, ainsi présenté. Autrement dit, on regarde SN={a,b,a,b}N muni de la mesure produit (1/4,1/4,1/4,1/4)N. On note (gn) un element de SN. La marche aléatoire est le processus (Xn) defini sur B3 par, X0 = e, et,

Xn+1 = Xn .gn.

Frontiere

Theoreme

Action sur le groupe libre F3

Definition

B3 agit sur le groupe libre.
On appelle O l'orbite d'un lacet fondamental.

Etude de O

Lemme: On etablit une bijection entre O et un sous shift de type fini STS sur {A,B,C}N.

Pas tout a fait, a cause du debut. En fait, on etablit une bijection entre O et O = Z x s3 x STS. Bon, il faut voir, on peut se passer de Z, mais c'est plus simple pour decrire les choses apres.

Géometriquement, le triplet (m, s, (Un)) s'interprete comme ça. On fait m tours (algebriques) autour de nos trois points, organisés suivant la permutation s, avant de commencer a se promener entre les points. On peut ecrire la bijection algorithmiquement, mais pas vraiment explicitement.

Plus precisement, avec la decomposition, un mot s'ecrit (s(A)s(B)s(C))[m/2] t(s,m,x0) x.
Si m < 0 on inverse ABC en CBA.
Si m est pair, t(s,m,x0) = s(B). Si m est impair, alors ca depend du signe. t(s,+,s(A)) = s(AB), t(s,+,s(C)) = s(A), et t(s,-,s(A)) = s(C), t(s,-,s(C)) = s(CB). Essentiellement, il y a deux cas ou le "B" qui devrait apparaitre n'apparait pas (on lui passe en dessous parcequ'on arrive par l'autre coté. Voir dessin).


Action de B3 sur O

L'interet de O est que l'on peut decrire simplement l'action de B3.

On peut a partir de la distinguer 4 situations sensiblement differentes. Pour alleger, placons nous dans la sitution ou s=id. On distingue suivant la parité de m (m=0 ou 1, mod1) et suivant que x0 = A ou C.
Un petit dessin montre que  (m,x) est envoyé sur (m±1,x) avec proba 1/4, (m,T(x)) avec proba 1/4 ou sur  (m,Bx) avec proba 1/2. Bon il faut quand meme verifier formellement qu'on ne touche pas a x. Un argument topologique devrait y parvenir.

A partir de la, il ne devrait pas couter grand chose de montrer que la longueur du code tend vers l'infini a vitesse  1/4. Cela doit aussi nous donner la mesure "invariante" sur les codes, que j'ai du mal a imaginer differente de la mesure d'entropie maximale sur le sous shift. Mais il faut prendre des precautions a cause du demarrage (On a privilegié un point de départ).

Detricotage

Maintenant il s'agit de detricoter un lacet. La on y va brutalement. Si la permutation est fixee (s=id), il y a 4 possibilités. Soit on commence par A (m>0), soit par BC (m=0), soit par BA (m=0), soit par C (m<0). On va se donner une maille differente pour detricoter (d'un cran) chacune de ces situations.

Pour A, on fait a b. Pour BC, on fait b. on fait a, et, pour C, on fait ba. C'est a dire qu'on a un t[s,X0X1] tel
que t[s,X0 X1](s,X) = (s',T(X)). On en déduit une suite tX telle que  tX(s,X) = (id, ¢), avec tX =  tn  ... t1t0. Chacune des tresses elementaires est de longueur 1 ou 2. A priori il peut y avoir des annulations. Mais il peut aussi y avoir des raisons pour qu'il n'y en ait pas. En effet, tout ne peut pas etre suivi par n'importe quoi...

Il apparait apres une petite etude triviale qu'on commence par derouler, soit avec une suite de a b, soit avec une suite de ba, puis qu'on utilise uniquement une suite de a et de b. Ce qui a l'air d'etre assez proche de la forme normale de Garside, non ? On obtien des formes normales du type (a b)m un ... u1, avec ui = a ou b. Bon, ca, ca deroule un lacet, mais ca ne redonne pas "la" tresse. Il faut decider avec quel lacet on demarre.

Forme normale

L'idee serait de demarrer avec un lacet infini, qui passe un peu partout pour eviter des trivialités. On montre alors que le debut peut etre rogné un peu, mais que par la transcience, la fin doit coincider. A partir de la, on reconstruit. Mais ca change un peu la forme normale.

Lemme: Une tresse est completement determinée par l'image d'un lacet non quadratique (de codage non periodique) et recurent (contenant toutes les lettres une infinité de fois).

Preuve: Connaissant l'image du lacet infini, on connait les images de tous les lacets finis (non quadraticité), donc celles de lacets arretés a chacune des lettres, vue la recurrence). Separement, pour chacun de ces lacets, on detricote pour se ramener au lacet de base correspondant. En composant le detricotage et l'image du lacet fini, on deduit l'image du lacet de base correspondant. Soit t' une tresse qui detricote X1...XnA en a. On obtient t(a) = t'(Y1 ...YmA) comme image du lacet image par le detricotage puisque t t' = . Resultat on connait l'image d'une base du groupe libre. Ça, ça determine la tresse. Cet argument est completement faut. On prend le groupe des tresses pour un groupe commutatif.

J'ai le sentiment qu'il faut etre assez soigneux. Commencer par quelquechose de simple, genre  que si un est le shifté d'un autre, alors pas de souci.

Lemme 1 : Seule l'identité envoie un lacet quadratique sur lui meme.
Lemme 2 : Soit t une tresse qui envoie un lacet X sur un autre Y. Soit t* une autre. t* t-1 envoie  Y sur lui meme. C'est l'identité en vertue du lemme prçédent.

Donc il suffit de prouver le lemme 1.



On a utilisé le lemme: Si on connait l'image d'un lacet infini (non quadratique), on connait l'image de chacun des lacets tronqués finis qui le compose. Dont je ne vois pas la preuve directe. Mais les indices suivent:

On part du lacet X, non quadratique et recurent. L'application de la tresse t donne un lacet Y. Les deux lacets coincident a partir d'un certain rang (a shift pres), c'est a dire qu'il existe des entiers m et n tels que,  (ym, ..., ym+k, ...) = (xn, ..., xn+k, ...) puisque la tresse ne change le lacet que sur au plus sa longueur. Il existe donc deux tresses (uniques, du fait de la non quadraticité si elles sont obtenues par l'algorithme de detricotage. Bon elles pourraient etre unique si on dit qu'on prend la premiere dans l'algorithme, mais la on sait qu'il n'y en aura pas d'autres donnees par l'algorithme), tx et ty telles que, tx(x) = ty (y) = (xn, ..., xn+k, ...). On en deduit que y = ty-1 ° tx (x)

Soit alors t* une autre tresse telle que y = t* (x). Bon on peut se restreindre au cas ou l'un est suffixe de l'autre. Pour l'instant j'ai du mal a voir le role de la permutation.

Pour que tout ca soit clair, je crois qu'il faut specifier ce qu'on entend par image d'un lacet infini. L'action est a priori sur les lacets finis, et il y a un passage a la limite, qui peut induire un decalage si il y a une periodicité. Mais une fois les choses clarifiées, il me semble que dans la situation ci dessus (non quadratique), l'image des lacets finis (du lacet "court") doit etre le  lacet tronqué fini correspondant dans l'image. A partir de la la recurence suffit pour assurer qu'on connait l'image des lavcets de base, meme s'il ne sont pas obtenus simultanement. On detricote sans assurer l'unicité, mais en garantissant ce qu'est l'image, lacet par lacet. Il reste a remettre tout ca dans l'ordre.