Pavages, arbres et labyrinthes aléatoires

15 octobre 2004  - Ecrit par  Wendelin Werner, Richard Kenyon Voir les commentaires

Nous donnons un aperçu de quelques développement récents
concernant l’étude à grande échelle de pavages aléatoires qui
se trouvent être très intimement liés aux arbres aléatoires ainsi
qu’aux labyrinthes aléatoires.

L’étude à grande échelle de systèmes formés d’une multitude de composantes microscopiques aléatoires constitue l’une des problématiques fondamentales de la physique statistique ainsi que du calcul des probabilités. Souvent, on souhaite évaluer une grandeur macroscopique qui décrit ce système (qui peut être une somme ou moyenne, comme la magnétisation globale, ou la pression). Ce calcul est d’autant plus complexe lorsque les composantes interagissent fortement entre elles.

Deux cas peuvent se produire lorsque la taille du système devient grande. Dans le premier, l’observable macroscopique devient déterministe. En d’autres termes, on tend à observer toujours une valeur donnée $x$ (avec une probabilité grande, on observe une valeur proche de $x$).

L’exemple le plus simple est celui de $n$ variables aléatoires $X_1, \ldots, X_n$ indépendantes qui prennent chacune les valeurs $1$ et $-1$ avec probabilité $1/2$ (en d’autres termes, on tire $n$ fois à pile ou face et $X_n$ vaut $-1$ ou $1$ suivant si le résultat du $n$-ième lancer est pile ou face). La moyenne $(X_1+ \cdots + X_n) / n$ des $n$ valeurs observées (qui est reliée à la proportion du nombre d’observations « face ») est en fait proche de zéro. C’est la loi des grands nombres. Plus généralement, dans des systèmes physiques, les grandeurs thermodynamiques comme par exemple la pression peuvent être vues comme une quantité (déterministe) mesurée à partir du mouvement désordonné (aléatoire) d’une multitude de particules (c’est la base de la physique statistique).

Il se peut aussi que la quantité observée à grande échelle soit elle-même aléatoire. Bien qu’elle soit aléatoire, on peut tout de même la décrire par l’intermédiaire de
sa distribution. Dans l’exemple ci-dessus, on sait que lorsque $n$ tend vers l’infini,
la loi de $(X_1+ \cdots + X_n) / \sqrt {n}$ tend vers une loi gaussienne. En d’autres termes, pour tout $a$<$b$ fixés, la probabilité pour que la quantité aléatoire $(X_1 + \cdots + X_n)/ \sqrt {n}$ tombe dans l’intervalle $(a,b)$ devient de plus en plus proche de $(2\pi)^{-1/2} \int_a^b e^{-x^2/2} dx$. C’est le théorème de la limite centrale [1]. On peut le généraliser en disant que la trajectoire d’une marche aléatoire très longue convenablement renormalisée ressemble à une courbe continue aléatoire, le mouvement brownien [2].

PNG - 14.2 ko
Figure 1. La trajectoire d’une longue marche aléatoire.

LE MOUVEMENT BROWNIEN PLAN

Supposons qu’un domaine ouvert plan $D$ contenant l’origine
$0$ soit donné (par exemple un carré),
et considérons une marche
aléatoire simple sur la
grille carrée de maille $\delta$ , issue de $0$ et
arrêtée au premier instant $N$ où il quitte $D$. En d’autre termes,
à chaque pas, la marche bouge de $\delta$ dans l’une des quatres
directions cardinales choisie au hasard. Elle part de l’origine et
s’arrête lorsqu’elle quitte $D$.
Lorsque $\delta \to 0$, la loi de la trajectoire de la
marche aléatoire converge vers celle d’une trajectoire
$\gamma$ continue aléatoire : Celle d’un mouvement brownien
plan issu de $0$ et arrêté au premier instant de
sortie de $D$.
Il a été observé par Paul Lévy que si $\Phi$ est une
transformation conforme (i.e. une bijection
qui préserve les angles) du domaine $D$ dans le domaine $D'$ telle
que $\Phi(0)=0$, alors $\Phi(\gamma)$ est la
trajectoire d’un mouvement brownien arrêté lorsqu’il
quitte $D'$ : C’est l’invariance
conforme du mouvement brownien plan.

$\qquad$

Mis à part le mouvement brownien et les objets
(comme les solutions d’équations
différentielles stochastiques) qui lui ressemblent,
on connait en fait très peu
d’exemples pour lesquels on est capable de décrire de mathématiquement
un comportement macroscopique aléatoire. En particulier,
la modélisation de systèmes où les composantes microscopiques
ne sont pas indépendantes (qui constitue la majorité des phénomènes
aléatoires autour de nous : on peut par exemple penser
à la forme d’un nuage) pose problème.

Récemment, dans un cadre assez particulier, les mathématiciens
ont commencé à être capables d’appréhender de tels
comportements aléatoires. Il s’agit de l’étude de
systèmes aléatoires bi-dimensionnels dits
critiques pour lesquels les
physiciens théoriciens avaient depuis une vingtaine
d’années prédit
un comportement macroscopique aléatoire particulièrement intéressant
(en particulier leur « invariance conforme »).
Il y a eu ces dernières années de nombreux travaux sur
ce sujet (l’étude de la percolation critique, les marches
aléatoires en dimension 2, etc.) mais nous ne nous focaliserons
dans cet article que sur un modèle particulier qui
entre dans ce cadre.
En fait, ce modèle peut être
formalisé de quatres manières équivalentes que
nous allons maintenant décrire.

PAVAGE PAR DOMINOS

Le modèle est élémentaire. On se donne
un carré $N\times N$ où $N$ est un nombre pair.
On dispose d’une boîte contenant $N^2 / 2$ dominos
de taille $2 \times 1$.
Alors, on choisit au hasard (uniformément parmi
toutes les solutions possibles, qui sont nombreuses si
$N$ est grand) un recouvrement du carré par ces dominos.
C’est un pavage aléatoire.
La figure 2
représente un pavage d’un carré
de côté 6, où l’on a également colorié le
carré à la manière d’un échiquier (cases grises et
cases blanches).

PNG - 18.9 ko
Figure 2. Un pavage d’un carré 6x6.

ARBRES

Il existe une bijection naturelle entre l’ensemble des pavages du
carré $N \times N$ et un certain ensemble d’« arbres » que nous allons
maintenant décrire.
Supposons que l’on indice les petits carrés (de l’échiquier) par
leurs coordonnées cartésiennes de sorte que le petit
carré en bas à gauche à pour coordonnées $(0,0)$ alors
que celui en haut à droite a pour coordonnées $(N-1,N-1)$.
On s’intéresse au graphe plan formé par tous les points
à coordonnées paires dans le carré, auquel on rajoute un point
« extérieur » au carré qui est relié à tous les points
d’abscisse ou d’ordonnée égale à $N-1$.
On dit qu’un sous-graphe de ce graphe est un arbre s’il n’a
qu’une composante connexe, mais pas de cycle. On peut le
représenter comme dans la figure 3
sous la forme d’une famille de petits arbres disjoints attachés
aux bords droit et supérieur du carré.
Cet ensemble d’arbres est en fait en bijection avec
l’ensemble des pavages :
Si un tel arbre est donné, on dispose des dominos le long des
chemins partant des points pairs en direction de l’extérieur.
On a ainsi disposé $N^2/4$ dominos (il y en a un par point
pair du carré). Puis, on complète le pavage de l’unique
façon possible avec les $N^2/4$ dominos « restants ».
En observant la figure, on observe un phénomène de dualité :
On aurait pu aussi étudier l’arbre « dual » qui y est dessiné
en gris (qui joint les points à coordonnées impairs au bords
inférieur et gauche). On aurait commencé par disposer les
$N^2/4$ dominos « restants » et complété le pavage avec les
dominos qui vont le long de l’arbre noir .

PNG - 51.8 ko
Figure 3. Le pavage et les arbres associés.

LABYRINTHES

Une troisième manière de coder le pavage se fait par l’intermédiaire
du labyrinthe qui passe « entre » l’arbre noir et son dual gris.
Plus précisément,
on peut tracer le contour de l’arbre noir
(qui est aussi le contour de l’arbre gris)
c’est à dire l’ensemble des points à égale distance
des graphes noirs et gris.
C’est un chemin qui part du coin supérieur
gauche du carré pour finir au coin
inférieur droit.
Il est à noter que ce chemin passe par
tous les points constituant les coins des
petits carrés de l’échiquier
et qu’il n’a pas de point
double.
Inversement, si un tel chemin est donné, il est facile
de lui associer un arbre dont il est le contour :
Il y a bien une bijection entre l’ensemble de
ces chemins couvrants et l’ensemble des arbres
(et donc aussi l’ensemble des dominos).

PNG - 58.5 ko
Figure 4. Le pavage 6x6, les arbres et le labyrinthe associés.
PNG - 90.6 ko
Figure 5. Un pavage 16x16, les arbres et le labyrinthe associés.

MARCHES A BOUCLES EFFACÉES

Comment choisir au hasard et uniformément un pavage aléatoire
d’un carré ? Le nombre de pavages d’un carré
$N \times N$ croît exponentiellement avec $N^2$ de sorte qu’il
est difficile d’énumérer tous les pavages et d’en choisir
un au hasard.
Il existe plusieurs algorithmes beaucoup plus rapides qui
permettent de construire un tel pavage aléatoire. Le plus
performant est dû à David Wilson et démontre un lien
étonnant entre les arbres aléatoires et les
marches aléatoires à boucles effacées.

Définissons maintenant ces marches à boucles effacées :
Supposons qu’un marcheur parte d’un point $a$ du carré. On se donne
aussi un ensemble $B$ de points du carré.
A chaque pas, le marcheur choisit au hasard l’un de ses voisins
(s’il est sur le bord du carré, il peut y avoir moins
de quatre voisins) et s’y déplace.
Lorsqu’il atteint $B$ (soit $b$ le
point où il atteint $B$), il s’arrête. A partir de la trajectoire
du marcheur de $a$ au point $b \in B$, on construit une trajectoire
sans points doubles de la manière suivante : On efface
de manière chronologique les boucles effectuées par le marcheur
au fur et à mesure qu’elles apparaissent. La courbe aléatoire
de $a$ à $B$ ainsi obtenue s’appelle la marche
aléatoire à boucles effacées de $a$ à $B$.

Décrivons maintenant
l’algorithme de Wilson qui
montre en particulier que les branches
d’un arbre aléatoire uniforme sont en fait distribuées comme
des marches à boucles effacées.
On construit l’arbre de manière récursive.
On se donne un ordre quelconque $(x_1, \ldots, x_n)$ des
points dans le carré, et on note $L_0$ la réunion des bords
supérieur et droit du carré.
On définit alors une marche aléatoire à boucles effacées
$\gamma_1$ (dans le carré) de $x_1$ à $L_0$.
On pose $L_1=\gamma_1 \cup L_0$.
Puis, on définit une marche aléatoire $\gamma_2$
à boucles effacées de $x_2$
à $L_1$ (si $x_2$ est déjà sur $L_1$, alors $\gamma_2$ est
de longueur nulle). Par récurrence, pour tout $j$,
on définit une marche aléatoire à
boucles effacées $\gamma_j$ de $x_j$ à $L_{j-1}$, et on
pose $L_j= L_{j-1} \cup \gamma_j$.
Par définition, $L_n$ est un arbre, qui passe par tous les
points $x_1, \ldots, x_n$. Wilson a démontré que sa loi est
en fait celle d’un arbre aléatoire uniforme.
Les figures ci-dessous illustrent la construction dans le cas
du carré lorsque $L_0$ est la réunion du bord droit et du
bord supérieur.

PNG - 9.9 ko
Figure 6 . (a)
PNG - 10.8 ko
Figure 8. (c)
PNG - 6.9 ko
Figure 10. (e)
PNG - 9.7 ko
Figure 7. (b)
PNG - 10.8 ko
Figure 9. (d)
PNG - 8 ko
Figure 11. (f)

LE NOMBRE DE POINTS

On se pose la question suivante :
Considérons que $N$ est très grand. Choisissons le point $A$
au centre du carré (par exemple). Sur l’arbre aléatoire uniforme,
il existe un unique chemin (sans point double) reliant
$A$ au bord du carré (c’est à dire à la partie $L_0$
supérieure/droite du bord du carré).
L’algorithme de Wilson nous dit
que cette courbe est distribuée comme une marche aléatoire à
boucles effacées dans le carré de $A$ à $L_0$.
On veut conna^i tre l’ordre de grandeur de la longueur de
cette courbe. On sait d’après le théorème central
limite qu’avant l’effacement des boucles, l’ordre de grandeur du nombre
de pas de la marche aléatoire est $N^2$. Combien (typiquement)
en restera-t-il après ?
En exploitant le lien avec les pavages par dominos et par des
considérations assez compliquées, il est possible de montrer
que la moyenne de la longueur de cette marche à boucles effacées
est de l’ordre de $N^{5/4}$, ce qui confirme des prédictions
effectuées par les physiciens théoriciens (dans ce cas précis,
Majumdar ; des exposants étroitement reliés ont été prédits
par Duplantier).

STATISTIQUES LOCALES

Dans une configuration aléatoire de dimères, on peut se poser la
question de connaître la probabilité de trouver un certain motif
en un point donné. Par exemple, quelle est la probabilité de trouver
un domino couvrant à la fois la case $(x,y)$ et la case
$(x+1,y)$ ? Cette probabilité vaut $1/4$, car le domino
qui couvre la case $(x,y)$ a des chances égales de couvrir
les quatre cases adjacentes. En revanche la probabilité
de trouver un motif composé de plusieurs dominos différents
peut avoir une expression plus compliquée.
Par exemple la probabilité de trouver, dans une configuration aléatoire,
un domino couvrant
$(x,y)$ et $(x+1,y)$ et en même temps un domino
couvrant $(x,y+1)$ et $(x,y+2)$ (un motif en ’L’) vaut $1/4\pi$.
Dans la figure 12
on voit une configuration aléatoire
où les motifs de ce type ont été coloriés. Ces motifs
couvrent en moyenne une fraction $1/\pi$ de l’aire.

PNG - 66.3 ko
Figure 12. Un pavage et ses motifs en forme de L.

LA LIMITE CONTINUE ?

Les deux résultats exposés ci-dessus (le nombre de points et
les statistiques locales) se démontrent en utilisant comme point de
départ le fait qu’il est possible d’exprimer le nombre de
pavages d’un domaine via des déterminants, dont on peut
ensuite évaluer le comportement asymptotique. Ces calculs
donnent des informations précises concernant le
comportement en moyenne
de certaines quantités (le nombre moyen de points sur une
marche à boucles effacées, le nombre moyen de
configurations d’une forme donnée).

On peut essayer de manière complémentaire de comprendre
l’objet aléatoire qui serait la limite d’échelle (donc
continue) des labyrinthes aléatoires et des marches
à boucles effacées lorsque l’on fait tendre la maille
du réseau vers $0$.

L’algorithme de Wilson montre que l’étude asymptotique de
la loi des pavages aléatoires (ou des labyrinthes/arbres aléatoires)
lorsque $N \to \infty$ est très étroitement relié
à l’étude du comportement des très longues marches à
boucles effacées.
Il serait naturel
de penser que la limite des marches aléatoires à boucles
effacées devrait être une courbe brownienne à boucles
effacées. Cependant, les trajectoires browniennes
ont une géométrie extrêmement compliquée (il y a par exemple
des points de multiplicité infinie) de sorte qu’il n’est
pas possible de simplement effacer les boucles dans l’ordre
chronologiques sur une trajectoire
brownienne puisqu’il n’y a pas de « première » boucle à
effacer (sur tout intervalle de temps, le mouvement brownien
fait déjà une infinité de boucles). Il ne semble
donc pas possible de définir la limite des marches à boucles
effacées en partant d’un mouvement brownien plan.
Il faut trouver une autre méthode pour décrire cet
objet (et montrer la convergence du discret au continu).

LA LIMITE CONTINUE !

En fait, il est possible de construire et de décrire les objets
continus qui sont la limite du labyrinthe uniforme et de
la marche aléatoire à boucles effacées lorsque la maille
du réseau tend vers $0$.
Ces objets sont construits en combinant des outils d’analyse
complexe (l’équation de Loewner) et des idées probabilistes.
Oded Schramm a introduit en 1999 cette classe
de processus, et il a été prouvé en 2002 qu’effectivement
ils sont la limite d’échelle de ces deux modèles.
Comme on peut s’y attendre, la limite des marches à
boucles effacées est une courbe aléatoire de dimension
de Hausdorff $5/4$ (mais c’est difficile à prouver).
Elle s’appelle l’évolution de Schramm-Loewner (SLE) de paramètre
2. On peut l’interpréter comme étant un
mouvement brownien à boucles effacées (malgré la
difficulté
expliquée plus haut) : En effet, en lui rajoutant
des « boucles browniennes », on peut reconstruire un
mouvement brownien plan.

La courbe de Peano aléatoire converge quant à elle vers le
SLE de paramètre 8.
Puisqu’il est la limite d’échelle
des labyrinthes aléatoires,
on peut heuristiquement décrire ce processus comme étant
une courbe de Peano
aléatoire choisie de manière uniforme parmi toutes les courbes
de Peano. Il se trouve que cette mesure se concentre en
fait sur des courbes particulières : La frontière du domaine
recouvert après un certain temps a toujours
une dimension de Hausdorff égale à $5/4$.

PNG - 20 ko
Figure 12. Le début d’un grand labyrinthe aléatoire.

LE PROCESSUS DE SCHRAMM
On cherche une courbe aléatoire
$(\gamma_t, t \ge 0)$ infinie issue de $0$
dans le demi-plan supérieur $H$.
A chaque instant $t$, on associe à la courbe la transformation conforme
$f_t$ de $H \setminus \gamma [0,t]$ dans $H$
telle que $f_t (\gamma_t) = 0$ et $f_t (z) \sim z$ lorsque $z \to \infty$.
On veut qu’étant donné $\gamma [0,t]$,
la loi du futur $f_t (\gamma [t, \infty))$ soit distribué
comme une copie indépendante de $\gamma$.
En outre, on impose une condition de symétrie : La loi de $\gamma$ est
symétrique par rapport à l’axe imaginaire.
Alors, la théorie développée par Charles Loewner dans les années
1920 pour étudier les propriétés des fonctions univalentes, peut être
utilisée pour montrer que $f_t$ (modulo un
changement de temps approprié) vérifie
l’équation
$d f_t(z) = \sqrt {\kappa} dB_t + 2 dt/ f_t (z)$
où $B$ est un mouvement brownien unidimensionnel.
Cette équation s’avère charactériser $\gamma$, et définit le
SLE de paramètre $\kappa$ qui va de $0$ à l’infini dans $H$.
Par transformation conforme, ceci permet de définir les SLE joignant
deux points du bord d’un domaine plan simplement connexe (comme par
exemple
les deux coins opposés d’un carré) : On considère la courbe
aléatoire $\phi (\gamma)$ où $\phi$ est une transformation
conforme de $H$ dans $D$ qui envoie $0$ et l’infini sur deux
points donnés du bord de $D$.

Il se trouve qu’en fait, le paramètre $\kappa$ a une grande influence
sur les propriétés de la courbe $\gamma$ ainsi définie.
Il a été récemment démontré (mis à part
les cas $\kappa=2$ et $\kappa=8$ détaillés dans cet
article) que le SLE de paramètre $6$ correspond
à la limite d’échelle des interfaces d’un modèle de
percolation critique (c’est un travail de Stanislav Smirnov).
La valeur importante $\kappa=8/3$ correspond
à la frontière extérieure de trajectoires browniennes
planes et d’amas de percolation critique, et devrait en outre
correspondre à la limite des marches aléatoires
auto-évitante (ce serait la loi « uniforme » sur les
courbes simples).
Il est en fait conjecturé que chaque valeur de
$\kappa$ (au moins dans l’intervalle $[2,8]$) correspond à la limite d’échelle
de modèles discrets issus de la physique statistique.
Par exemple $\kappa=16/3$ devrait être relié au modèle
d’Ising.

INVARIANCE CONFORME

Afin de simplifier l’exposé, nous nous sommes focalisés
sur le cas du pavage d’un carré. En fait, on aurait pu choisir
une forme quelconque, c’est à dire un domaine
$D$ simplement connexe (disons borné) du plan.
On se donne $a$ et $b$ deux points distincts du bord
de $D$ (qui jouent le rôle des
coins du carré précédent).
Alors, pour chaque valeur de $\delta$ (petite), on choisit une
approximation (bien choisie) $D_\delta$ de $D \cap \delta Z^2$,
et deux points $a_\delta$ et $b_\delta$ approximant $a$
et $b$ dans ce graphe.
On considère alors un labyrinthe $\gamma_\delta$
de $a_\delta$
à $b_\delta$ (i.e. un pavage, ou un arbre)
aléatoire dans $D_\delta$.

Il s’avère (et c’est en fait fondamental pour montrer la convergence
dans le cas du carré) que la loi de $\gamma_\delta$ converge
lorsque $\delta \to 0$ vers celle d’une courbe de Peano aléatoire
(continue) de $a$ à $b$ dans $D$.
Cette courbe a la même loi que l’image
de la courbe de Peano aléatoire
dans le carré
par une application conforme $\Phi$ du carré
dans $D$ qui envoie les coins (inférieur gauche et
supérieur droit) du carré sur $a$ et $b$.
L’objet limite est invariant conforme. C’est ce qui
permet de le définir (dans l’encadré ci-dessus)
d’abord dans le demi-plan supérieur et ensuite
dans tout domaine $D$ en
prenant son image par transformation conforme.

Ces problèmes
ont aussi un rapport avec
d’autres domaines des mathématiques. On peut par
exemple montrer que le SLE de paramètre $\kappa=2$ est relié
à certaines représentations de plus haut poids
de l’algèbre
de Lie des
champs de vecteurs sur le cercle. Comme les
physiciens théoriciens l’avaient prédit, ces
modèles de prime abord de nature élémentaires
sont en fait profonds et
relient des domaines mathématiques
à priori disjoints (analyse complexe,
combinatoire, probabilités, représentations).

Références

R. Kenyon Local statistics of lattice dimers
Ann. Inst. Henri Poincaré 33 591-618, 1997

R. Kenyon
The asymptotic determinant of the discrete Laplacian
Acta Math. 185 239-286, 2000

G.F. Lawler, O. Schramm, W. Werner
Conformal invariance of planar loop-erased random walks
and uniform spanning trees

Ann. Prob. vol. 32, no1B, pp. 939-995, 2004

O. Schramm
Scaling limits of loop-erased random walks and uniform spanning
trees

Israel J. Math 118 221-288 ,2000

D.B. Wilson
Generating random spanning trees more
quickly than the cover time

Proc. 28th ACM 296-303, 1996

Post-scriptum :

Quelques autres articles sur les pavages :

Ornements et cristaux, pavages et groupes, I, II et III

Pavages aléatoires par touillage de dominos

Notes

[1Ce théorème est expliqué dans cet article

Partager cet article

Pour citer cet article :

Wendelin Werner, Richard Kenyon — «Pavages, arbres et labyrinthes aléatoires» — Images des Mathématiques, CNRS, 2004

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