Groupes en marche au hasard

Piste bleue 17 août 2014  - Ecrit par  Pierre Pansu Voir les commentaires (2)

C’était le 19 mars 2014 (en pleine Semaine des mathématiques, saturée d’animations). L’IHP recevait une centaine de collégiens et lycéens, dans le cadre du trimestre Marches aléatoires et géométrie asymptotique des groupes. L’initiative en revient à deux des organisatrices du trimestre, Anna Erschler et Indira Chatterji.
Au programme de l’après-midi, deux conférences, par Etienne Ghys et Nicolas Curien, précédées d’un jeu-concours.

Le jeu

A l’entrée, chaque participant s’est vu remettre un hexagone dont les deux faces sont blanche et grise, et les arêtes multicolores, un cube aux faces multicolores et le sujet que

voilà.

Première partie : Range tes jouets !

Énigme 1. Vous avez en main un hexagone en carton dont les côtés sont tous différents. Posez-le sur l’hexagone ci-dessous.
JPEG - 20.9 ko

A. Combien y a-t-il de façons différentes de poser le carton sur la feuille ?

B. Et si on compte seulement les positions pour lesquelles la face blanche du carton est sur le dessous ?

Énigme 2. Vous avez en main un cube dont toutes les faces sont différentes. Combien y a-t-il de façons différentes de poser ce cube sur le carré ci-dessous ?
JPEG - 13.6 ko

Seconde partie : Je travaille avec qui ?

Alice a son bureau dans un couloir droit, avec d’autres bureaux numérotés de gauche à droite en partant de 0. Le bureau d’Alice est au numéro 1, au 0 c’est le bureau de Bob, au 2 celui de Carine, au 3 celui de Dave, au 4 c’est Elise et tout au fond du couloir, au 37 c’est le secrétariat.
Alice hésite à partir à droite ou à gauche. Afin de décider, elle lance une pièce de monnaie : si c’est pile (probabilité 1/2) elle ira à droite d’un numéro (donc fait $+1$). Si c’est face (probabilité 1/2) elle ira à gauche d’un numéro (donc fait $-1$). Elle relance sa pièce de monnaie après s’être déplacée d’un numéro, et recommence.

1. Quelle est la probabilité qu’elle aille chez Bob avant d’aller chez Carine ?

2. Si Carine n’est pas dans son bureau, quelle est la probabilité qu’Alice arrive dans le bureau de Dave qui est au 3, avant de passer dans le bureau de Bob ?

3. Si ni Carine ni Dave ne sont dans leur bureau, quelle est la probabilité qu’Alice arrive dans le bureau d’Elise qui est au 4, avant de passer dans le bureau de Bob ?

4. Quelle est la probabilité qu’elle arrive au secrétariat, qui se trouve au 37 de ce même couloir, avant de passer par le bureau de Bob ?

Au travail ! Pour vous encourager, sachez que la plupart des participants ont résolu correctement la première partie (Range tes jouets !), et qu’un élève de 3ème a suffisamment bien avancé dans la seconde (Je travaille avec qui ?) pour être primé. Néanmoins, c’est piste rouge. Si vous souhaitez connaître les réponses, cliquez

ici, pour la première partie,

Range tes jouets !

1.A. 12, car une fois qu’on a choisi la face qui est contre la feuille (2 choix) et la position de l’arête jaune (6 choix indépendants du premier), c’est fini.

1.B. Moitié moins, soit 6.

2. 24, car une fois qu’on a choisi la face qui est contre la feuille (6 choix), on peut encore tourner le cube dans 4 directions.

et

là, pour la seconde.

Avec qui je travaille ?

1. 1/2. Par hypothèse, il y a autant de chance qu’Alice frappe à la porte de Bob qu’à celle de Carine.

2. 1/3. J’appelle $x$ la probabilité d’atteindre la porte 3 sans être passé par la porte 0 sachant qu’on part de la porte 1. J’appelle $y$ la probabilité d’atteindre la porte 3 sans être passé par la porte 0 sachant qu’on part de la porte 2. Par symétrie (échanger 0 et 3, 1 et 2), $y=1-x$. D’autre part, pour atteindre la porte 3 sans être passé par la porte 0, il faut, au premier mouvement, arriver à la porte 2 (qui arrive avec probabilité 1/2). Ce qui se passe ensuite est indépendant, donc $x=\frac{1}{2}y$. Les deux équations combinées donnent $x=1/3$.

3. 1/4. J’appelle $x$ la probabilité d’atteindre la porte 4 sans être passé par la porte 0 sachant qu’on part de la porte 1. J’appelle $y$ la probabilité d’atteindre la porte 4 sans être passé par la porte 0 sachant qu’on part de la porte 3. Par symétrie (échanger 0 et 4, 1 et 3), $y=1-x$. D’autre part, pour atteindre la porte 4 sans être passé par la porte 0, il faut d’abord atteindre la porte 3 sans être passé par la porte 0 (ce qui arrive avec probabilité 1/3). Ce qui se passe ensuite est indépendant, donc $x=\frac{1}{3}y$. Les deux équations combinées donnent $x=1/4$.

4. 1/37. Là, on a besoin d’un raisonnement par récurrence. On va traiter le cas général, la porte visée s’appelle $n>1$. J’appelle $x_n$ la probabilité d’atteindre la porte $n$ sans être passé par la porte 0 sachant qu’on part de la porte 1. Montrons par récurrence sur $n$ que $x_n=\frac{1}{n}$. On a déjà montré que $x_2=\frac{1}{2}$. Supposons donc montré que $x_{n-1}=\frac{1}{n-1}$. J’appelle $y_n$ la probabilité d’atteindre la porte $n$ sans être passé par la porte 0 sachant qu’on part de la porte $n-1$. Par symétrie (échanger 0 et $n$, 1 et $n-1$), $y_n=1-x_n$. D’autre part, pour atteindre la porte $n$ sans être passé par la porte 0, il faut d’abord atteindre la porte $n-1$ sans être passé par la porte 0 (ce qui, d’après l’hypothèse de récurrence, arrive avec probabilité $\frac{1}{n-1}$). Ce qui se passe ensuite est indépendant, donc $x_n=\frac{1}{n-1}y_n$. Les deux équations combinées donnent $x_n=1/n$.

Et encore là pour en savoir davantage.

Nicolas Curien propose une solution sans récurrence, je vous la livre. L’idée est, au lieu de toujours partir de la porte 1, de se demander ce qui se passerait si on partait d’une autre porte, de numéro $i$ compris entre 0 et 37. Nicolas appelle $p_i$ la probabilité d’atteindre la porte 37 sans être passé par la porte 0 sachant qu’on part de la porte $i$. Par construction, $p_0=0$ et $p_{37}=1$.
Partant de $i$, $1\le i\le 36$, de deux choses l’une, on passe en $i-1$ ou en $i+1$. A partir de là, ce qui se passe est indépendant du passé, et il y a une probabilité $p_{i-1}$ (resp. $p_{i+1}$) d’atteindre la porte 37 sans être passé par la porte 0. Autrement dit, $p_i= \frac{1}{2}p_{i-1}+ \frac{1}{2}p_{i+1}$. Si on représente graphiquement les points de coordonnées $(i,p_i)$, cette formule signifie que $(i,p_i)$ appartient au segment de droite d’extrémités $(i-1,p_{i-1})$ et $(i+1,p_{i+1})$. De proche en proche, on déduit que les points $(i,p_i)$ sont alignés, ils appartiennent tous au segment d’extrémités $(0,p_0)=(0,0)$ et $(37,p_{37})=(37,1)$. Cela donne $p_1=\frac{1}{37}$.

Voici comment le jeu est relié aux thèmes du trimestre Marches aléatoires et géométrie asymptotique des groupes. La première partie visait à se familiariser avec les déplacements de l’espace qui préservent une figure, un hexagone plan dans la partie A et un cube dans la partie B. Dans les deux cas, ces opérations forment ce que l’on appelle un groupe [1]. Si on demande que la face blanche de l’hexagone reste sur la feuille, on obtient un autre groupe formé de 6 rotations autour du même axe. Dans l’exposé d’Etienne Ghys, il y a aussi un groupe, composé des permutations de l’ensemble des cartes à jouer.

La seconde partie portait sur une promenade au hasard sur les entiers qui apparaît dans l’exposé de Nicolas Curien. On voit que la probabilité de s’en aller loin, jusqu’au secrétariat, sans passer par la porte 0 est petite. Cela sera confirmé plus loin : la probabilité de ne jamais revenir à la porte 0 est nulle.

JPEG - 410.8 ko
Dans l’amphi Hermite

Mélanges de cartes et mathématiques

Étienne Ghys nous a fait 4 tours de prestidigitation avec un jeu de 32 cartes. Vous connaissiez Ghys en magicien des mathématiques ; il faut reconnaître que sa première prestation de prestidigitateur a été très réussie. Son premier tour est tiré du livre de P. Diaconis et R. Graham, Magical Mathematics. Il marche à tous les coups, à condition que les assistants respectent scrupuleusement les consignes.

Ghys tend à un élève un paquet de 32 cartes et lui demande de le couper, puis de le passer à son voisin, qui coupe, etc.., jusqu’à ce que 5 élèves aient coupé. Le 5ème élève prend la carte du dessus du paquet, puis le passe à son voisin, qui prend la carte du dessus du paquet, jusqu’à ce que 5 cartes aient été retirées. Etienne demande à chacun des élèves la couleur (rouge ou noir) de la carte qu’il a en main. Après un court boniment illustré à l’aide du vidéoprojecteur, Etienne fait apparaître à l’écran une carte. C’est la 5ème carte tirée ! Stupéfaction de la salle.

Voici le secret. Le paquet était rangé initialement d’une façon très astucieuse. Cet ordre n’est pas perturbé par les coupes successives. Si, la coupe casse l’ordre des cartes, mais elle conserve l’ordre circulaire.

JPEG - 31.5 ko
Couper conserve l’ordre circulaire

Je m’explique. Si je pars d’un paquet de 5 cartes, 1,2,3,4,5 dans cet ordre, et que je coupe entre 3 et 4, le paquet devient 4,5,1,2,3. On constate que c’est toujours le 2 qui suit le 1, le 3 qui suit le 2, le 4 qui suit le 3 (à condition de revenir au-dessus quand on a épuisé le paquet), le 5 qui suit le 4 et le 1 qui suit le 5. En particulier, je peux parler de mains de trois cartes consécutives : celle qui se termine par la carte 2, c’est 5,1,2. Couper le paquet ne change pas cette notion. Considérons maintenant, dans un paquet de 32 cartes, les mains de 5 cartes consécutives. Il y en a 32. A chaque main est associé une suite de 5 couleurs, $r$ (rouge) ou $n$ (noir). Par exemple, à la main de cartes $7\heartsuit,D\clubsuit,R\clubsuit,8\diamondsuit,A\spadesuit$ est associée la suite $(r,n,n,r,n)$. Remarquer que le nombre total de suites de 5 lettres prises parmi $r$ et $n$ est aussi égal à 32.

Question : peut-on ranger les 32 cartes de telle sorte que les 32 suites de couleurs rouge/noir possibles apparaissent chacune une et une seule fois ?

La réponse est oui. Les solutions s’appellent des suites de de Bruijn. Et nos lycéens (et collégiens) de se mettre à gamberger ! J’ai eu un peu de mal, mais j’ai fini par trouver une

solution.

Il suffit d’indiquer une suite de 32 lettres $r$ ou $n$. Ensuite, n’importe quel rangement des 32 cartes qui respecte l’ordre des couleurs convient. Voici ma solution :
\[nnnnnrnnrnrrnnrrrrrnnnrrnrrrnrnr.\]
Voici un rangement des cartes qui fait l’affaire
\[7\clubsuit,8\clubsuit,9\clubsuit,10\clubsuit,V\clubsuit,7\heartsuit,D\clubsuit,R\clubsuit,8\diamondsuit,A\spadesuit,9\heartsuit,10\heartsuit,7\spadesuit,8\spadesuit,V\heartsuit,D\heartsuit,\]
\[R\heartsuit,A\heartsuit,7\diamondsuit,9\spadesuit,10\spadesuit,V\spadesuit,8\heartsuit,9\diamondsuit,D\spadesuit,10\diamondsuit,V\diamondsuit,D\diamondsuit,R\spadesuit,R\diamondsuit,A\clubsuit,A\diamondsuit.\]
La suite $(r,n,n,r,n)$ se retrouve à une unique position (couleurs 6 à 10), qui correspond bien à une unique main de 5 cartes $7\heartsuit,D\clubsuit,R\clubsuit,8\diamondsuit,A\spadesuit$.

On peut se poser la même question pour un jeu de 2 cartes ($nr$), 4 cartes ($nnrr$), 8 cartes ($nnnrnrrr$) et 16 cartes ($nnnnrrnrnnrnrrrr$).

JPEG - 14.5 ko
Rachel, Argine, Judith, Pallas

Un paquet de 32 cartes rangé de cette façon a la propriété suivante : si on me donne la suite des couleurs (rouge/noir) de 5 cartes consécutives, je sais dire où cette main est située dans le paquet et quelles sont les cartes qui la constituent. En particulier, je sais dire quelle est la 5ème carte de la main. Le protocole du tour permet de connaître la suite des couleurs (rouge/noir) de 5 cartes consécutives, et donc de deviner la 5ème carte de la main.

Encore faut il savoir remonter d’une suite comme $(r,n,n,r,n)$ à la main de cartes $7\heartsuit,D\clubsuit,R\clubsuit,8\diamondsuit,A\spadesuit$. C’est là que l’habileté du prestidigitateur entre en jeu. On peut essayer d’apprendre par cœur la correspondance entre suites et mains de cartes. C’est ce que ferait un prestidigitateur professionnel. Mais Ghys n’est pas un prestidigitateur ordinaire, il a le droit d’utiliser un ordinateur et un vidéoprojecteur. Un logiciel installé sur l’ordinateur remplace sa mémoire défaillante. Mais ce n’est pas tout. Personne n’a vu Ghys tapoter sur son ordinateur une suite de 5 couleurs. Et pourtant, il l’a fait.
L’air de rien, il a montré à l’écran des cartes à jouer et a disserté de façon érudite sur les prénoms des figures, d’abord les dames, Pallas et Judith, et voilà Rachel et Argine ; les rois, ce sont David et Charles, et ensuite César et Alexandre. Pour passer d’une image à la suivante, il cliquait sur une des deux cartes visibles à l’écran, la rouge ou la noire. Sans que le public s’en aperçoive, il saisissait ainsi une suite de couleurs rouge/noir. Ce n’est pas de la prestidigitation, ça ?

Promenades au hasard

Nicolas Curien fait remonter l’intérêt pour les marches au hasard à une question posée en juillet 1905 par Karl Pearson. Un homme fait un pas dans une direction tirée au hasard. Il tire à nouveau une direction au hasard, et il fait un pas dans cette direction. Puis il recommence, en tout il fait $n$ pas. A quelle distance de son point de départ se trouve-t-il typiquement ? Lorsqu’on répète l’expérience, l’histogramme des distances est proche d’une courbe en cloche. Cette réponse, c’est Lord Rayleigh qui la donne quelques jours plus tard, car il avait rencontré ce problème dans sa théorie du son dès 1880.

Marche au hasard dans le plan

Chaque promenade est différente, mais elles ont toutes le même aspect, vu de loin : elles sont très irrégulières ! Elles rappellent ce qu’on voit lorsqu’on observe l’agitation perpétuelle de particules dans l’eau, le pollen notamment. C’est pourquoi on utilise les promenades aléatoires pour décrire ce mouvement, appelé mouvement brownien, du nom du botaniste Robert Brown qui, en 1827, a compris que l’agitation n’a rien à voir avec un prétendu fluide vital. La théorie du mouvement brownien a été échafaudée par Bachelier, Einstein, Smoluchowski, Perrin, Langevin au début du XXème siècle. Le lien avec les promenades aléatoires a été proposé par Wiener (1923) et consolidé par Lévy (1933).

Il est plus simple de contraindre notre homme à ne se déplacer que dans quatre directions, vers l’avant, vers l’arrière, à droite, à gauche. Cela ne change pas l’allure des promenades, quand on les regarde longtemps et de loin. Pourtant, elles sont confinées sur un graphe en forme de grille. On s’intéresse plus généralement aux promenades aléatoires sur des graphes. Celle sur le graphe du web est au coeur de l’algorithme de calcul du pagerank imaginé par les créateurs de Google.

Marche au hasard le long d’une droite

Temps en abscisse, position en ordonnée

En 1921, Polya montre que la promenade aléatoire dans quatre directions ramène presque toujours notre homme à son point de départ. Pour terminer sa conférence, Curien nous explique la version unidimensionnelle de ce théorème : l’homme se déplace en ligne droite, en avant ou en arrière (c’est le mode de déplacement d’Alice dans le jeu ci-dessus). Autrement dit, il saute d’un nombre entier à un autre, en tirant au hasard le précédent ou le suivant, en partant de 0.
Le théorème énonce que notre homme reviendra avec probabilité 1 à l’origine. Curien en donne même une

démonstration au tableau (piste rouge).

Curien appelle $x$ la probabilité de repasser un jour par 0 sachant qu’on est parti de 0, et $y$ la probabilité de passer un jour par 0 sachant qu’on est parti de 1. Par symétrie, $y$ est aussi la probabilité de passer un jour par 0 sachant qu’on est parti de $-1$. Après le premier pas, on est en $-1$ ou en 1. Dans les deux cas, la probabilité de repasser par 0 est $y$, donc $x=\frac{1}{2}y+\frac{1}{2}y=y$.

Partons de 1. Avec probabilité $1/2$, on saute en $0$, c’est gagné. Sinon, et si on doit passer par 0, il faut bien repasser avant par 1. La probabilité que cela se produise est égale à $x$. Au premier retour en 1, il y a une probabilité $y$ de revenir un jour en 0. Donc $y= \frac{1}{2}+\frac{1}{2}xy$.

Comme $y=x$, l’équation $x=\frac{1}{2}+\frac{1}{2}x^2$ a pour unique solution $x=1$.

Un grand merci à Etienne Ghys et Nicolas Curien pour cette agréable promenade entre cartes et hasard.

La conférence de Ghys a été filmée, elle sera bientôt disponible sur le site de l’IHP.

Post-scriptum :

Merci à Aurélien Djament, Roger Mansuy, Lison, Depresseux pour leur travail de relecture.

Article édité par Pierre Pansu

Notes

[1Voir à ce sujet la présentation « Sur les groupes, ça marche » de l’ensemble du trimestre, et une conférence d’Etienne Ghys.

Partager cet article

Pour citer cet article :

Pierre Pansu — «Groupes en marche au hasard» — Images des Mathématiques, CNRS, 2014

Commentaire sur l'article

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.

Connexions’inscriremot de passe oublié ?

Suivre IDM