Pavages aléatoires par touillage de dominos
Piste bleue Le 17 février 2009 Voir les commentaires (5)Lire l'article en


La physique statistique s’intéresse à l’étude à grande échelle de systèmes formés d’un nombre immense de composantes microscopiques. Une question essentielle est de savoir comment cette multitude d’éléments s’organise en fonction des contraintes qui leur sont imposées : quelle est la place laissée au hasard ? Quel comportement observe-t-on à l’échelle macroscopique ? Expérimenter dans ce domaine nécessite de pouvoir générer des configurations typiques à l’aide d’algorithmes simulant les effets du hasard.
Paver avec des dominos
L’exemple que nous considérons ici est celui des pavages d’une région du plan avec des dominos de taille $2\times 1$.
Les règles du pavage sont les suivantes : les dominos doivent remplir toute la région et ils ne doivent pas se chevaucher.
Parmi toutes les façons de paver une énorme région, y a-t-il une tendance générale ?
Bien sûr, il n’est pas toujours possible de paver une région donnée. Une condition nécessaire est clairement que la région soit la réunion d’un nombre pair de carrés de côté 1.
Et il existe même des régions du plan satisfaisant cette condition qui ne sont pas pavables par des dominos.
Pavage aléatoire
Quand une région du plan est pavable avec des dominos, il existe en général un très grand nombre de façons possibles de les placer.
Pour connaître la manière typique dont s’organisent les dominos, il est souhaitable de pouvoir tirer au sort un pavage.
Mettons tous les pavages possibles dans un chapeau, mélangeons bien et tirons-en un sans regarder.
C’est ce que l’on appelle un tirage équiprobable : tous les pavages ont la même probabilité d’être choisis.
En pratique, une telle énumération de tous les pavages est irréalisable : le nombre de pavages possibles augmente extrêmement vite avec la taille de la région à paver.
Les mathématiciens ont donc mis au point des algorithmes qui permettent de réaliser une telle expérience sans recourir à un chapeau.
Le plus connu utilise le lien avec les « arbres couvrants » [2] et l’algorithme de David Wilson [3] pour générer ces objets.
Nous allons ici présenter une autre méthode, dite de « touillage de dominos » (domino shuffling), pour générer des pavages aléatoires.
Elle a été développée pour une forme très particulière de région, le diamant aztèque, mais peut être généralisée pour réaliser d’autres sortes de pavages.
L’algorithme du touillage de dominos
Voici les diamants aztèques d’ordre 1, 2, 3 et 6 :
- Diamants aztèques d’ordre 1, 2, 3 et 6
Il y a bien sûr deux façons de paver le diamant d’ordre 1 :
Pour le diamant d’ordre 2, il est encore possible de recourir au chapeau. On voit qu’il y a une chance sur 8 de tirer l’un des pavages suivants :
- Le diamant aztèque d’ordre 2
- Les 8 pavages possibles.
On pourrait aussi énumérer tous les pavages du diamant d’ordre 3, bien que cela commence à être difficile.
Mais pour le diamant d’ordre 4, ce n’est déjà plus raisonnable de construire à la main tous les pavages possibles : il en existe 1024 différents.
En général, on peut montrer qu’il y a exactement $2^{n(n+1)/2}$ manières de paver un diamant d’ordre $n$.
Pour le diamant d’ordre 100, il y a donc $2^{5050}$ pavages possibles, un nombre qui s’écrit avec plus de 1 500 chiffres !
On peut facilement passer du diamant aztèque d’ordre $n-1$ à celui d’ordre $n$ : Il suffit d’ajouter autour une couche supplémentaire.
C’est cette propriété géométrique qui permet de construire un pavage aléatoire d’un gros diamant, en construisant successivement des pavages des diamants plus petits : on commence par le diamant d’ordre 1 en tirant à pile ou face l’orientation des deux dominos (tous les deux horizontaux ou tous les deux verticaux). Puis on construit successivement des pavages des diamants d’ordre 2, 3, 4,... jusqu’à l’ordre souhaité. Le passage d’un pavage d’ordre $n-1$ à celui d’ordre $n$ s’effectue en déplaçant localement les dominos (d’où le nom de l’algorithme). Il arrive régulièrement qu’un choix d’orientation des dominos se présente : à chaque fois que c’est le cas, on tire à pile ou face pour décider. En procédant ainsi, on obtient à chaque étape un pavage choisi de manière équiprobable parmi tous les pavages de la même taille.
Les animations suivantes présentent les étapes successives de l’exécution de l’algorithme du touillage pour des diamants aztèques d’ordre 10 puis 100.
- Algorithme du touillage de dominos
- Étapes successives de l’algorithme pour la génération d’un pavage du diamant d’ordre 10. Chaque pavage est tiré de manière équiprobable parmi tous les pavages possibles.
- Le même algorithme, poussé jusqu’à un diamant d’ordre 100
Le phénomène du cercle arctique
Si l’on tire au hasard un des pavages possibles d’un diamant d’ordre assez grand, on verra, comme sur l’animation ci-dessus, apparaître avec une probabilité proche de 1 le fameux cercle arctique [4] : à l’extérieur du cercle inscrit dans le diamant les dominos sont tous « gelés » dans le même sens, alors qu’à l’intérieur le désordre règne.
Le phénomène du cercle arctique dans le pavage aléatoire du diamant aztèque présente un intérêt très particulier : dans ce modèle, les effets de bord se propagent à une grande distance de la frontière du domaine et sont donc visibles à l’échelle macroscopique. Ce n’est pas le cas pour le carré par exemple.
- Effets de bords
- À gauche : un pavage typique du diamant aztèque d’ordre 100, sur lequel on observe le phénomène du cercle arctique. À droite : un pavage typique du carré de côté 60.
Pavage aléatoire d’autres régions du plan : l’algorithme du touillage avec poids
Lors de l’application de l’algorithme du touillage, il est nécessaire de tirer à pile ou face pour passer d’un pavage du diamant d’ordre $n-1$ au pavage du diamant d’ordre $n$.
On utilise une pièce équilibrée pour décider entre les deux façons possibles d’orienter certains dominos car on ne souhaite pas privilégier un sens plutôt que l’autre.
Il existe une version [5] plus sophistiquée de l’algorithme qui permet de favoriser ou défavoriser certains placements des dominos.
On associe un poids à chaque position possible d’un domino : la position sera d’autant plus favorisée que le poids est important.
Les tirages au sort se font alors avec des pièces biaisées (qui favorisent ou défavorisent les piles).
En fait, il est même possible d’interdire de placer des dominos à certains endroits en leur attribuant des poids nuls [6].
C’est ce que l’on a fait pour obtenir un pavage aléatoire du carré de côté 60 présenté plus haut.
Celui-ci a été « inséré » dans un diamant aztèque, et on a interdit certains placements de dominos.
- Un carré inséré dans un diamant aztèque.
- On interdit que les dominos chevauchent le carré, en attribuant un poids nul aux positions spécifiées en rouge.
À l’extérieur du carré, les dominos se rangent obligatoirement tous de la même façon (horizontalement en bas et en haut et verticalement à droite et à gauche).
On obtient, à l’aide de l’algorithme du touillage, un pavage aléatoire équiprobable du carré.
Bien sûr, on peut faire la même chose pour paver un rectangle (dont la largeur ou la longueur est paire) ou une autre région de forme plus compliquée.
On peut même s’amuser en attribuant des poids en fonction de l’intensité de pixels d’une photographie. Voilà ce que cela donne :
- Pavage avec poids
- Pavage aléatoire d’un carré lorsque les orientations sont pondérées en fonction de l’intensité des pixels d’une photo.
Autres pavages aléatoires
Il est possible de réaliser des pavages avec d’autres formes que des dominos à partir de l’algorithme du touillage : par exemple paver un hexagone avec des losanges. L’idée est de remplacer le réseau carré, qui est en quelque sorte le « squelette » du diamant aztèque, par un autre réseau régulier : le réseau hexagonal (en haut à droite), le réseau carrés-octogones (en bas à gauche), ou le réseau composé de carrés, hexagones et octogones (en bas à droite).
Un pavage typique de l’hexagone à l’aide de losanges fait apparaître un phénomène semblable au cercle arctique dans le diamant aztèque.
- Pavage aléatoire de l’hexagone.
Les autres réseaux présentés ci-dessus donnent lieu à des pavages dans lesquels apparaissent simultanément des pavés de formes différentes (carrés, triangles, etc.). La figure suivante présente deux pavages aléatoires obtenus à partir de ces réseaux (avec détails des pavages à l’intérieur des disques).
On observe à nouveau sur ces pavages un phénomène de gel des bords, mais on ne sait pas encore identifier la forme de la partie gelée.
Notes
[1] J. C. Fournier. Tiling pictures of the plane with dominoes. Discrete Mathematics
165-166, (1997), 313—320
Graphs and Combinatorics
[2] R. Kenyon, J. Propp, D. Wilson. Trees and matchings. Electron. J. Combin. 7 (2000), Research Paper 25, 34 pp.
[3] J. Propp and D. Wilson.
How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph.
J. Algorithms 27 (1998), no. 2, 170—217.
[4] W. Jockusch, J. Propp et P. Shor. Random domino tilings and the arctic circle theorem (1998).
[5] J. Propp. Generalized domino-shuffling. Theoretical Computer Science 303 (2003), p. 267-301
[6] É. Janvresse, T. de la Rue, Y. Velenik. A note on domino shuffling. Electron. J. Combin. 13 (2006), no 1.
Partager cet article
Pour citer cet article :
Thierry de la Rue , Élise Janvresse — «Pavages aléatoires par touillage de dominos» — Images des Mathématiques, CNRS, 2009
Laisser un commentaire
Actualités des maths
-
6 février 2023Journées nationales de l’APMEP, appel à ateliers (9/4)
-
20 janvier 2023Le vote électronique - les défis du secret et de la transparence (Nancy, 26/1)
-
17 novembre 2022Du café aux mathématiques : conférence de Hugo Duminil-Copin (Nancy et streaming, 24/11)
-
16 septembre 2022Modélisation et simulation numérique d’instruments de musique (Nancy & streaming, 22/9)
-
11 mai 2022Printemps des cimetières
-
3 mai 2022Comment les mathématiques se sont historiquement installées dans l’analyse économique (streaming, 5/5)
Commentaire sur l'article
Pavages aléatoires par touillage de dominos
le 23 octobre 2009 à 22:58, par FrancoisGueg
Pavages aléatoires par touillage de dominos
le 26 octobre 2009 à 11:01, par Thierry de la Rue
Pavages aléatoires par touillage de dominos
le 9 novembre 2009 à 17:01, par FrancoisGueg
Pavages aléatoires par touillage de dominos
le 3 avril 2015 à 18:29, par myryllion
Pavages aléatoires par touillage de dominos
le 11 août 2020 à 09:19, par Dasson