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].
- 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.
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).
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 .
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).
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.
|
|
|
|
|
|
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).
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.
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).
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$.
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.
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. 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
Quelques autres articles sur les pavages :
