Fragmentation d’arbres aléatoires - Une interview de Jean Bertoin
Piste rouge Le 25 octobre 2016 Voir les commentaires
Cet article a été écrit en partenariat avec La Gazette des Mathématiciens

En 2015, Jean Bertoin a reçu le prix Thérèse Gautier de l’Académie des Sciences. À cette occasion, il nous explique ce que sont les processus de fragmentation, et le cheminement qui l’a conduit jusqu’à l’étude récente de la « destruction des arbres aléatoires récursifs ».
Cet article, en partenariat avec la Société Mathématique de France (SMF) et son journal la Gazette des mathématiciens, paraît en même temps que l’article de Jean Bertoin et Erich Baur : « Sur la destruction de grands arbres aléatoires récursifs » dans la Gazette.
— Le site de l’Académie des Sciences indique que tu as reçu le prix Thérèse Gautier, notamment, pour avoir « inventé la théorie des processus de fragmentation, qui étudie la manière dont un objet se fragmente de façon aléatoire au cours du temps ». De quoi s’agit-il ?
Les processus de fragmentation sont des modèles mathématiques qui décrivent l’évolution d’une masse qui va se scinder au cours du temps, de façon répétée, aléatoire, et avec des propriétés d’« auto-similarité ». On peut imaginer une masse qu’on va mettre dans un concasseur, et puis à des instants aléatoires la masse va se disloquer en plusieurs morceaux.
On formule des hypothèses qui ne sont peut-être pas très réalistes, mais qui permettent de développer une étude mathématique. L’hypothèse essentielle, qu’on appelle une « hypothèse de branchement », c’est que dès qu’on a plusieurs masses distinctes, leurs évolutions sont indépendantes. C’est-à-dire que la façon dont l’une des masses va continuer à se disloquer au cours du temps ne dépend pas de la façon dont les autres vont le faire. Ça c’est très important, ça permet de répéter le processus. On part de la description d’une dislocation, et on va supposer que par la suite ça va se répéter de façon indépendante, mais toujours avec les mêmes statistiques.

Un concasseur
Quand je disais que ça n’était pas très réaliste, si tu imagines un bloc de minerai dans un concasseur, il est évident que les blocs vont se cogner les uns contre les autres, et en fait il y a vraiment de la dépendance. Mais néanmoins, cette hypothèse d’indépendance est très utile mathématiquement, parce qu’elle permet de faire des calculs. Même si dans la pratique elle n’est pas forcément réalisée, elle est relativement raisonnable, et on espère que les résultats mathématiques que l’on peut établir sur le modèle ne vont pas être trop éloignés de ce qu’on peut observer dans la réalité.
— Quel genre de questions se pose-t-on sur ces objets ?
On est dans une situation où on sait décrire ce qui se passe de façon « infinitésimale », on sait décrire un pas du processus, et on va s’intéresser au « comportement asymptotique », c’est-à-dire à ce qui se passe après un très grand nombre de pas. Finalement on pourrait dire que la moitié des maths c’est ça, quand on regarde les systèmes dynamiques, ou les équations différentielles...
Pour en revenir à cette image de concassage de roches, ce modèle est utilisé dans l’industrie minière. Pour extraire du minerai, ils vont concasser de façon très importante des gros blocs de minerai, et puis au bout d’un certain temps ils vont passer ça sur une sorte de tamis pour retirer les toutes petites particules, le sable fin qu’ils vont pouvoir ensuite traiter ; tandis que les gros blocs, il faudra encore les concasser. Une des questions qu’on peut regarder, par exemple, c’est des questions d’optimisation de coût. Le concassage a un coût énergétique assez conséquent, et les gens peuvent utiliser des modèles de fragmentation pour essayer de comprendre, selon la façon dont un bloc se disloque lors d’un choc, ce qui va se passer à assez long terme, et pour avoir une idée de la répartition des masses des grains de sable quand le bloc est bien concassé : est-ce qu’on aura une distribution assez uniforme avec des morceaux qui ont tous à peu près la même taille, ou bien au contraire va-t-il y avoir des morceaux relativement gros et d’autres plus petits ? Voilà le genre de questions qu’on se pose.
PERCOLATION DANS LES GRAPHES COMPLETS
— Comment en es-tu arrivé à étudier la fragmentation dans les arbres ?

Le graphe complet à 11 sommets
Pour commencer, il y a des travaux très importants et bien connus de Erdős et Rényi dans les années 1950, qui portent sur la « percolation sur le graphe complet ». Un graphe est un objet mathématique constitué de sommets et d’arêtes, et on parle de graphe complet lorsqu’il y a toutes les arêtes possibles, tous les couples de sommets sont joints par une arête. La percolation consiste à retirer certaines arêtes, en fait chaque arête a une certaine probabilité fixée d’être retirée, indépendamment des autres arêtes. On obtient alors un graphe aléatoire, dont la géométrie dépend de cette probabilité fixée.

Un graphe tiré au hasard dans le modèle d’Erdös-Rényi. Les morceaux sont appelés « composantes connexes » ; ici, il reste une « composante connexe géante », en rouge, les autres composantes connexes sont nettement plus petites, voire même réduites à un seul sommet (en gris)
Les résultats les plus fameux de Erdős et Rényi concernent l’existence d’une « composante connexe géante » : tu imagines que le nombre initial de sommets est très grand, et après avoir retiré comme ça au hasard des arêtes, est-ce que tu vas encore avoir une composante connexe, disons, qui contient plus de la moitié des sommets, ou est-ce qu’au contraire toutes les composantes connexes sont petites ? Plus généralement, quelle va être la taille de la plus grande composante connexe ? Ce problème a été étudié en profondeur par Erdős et Rényi, et il est à l’origine de la théorie des graphes aléatoires, un domaine à l’interface de la combinatoire et des probabilités, qui est encore très actif.
ISOLER LA RACINE DANS LES ARBRES ALÉATOIRES
Au lieu des graphes complets, on peut aussi regarder ces histoires de percolation sur des « arbres ». Un arbre est un graphe qui n’a pas de cycle, c’est-à-dire que chaque fois qu’on retire une arête, on le découpe en deux. Le problème s’apparente alors à un processus de fragmentation.

Différents types de graphes. Dans le second, si on efface n’importe quelle arête, on le découpe en deux morceaux : c’est un arbre. Le quatrième est un arbre particulièrement simple : tous les sommets sont reliés à la racine
— L’arbre, c’est un peu l’opposé du graphe complet ?
C’est un peu l’opposé du graphe complet, oui, mais ça reste quelque chose dont la géométrie est très simple. Dans les années 1970, Meir et Moon se sont intéressés à certaines familles d’arbres aléatoires. Ils considéraient ce qu’on appelle des arbres enracinés, il y a un sommet particulier qu’on appelle la racine de l’arbre, et la question qu’ils s’étaient posée, c’était : si on retire les arêtes une par une au hasard, indépendamment les unes des autres, combien d’arêtes doit-on retirer pour isoler la racine ?
— Isoler la racine, ça veut dire que tu as retiré toutes les arêtes qui partaient de la racine ?
C’est ça. Chaque fois que tu enlèves une arête, tu découpes ton arbre en deux morceaux, et tu ne gardes que le morceau qui contient la racine, l’autre tu ne t’en occupes plus. Quand tu répètes ce procédé, le morceau qui contient la racine va devenir de plus en plus petit, et tu te demandes en combien d’étapes tu te retrouves avec seulement la racine. Ils ont regardé ce problème pour certaines catégories d’arbres, et notamment pour les « arbres aléatoires récursifs ». C’est-à-dire que maintenant, l’objet de départ, avant la percolation, va lui-même être aléatoire...
LES ARBRES ALÉATOIRES RÉCURSIFS

Construction d’un arbre aléatoire récursif. A la vingtième étape, on tire au hasard une boule d’une urne contenant les boules 0 à 19, et on relie le sommet numéro 20 au sommet dont le numéro a été tiré (ici le 13). On remet ensuite la boule tirée dans l’urne, ainsi qu’une nouvelle boule numérotée 20
Les arbres aléatoires récursifs sont des arbres aléatoires, peut-être parmi les plus simples qu’on puisse imaginer. Comme leur nom l’indique, on les construit de façon récursive, c’est-à-dire en ajoutant les sommets l’un après l’autre. Tu commences par le sommet numéro $0$, qui est ta racine. Ensuite tu ajoutes le sommet numéro $1$, tu n’as pas le choix, tu le relies à $0$. Ensuite tu ajoutes le sommet numéro $2$, tu as deux possibilités, tu le relies soit à $1$, soit à $0$, et pour décider de ce choix tu tires au hasard avec une chance sur deux. Tu ajoutes le sommet numéro $3$, tu as trois possibilités, tu le relies au sommet numéro $0$, $1$ ou $2$ en tirant au hasard avec une chance sur trois, et ainsi de suite. Tu obtiens un arbre aléatoire, aussi grand que tu veux. C’est une construction très simple, et qui en fait a des tas de liens avec d’autres objets de combinatoire.
— Si je mets tous les arbres imaginables ayant un nombre donné de sommets dans une même urne, et que j’en tire un au hasard, est-ce que j’obtiens la même chose ?

Un arbre aléatoire récursif à 15000 sommets

Un arbre aléatoire de Cayley à 27179 sommets
Non, pas du tout ! Le fait de construire les arbres aléatoires récursivement modifie considérablement la géométrie. Si on fait un tirage uniforme, comme tu le proposes, on obtient ce qu’on appelle un arbre de Cayley. Un arbre de Cayley, quelque part ça ressemble beaucoup plus à un vrai arbre, c’est beaucoup plus fin, beaucoup plus élancé qu’un arbre récursif [1]. Un arbre récursif, ça ressemble davantage à un buisson, c’est très touffu. On le voit sur les dessins, mais on s’en rend compte aussi, par exemple, en comparant les hauteurs, c’est-à-dire la distance entre la racine et un sommet typique. Pour un arbre de Cayley, la hauteur est proche de la racine carrée du nombre de sommets, alors qu’elle est proche du logarithme du nombre de sommets pour un arbre récursif. Et le fait que des arbres soient touffus ou pas, intuitivement c’est très important quand tu vas faire de la percolation, parce que c’est plus facile de déconnecter la racine de ton arbre quand il est très étiré que quand il est très touffu. Quand ton arbre est très touffu, si par exemple tu cherches isoler la racine, il faut vraiment couper de partout pour le faire, alors que pour un arbre de type Cayley ça va être fait de façon beaucoup plus rapide.

Graphes de la racine carrée de $x$ et du logarithme de $x$, pour $x$ entre $1$ et $1000$. La croissance du logarithme est beaucoup plus lente que celle de la racine.
ARBRES ALÉATOIRES RÉCURSIFS ET MODÈLES DE POPULATION
On peut aussi voir les arbres récursifs aléatoires comme des arbres généalogiques dans des modèles de population les plus simples qui soient, qu’on appelle les modèles de Yule. Dans ces modèles de population tous les individus vont avoir une durée de vie infinie. Tu pars d’un ancêtre, et chaque individu va donner naissance à un enfant (qui a donc un seul parent !), après un temps aléatoire donné par une certaine loi appelée loi exponentielle. Et puis il continue à vivre, et après un autre temps aléatoire indépendant il va donner naissance à un autre enfant, etc.. Bien sûr chaque enfant, lui, va se comporter de la même façon, donc il y aura des petits-enfants, des arrière-petits-enfants, etc.. Si tu énumères les individus selon leur ordre de naissance, $0$, $1$, $2$ etc., et tu arrêtes le processus après la naissance du $n$-ième individu, la généalogie est décrite par un arbre aléatoire récursif avec $n$ sommets.
Quand tu prends ce modèle de population, faire une percolation dessus, c’est-à-dire couper certaines arêtes, c’est aussi quelque chose de très naturel. Jusque-là tes individus étaient semblables les uns aux autres, ils n’avaient pas de spécificité. Tu vas imaginer qu’ils ont maintenant un type génétique, et tu vas introduire des mutations : chaque fois qu’un enfant nait, avec une certaine probabilité ça va être le clone exact de son ancêtre, et dans le cas contraire ça va être un mutant, c’est-à-dire un individu d’un type génétique différent : tu supposes que chaque fois que tu as une mutation, tu crées un nouveau type. Maintenant tu peux diviser ta population totale en sous-populations correspondant aux différents types génétiques ; eh bien, ceci revient à faire des coupes au hasard sur ton arbre généalogique, à faire exactement ce procédé de percolation qu’on a décrit précédemment.
ISOLATION DANS LES ARBRES RECURSIFS : LOI DES GRANDS NOMBRES
Ces arbres récursifs ont une propriété « fractale » tout à fait remarquable : quand tu retires une arête de ton arbre, tu le découpes en deux sous-arbres, et ces sous-arbres sont encore des arbres aléatoires récursifs (plus petits, bien sûr). Et ça c’est très facile à comprendre quand on prend par exemple le modèle de population : on a une mutation, et ensuite les deux populations évoluent de façon indépendante, en suivant les mêmes dynamiques qu’avant. Cette propriété est importante parce qu’elle permet de répéter le procédé : si tu as compris ce qui se passe lorsque tu enlèves une arête, comme tu sais qu’ensuite les deux morceaux vont évoluer indépendamment et selon les mêmes lois, tu peux très facilement continuer le processus. Autrement dit, l’hypothèse de branchement dont nous avons parlé au début est satisfaite pour les arbres récursifs aléatoires. Meir et Moon ont utilisé cette propriété pour étudier le nombre d’arêtes qu’il fallait supprimer pour isoler la racine, et ils ont montré que quand le nombre de sommets $n$ de l’arbre est grand, il y a une grande probabilité que ce nombre soit proche de $\frac{n}{\log(n)}$. On peut le voir comme une sorte de loi des grands nombres : on a une quantité aléatoire qui, quand $n$ devient grand, devient proche de $\frac{n}{log(n)}$ qui est une quantité déterministe, le hasard s’estompe peu à peu.
Beaucoup plus tard, ces travaux de Meir et Moon ont été précisés par Drmota, Iksanov, Möhle et Rösler. Puis Iksanov et Möhle ont donné une explication de leurs résultats en introduisant une technique dite de « couplage ». C’est là que j’ai commencé à m’intéresser à cette histoire, parce que j’avais étudié les processus de fragmentation, dont l’un des exemples concrets qu’on peut imaginer, c’est quand on coupe les arêtes d’un arbre, et là ils avaient une technique de couplage qui ramenait l’étude de certains problèmes de type fragmentation sur un arbre à des problèmes de marches aléatoires. Je me suis dit que c’était une méthode qui était sans doute très utile, avec laquelle on pouvait essayer d’étudier d’autres choses que ce problème d’isolation de la racine.
FRAGMENTATION DANS LES ARBRES RÉCURSIFS
Pour le graphe complet, Erdős et Rényi ne se sont pas intéressés spécialement à combien de coupes on doit faire pour isoler un sommet particulier, mais à l’existence de composantes connexes géantes, et plus généralement à la taille des composantes connexes.
Il semblait donc assez naturel de chercher à faire ce même genre d’étude pour les arbres récursifs.
Pour essayer de situer maintenant un peu plus précisément le cadre, avec Erich Baur, on a eu un programme d’étude qui est le suivant : on va se donner un grand arbre récursif, et puis on va retirer uniformément au hasard ses arêtes les unes après les autres.
On va ainsi détruire notre arbre progressivement, et on s’intéresse aux différents régimes qu’on va observer, un peu comme l’avaient fait Erdős et Rényi pour le graphe complet : jusqu’à quand va-t-il rester une composante connexe géante ? Tant qu’on a une composante connexe géante, quelle est la taille des autres composantes connexes ? Qu’est-ce qui se passe quand on cesse d’avoir une composante connexe géante ? etc., il y a plein de questions naturelles à étudier.

Fragmentation aléatoire d’un arbre aléatoire récursif
— Dans ce cadre, est-ce que la composante connexe qui contient la racine est privilégiée ?
À la différence de Meir et Moon et de leurs travaux sur l’isolation de la racine, tu ne t’intéresses plus du tout spécifiquement au sous-arbre qui contient la racine, mais à tous les sous-arbres que tu obtiens, et tu cherches à comprendre l’évolution de leur taille, c’est-à-dire leur nombre de sommets. Et tu ne peux pas vraiment le faire pour $n$ fixé, mais tu t’intéresses à ça quand $n$ est très grand.
MESURES DE DISLOCATION : VERS LES CARTES PLANAIRES
— Est-ce que vos travaux ouvrent d’autres perspectives ?
Finalement, à l’origine on s’est intéressés à ces questions d’une part parce qu’il y avait des problèmes analogues, pour d’autres modèles, qui avaient joué un rôle important, en particulier le graphe aléatoire d’Erdős-Rényi. Mais il s’est trouvé qu’en étudiant cette destruction d’arbres récursifs, ça nous a mis sur la piste d’objets mathématiques qui sont, je crois, assez intéressants.
Comme je l’ai expliqué au début, je me suis beaucoup intéressé à ces processus de fragmentation, dans lesquels une masse se scinde en plusieurs masses, et ainsi de suite, et on essaye de comprendre ce qui se passe après un grand nombre de dislocations. Dans cette théorie, il y a des « critères d’intégrabilité » pour ce qu’on appelle la « mesure de dislocation ». La mesure de dislocation, c’est ce qui décrit de façon infinitésimale la façon dont ces masses se disloquent ; tu ne peux pas prendre n’importe quoi comme mesure de dislocation, si tu prenais des mesures de dislocation avec de mauvaises « propriétés d’intégrabilité », toute ta masse se réduirait instantanément en poussière. Tu imagines un concasseur qui est beaucoup trop violent, tellement violent qu’il se produit un phénomène d’explosion instantanée.

Un critère d’intégrabilité non respecté ?
Et quand on a étudié la fragmentation des arbres récursifs, on est arrivé à une notion de mesure de dislocation naturellement liée à ce problème, mais de façon surprenante la condition d’intégrabilité n’était pas vérifiée. Le processus qu’on veut décrire est un processus de fragmentation, mais si on veut analyser les tailles des objets, on est obligés de faire ce qui s’appelle une « normalisation ». Le choix de cette normalisation fait qu’elle implique une croissance des composantes connexes que tu considères. C’est un petit peu comme si tu faisais grossir la taille en même temps que tu fragmentes. L’objet qu’on regarde alors a tendance à croitre, et en même temps on le découpe, ce qui le fait décroitre. S’il n’y avait pas cette croissance due à la normalisation, si on n’étudiait que ces dislocations, elles seraient tellement intenses qu’on ne verrait rien, instantanément il ne resterait que de la poussière.
Et ça c’est un phénomène que je n’avais pas envisagé, et qui est maintenant un de mes sujets d’étude. En particulier, c’est quelque chose qui va jouer un rôle important dans l’étude de ce qu’on appelle les « cartes planaires ». Les cartes planaires, c’est un sujet autour duquel il y a une très forte activité en ce moment, lié par exemple à des questions de gravitation quantique, sur lequel il y a de très beaux travaux. Il y a une certaine relation avec ces nouveaux processus qui vont combiner dislocation et croissance. On a commencé une série de travaux sur ce sujet en collaboration avec Nicolas Curien et Igor Kortchemski. Et finalement, je suis tombé dessus à partir de ce modèle de percolation dans les arbres aléatoires récursifs.
Jean Bertoin est né le 25 Mai 1961 à Lyon.
Il est élève de l’Ecole Normale Supérieure de Saint Cloud de 1980 à 1985, il soutient sa thèse en 1987, sous la direction de Marc Yor, à l’Université Pierre et Marie Curie (UPMC). Il est ensuite chargé de recherches au CNRS, puis professeur à l’UPMC.
Depuis 2011, il est professeur à l’Institut de mathématiques de l’université de Zurich. Le prix Thérèse Gautier lui est attribué en 2015 :« Ses travaux sur les processus aléatoires appelés processus de Lévy, dont le prototype est le mouvement brownien, ont conduit à un renouveau de cette branche importante des probabilités. Jean Bertoin a aussi apporté des contributions majeures aux processus de coalescence, qui fournissent des modèles mathématiques en génétique des populations. Il a enfin inventé la théorie des processus de fragmentation, qui étudie la manière dont un objet se fragmente de façon aléatoire au cours du temps. »
Cet article a été relu et corrigé par Jean Bertoin.
La rédaction d’Images des Mathématiques ainsi que l’auteur, souhaitent remercier pour leur relecture attentive, les relecteurs suivants : Claire Lacour, Michele Triestino, myg204 et Clement_M.
Notes
[1] Sous-entendu « arbre récursif aléatoire », ici et dans toute la suite.
[2] Ceci implique notamment que la probabilité d’être loin de la moyenne est beaucoup plus grande qu’avec la loi normale.
[3] Ceci n’arrive que lorsque $n$ est supérieur à $2^{1000}$, qui est un nombre gigantesque.
Partager cet article
Pour citer cet article :
Frédéric Le Roux — «Fragmentation d’arbres aléatoires - Une interview de Jean Bertoin» — Images des Mathématiques, CNRS, 2016
Laisser un commentaire
Actualités des maths
-
11 mai 2022Printemps des cimetières
-
3 mai 2022Comment les mathématiques se sont historiquement installées dans l’analyse économique (streaming, 5/5)
-
1er avril 2022Prix D’Alembert 2022 attribué à Jean-Michel Blanquer
-
10 mars 2022Géométries non euclidiennes mais dynamiques
-
6 mars 2022Contrôle et apprentissage automatique (streaming, 10/3)
-
24 février 2022Bienvenue au CryptoChallenge 2022 « Qui a volé les plans d’Ada Lovelace ? »
Commentaire sur l'article