Un modèle d’agrégat aléatoire

Piste bleue Le 25 mars 2020  - Ecrit par  Nicolas Chenavier Voir les commentaires

La mosaïque

Prenons 20 points (noirs) dans un carré et notons $A$ l’un de ces points. Le lieu où l’on est plus proche de $A$ que de tous les autres points s’appelle la cellule de Voronoï de germe $A$. Celle-ci est coloriée en vert dans la figure ci-dessous. La cellule de Voronoï est un polygone ; et la famille de toutes ces cellules forme un découpage du carré qu’on appelle la mosaïque de Voronoï. Cet objet a un grand nombre d’applications dans divers domaines, notamment en télécommunications, en biologie et en astrophysique. Pour plus de détails sur la mosaïque de Voronoï, nous vous invitons à consulter « Une version de la conjecture de Kendall ».

L’agrégat

Dans cet article, nous allons construire un agrégat aléatoire sur notre mosaïque. Celui-ci est défini étape par étape. A l’étape 1, il consiste en une cellule, disons qu’il s’agit de la cellule verte : celle de germe $A$.

Pour construire notre agrégat à l’étape 2, nous procédons comme suit. Imaginons une puce qui part de la cellule de germe $A$. Cette puce saute de la cellule à une cellule voisine et elle a autant de chances de sauter sur chacune de ces cellules. En l’occurrence, la puce saute sur la cellule coloriée en gris dans le dessin ci-dessous (elle aurait très bien pu tomber sur une autre cellule voisine, avec le même pourcentage de chance). L’agrégat à l’étape 2 consiste en les deux cellules : celle de germe $A$ et celle sur laquelle la puce est tombée. Le dessin ci-dessous représente notre agrégat à l’étape 2 (il s’agit du même dessin que précédemment mais nous avons colorié cette fois-ci nos deux cellules en vert).

L’étape 3 est plus délicate. Pour construire notre agrégat, nous demandons à une autre puce de repartir à nouveau de la cellule de germe $A$. Cette puce a le même comportement que la précédente : elle se déplace au hasard d’une cellule à une cellule voisine (elle ne peut pas sautiller sur la cellule sur laquelle elle est). Si la puce tombe sur une cellule verte, alors elle continuera de se déplacer, et elle le fera tant qu’elle reste sur une cellule verte. Si elle tombe sur une cellule blanche, alors elle s’y écrase. Voici le mouvement de notre puce : Notre puce s’est tout de suite écrasée sur une cellule, à nouveau coloriée en gris. Notre agrégat à l’étape 3 consiste à rajouter aux deux cellules précédentes notre cellule grise qu’on colorie en vert, et est donc celui-ci : Remarquons que, à l’étape 3, notre agrégat est constitué de trois cellules et qu’aux étapes 1 et 2, il était constitué respectivement de 1 et 2 cellules. Cela n’est guère étonnant car, à chaque étape, on rajoute une cellule : celle sur laquelle la puce s’est écrasée.

A l’étape 4, le procédé est le même. Une autre puce part depuis la cellule de germe $A$ et saute d’une cellule à une cellule voisine, avec le même pourcentage de chance. Elle se déplace tant qu’elle reste sur une cellule verte. La première fois qu’elle saute sur une cellule qui n’est pas verte (cela finira toujours par arriver au bout d’un certain temps), elle s’y écrase, et cette cellule est ajoutée à l’agrégat. Voici le mouvement d’une puce (représenté à nouveau par des flèches) : La puce est d’abord allée sur une cellule verte, puis elle s’est écrasée. L’agrégat à l’étape 4 est alors le suivant :

Il en est ainsi à chaque étape. Voici par exemple, le mouvement d’une puce qui part à nouveau de la cellule de germe $A$ avec un agrégat de 12 cellules (les cellules vertes), et en gris la cellule sur laquelle elle s’est écrasée :
Notre agrégat à l’étape 13 est donc le suivant :
On peut imaginer que l’on peut procéder ainsi à chaque étape.

Insistons sur deux points importants.

  1. Les mouvements des puces sont aléatoires. Les puces auraient pu avoir des trajectoires différentes. Le dessin ci-dessus est ce qu’on appelle une réalisation. Si les mouvements des puces avaient été différents, l’agrégat aurait probablement été lui aussi différent ; et l’on aurait eu une autre réalisation. A l’étape $N$, on sait que l’agrégat (aléatoire) est constitué de $N$ cellules, mais on ne peut pas prévoir à l’avance quelle sera sa forme. C’est pour cette raison que l’on parle de modèle d’agrégat aléatoire.
  2. Si les puces ont les mêmes comportements (elles se déplacent d’une cellule à une cellule voisine et continuent leurs chemins jusqu’à ce qu’elles s’écrasent sur une cellule qui n’est pas verte), leurs mouvements sont, en revanche, et en un certain sens, indépendants. Plus précisément, la trajectoire qu’a prise la puce $N-1$ avant de s’écraser, et plus généralement les trajectoires de toutes les puces qui l’ont précédée, ne permettent pas de déterminer la trajectoire que prendra la puce $N$.

Nous avons construit un agrégat à l’étape 13 avec 30 cellules dans un carré. Voici une réalisation d’un agrégat à l’étape 4500 avec 6500 cellules (les contours des cellules de l’agrégat sont en rouge et les contours des cellules qui ne sont pas dans l’agrégat sont en noir) : On constate que l’agrégat ressemble à un disque. En fait, si l’on avait fait une autre réalisation, c’est-à-dire si on avait considéré autant de puces qui n’auraient pas eu nécessairement le même mouvement, on aurait également remarqué que l’agrégat ressemble à un disque. Ceci semble, au premier abord, très curieux car il ne faut pas perdre de vue que les agrégats sont aléatoires ; et pourtant il semble que lorsque l’on prend beaucoup de cellules dans le carré et un agrégat de grande taille, c’est-à-dire avec un grand nombre d’étapes, la forme de l’agrégat semble être déterministe : à chaque fois, l’agrégat ressemble à un disque.

Le modèle que nous venons d’introduire porte un nom : on l’appelle le modèle d’agrégation limitée par diffusion interne (IDLA en anglais). Cet objet a été introduit dans le contexte d’un réseau régulier pour modéliser divers systèmes tels que les dépôts de minéraux, le claquage électronique et l’électro-polissage. La construction se fait dans le même esprit que ce que nous avons décrit à la différence près que les cellules doivent être remplacées par des points dont les coordonnées sont des nombres entiers. L’IDLA est un cas particulier de modèle de croissance (voir l’article « Processus de croissance »
pour un autre modèle). Un grand nombre de mathématiciens se sont intéressés à la forme que prend l’agrégat au bout d’un grand nombre d’étapes. Citons, par exemple, Asselah, Bramson, Gaudillière, Griffeath, Lawler, Lucas. Dans le cas d’un réseau régulier, il a été démontré que la forme de l’agrégat, lorsque celui-ci est gros, ressemble à un disque.

Une conjecture

Revenons à notre agrégat aléatoire sur Voronoï. Nous pensons que, dans le même esprit que pour le réseau régulier, l’agrégat ressemble à un disque au bout d’un grand nombre d’étapes. Pour l’agrégat de Voronoï, l’état actuel de la recherche n’en est qu’au stade de conjecture.

Nous souhaitons donner un énoncé mathématique de notre conjecture, mais pour cela nous devons modifier un peu notre problème. Plutôt que de considérer une mosaïque de Voronoï observée dans un carré avec un nombre fini de cellules, on imagine qu’on a une mosaïque de Voronoï dans le plan tout entier avec un nombre infini de cellules. Les germes qui ont permis de construire la mosaïque de Voronoï ont été pris au hasard. La construction d’un tel modèle n’a rien d’évident : elle suppose qu’il est possible de prendre au hasard une infinité de points dans le plan - et l’infini pose souvent des problèmes ! Des mathématiciens ont cependant montré qu’il est possible de faire cela (le procédé repose sur la notion de processus ponctuel de Poisson standard, voir le paragraphe 2 de « processus ponctuel » pour plus de détails), et nous allons donc accepter le fait qu’on peut prendre une infinité de points au hasard dans le plan, pour construire notre mosaïque de Voronoï avec un nombre infini de cellules.

L’agrégat à l’étape 1 consiste en une seule cellule, disons celle qui contient l’origine, et est noté $A(1)$. L’agrégat à l’étape $N$, constitué de $N$ cellules, est noté $A(N)$. Pour décrire mathématiquement la conjecture que l’agrégat ressemble à un disque, nous désignons par $D(0,r)$ le disque dont le centre est l’origine et de rayon $r$. Il s’agit de l’ensemble des points du plan à une distance inférieure à $r$ de l’origine. Notre conjecture peut s’énoncer comme suit.

Conjecture : Avec cent pour cent de chances, lorsque $n$ est suffisamment grand, et en prenant $N$ comme l’entier le plus proche de $\pi n^2$,
  • tous les points du disque $D(0, n-\sqrt{n})$ appartiennent à l’agrégat $A(N)$ ;
  • tous les points de l’agrégat $A(N)$ appartiennent au disque $D(0, n+\sqrt{n})$.

Cette conjecture signifie que l’agrégat contient un disque de rayon $n-\sqrt{n}$ et est contenu dans un autre de rayon $n+\sqrt{n}$. Lorsque $n$ est grand, les nombres $n-\sqrt{n}$ et $n+\sqrt{n}$ sont du même ordre de grandeur. Il faut donc imaginer que, lorsque l’agrégat est de grande taille, il est compris entre deux disques qui sont sensiblement de la même taille et donc qu’il ressemble lui-même à un disque.

Deux collègues (David Coupier, Arnaud Rousselle) ainsi que l’auteur de cet article ont encadré un étudiant de master sur ce problème, et tentent toujours de prouver cette conjecture.

Post-scriptum :

Merci à Arnaud Rousselle, enseignant-chercheur à l’Université de Bourgogne, d’avoir fait une réalisation d’un agrégat aléatoire avec beaucoup de cellules (dernier dessin). Merci également à Shalom Eliahou et Bruno Martin pour leur relecture attentive.

L’auteur et la rédaction d’Images des Mathématiques remercient aussi le relecteur Alain Sebaoun pour sa relecture attentive et ses commentaires.

Article édité par Shalom Eliahou

Partager cet article

Pour citer cet article :

Nicolas Chenavier — «Un modèle d’agrégat aléatoire» — Images des Mathématiques, CNRS, 2020

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é ?