Asymptotic normality for general subtree counts in conditioned Galton--Watson trees

Cet article démontre que, sous une condition de moment modérée, le nombre d'occurrences d'un arbre enraciné fixé comme sous-arbre dans un arbre de Galton-Watson conditionné à avoir $n$ nœuds suit asymptotiquement une loi normale, confirmant ainsi une conjecture de Janson et établissant les cas où cette distribution dégénère.

L'essentiel

🌳 L'histoire des arbres qui poussent de manière aléatoire

Imaginez que vous êtes un jardinier qui observe une forêt magique. Dans cette forêt, les arbres ne poussent pas selon des règles strictes, mais selon une sorte de loterie. C'est ce que les mathématiciens appellent un arbre de Galton-Watson.

Chaque branche d'un arbre a une chance de se diviser en plusieurs nouvelles branches (des enfants) ou de s'arrêter. Si, en moyenne, chaque branche donne naissance à exactement une nouvelle branche, on dit que l'arbre est "critique". Il ne grandit pas éternellement, ni ne disparaît immédiatement ; il atteint une taille variable.

Dans cet article, les auteurs (Fameno et Dimbinaina) étudient une version spéciale de ces arbres : les arbres conditionnés. C'est comme si vous preniez un échantillon de la forêt et que vous ne regardiez que les arbres qui ont exactement $n$ feuilles (ou nœuds).

🔍 Le problème : Compter les petits motifs

Leur question est la suivante : Si vous regardez un très grand arbre de cette forêt (avec $n$ très grand), pouvez-vous prédire combien de fois un petit motif spécifique (par exemple, une petite branche en forme de "Y" ou une ligne droite de 3 nœuds) apparaît dans l'arbre ?

Ils appellent ce motif une sous-arbre. Ils veulent savoir :

1. Quelle est la moyenne de ces apparitions ?
2. Est-ce que le nombre d'apparitions suit une courbe en cloche (une distribution normale) quand on regarde des arbres de plus en plus grands ?

📈 La grande découverte : La loi des grands nombres et la cloche

Les auteurs ont prouvé quelque chose de très important :

1. La croissance est linéaire : Si vous doublez la taille de votre arbre, vous doublez à peu près le nombre de fois où vous trouvez votre petit motif. C'est logique et prévisible.
2. La régularité (La Cloche) : Même si la croissance est aléatoire, quand l'arbre devient gigantesque, la répartition de ces motifs suit une courbe en cloche parfaite (la loi normale). C'est comme si le chaos de la croissance finissait par créer un ordre statistique très lisse.

L'analogie de la foule :
Imaginez une foule de 100 000 personnes. Si vous demandez à chacun de lancer une pièce, le résultat de chaque personne est aléatoire (pile ou face). Mais si vous comptez le nombre total de "Pile" dans toute la foule, le résultat sera toujours très proche de la moitié, et si vous répétez l'expérience des milliers de fois, les résultats formeront une courbe en cloche parfaite. C'est ce qui arrive avec les motifs dans les arbres géants.

⚠️ La condition secrète : La règle de la "patience"

Pour que cette courbe en cloche apparaisse, il y a une condition importante sur la façon dont les arbres poussent. Les auteurs disent qu'il faut que la probabilité d'avoir des branches très nombreuses soit "raisonnable".

L'analogie du feu d'artifice :
Imaginez que la croissance d'un arbre est comme un feu d'artifice.

• Si la plupart des fusées éclatent en quelques étincelles, tout est calme et prévisible.
• Mais si, très rarement, une fusée explose en un million d'étincelles (ce qui est mathématiquement possible mais très extrême), cela peut tout gâcher.

Les auteurs montrent que si ces "explosions géantes" (des moments où un arbre a trop de branches d'un coup) sont trop fréquentes ou trop puissantes, la courbe en cloche disparaît. Le résultat devient imprévisible et ne suit plus la loi normale. Ils ont trouvé la limite exacte de cette "patience" nécessaire pour que la magie opère.

🚫 Les cas où ça ne marche pas (Les exceptions)

Il y a quelques cas particuliers où la courbe en cloche ne se forme pas, même avec de grands arbres :

• Cas dégénéré : Parfois, le motif est si spécial que son nombre d'apparitions est toujours le même, peu importe l'arbre. C'est comme si vous cherchiez un motif qui ne peut exister que d'une seule façon. Dans ce cas, il n'y a pas de variation, donc pas de courbe en cloche.
• Cas extrêmes : Si les règles de croissance de l'arbre sont trop "sauvages" (comme dans l'exemple du feu d'artifice), la variance (la mesure du désordre) devient trop grande et la prédiction normale échoue.

🏆 Pourquoi c'est important ?

Avant cet article, les mathématiciens (comme Svante Janson) avaient une intuition forte que cela devait marcher, mais ils n'avaient pas la preuve complète pour tous les types d'arbres.

Ces auteurs ont :

1. Confirmé la conjecture : Ils ont prouvé que oui, pour presque tous les arbres "normaux", le comptage des motifs suit une loi normale.
2. Défini les limites : Ils ont montré exactement jusqu'où on peut pousser les règles de croissance avant que la loi ne s'effondre.
3. Donné des contre-exemples : Ils ont créé des scénarios théoriques où, si on enlève une seule condition, tout le système s'effondre, prouvant que leurs règles sont optimales.

En résumé

C'est une histoire de prévisibilité dans le chaos. Même si la croissance d'un arbre est un processus aléatoire et complexe, si on regarde des arbres suffisamment grands et si les règles de croissance ne sont pas trop folles, la répartition des petits motifs à l'intérieur devient parfaitement prévisible et suit une loi mathématique élégante : la courbe en cloche.

Résumé technique

1. Problématique et Contexte

L'article s'intéresse à la statistique des arbres aléatoires, plus précisément aux arbres de Galton-Watson conditionnés ($T_n$) ayant exactement $n$ nœuds. Le modèle repose sur une distribution de descendance $\xi$ critique ($E[\xi]=1$) et apériodique.

Le problème central est l'étude asymptotique du nombre d'occurrences d'un arbre enraciné et ordonné fixe $t$ (appelé "sous-arbre général") dans un grand arbre $T_n$.

• Définition : Un sous-arbre général $t$ est un sous-graphe induit par un nœud et certains de ses descendants, où l'ordre des branches est préservé et où le degré d'un nœud image dans $T$ est supérieur ou égal à son degré dans $t$.
• Fonctionnelle : Soit $N_t(T)$ le nombre total d'occurrences de $t$ dans $T$. Cette fonctionnelle possède une propriété additive :
  $$N_t(T) = \sum_{k=1}^d N_t(T_k) + n_t(T)$$
  où $T_1, \dots, T_d$ sont les sous-arbres attachés à la racine de $T$, et $n_t(T)$ est le nombre d'occurrences de $t$ attachées directement à la racine (fonction de "péage" ou toll function).

L'objectif est de déterminer si la variable aléatoire $N_t(T_n)$ suit une loi normale asymptotique lorsque $n \to \infty$, et d'identifier les conditions nécessaires sur la distribution $\xi$ pour que cela soit vrai.

2. Méthodologie

Les auteurs utilisent une approche combinant l'analyse des moments, la théorie des arbres de Kesten (arbres de taille biaisée) et une méthode de troncature (truncation argument).

A. Outils Préliminaires

• Arbre de Kesten ($\hat{T}$) : Ils utilisent l'arbre de taille biaisée infini pour approximer localement la structure de $T_n$. La distribution locale de $\hat{T}$ est définie par $P(\hat{T}(M)=T) = w_M(T)P(T(M)=T)$, où $w_M(T)$ est le nombre de nœuds à distance $M$ de la racine.
• Lemmes de bornes de moments : Ils établissent des lemmes (Lemmes 2 et 3) prouvant que sous certaines conditions de moments sur $\xi$, les espérances conditionnelles de $n_t(T_n)$ et de ses produits croisés restent bornées.

B. Stratégie de Troncature

La preuve de la normalité centrale repose sur la décomposition de la fonctionnelle additive en deux parties via une troncature à une hauteur $p$ :

1. Partie locale ($F_{1,p}$) : Comprend les contributions des sous-arbres de taille inférieure à $p$. Pour $p$ fixe, cette partie est bornée et locale, permettant d'appliquer des théorèmes de limite centrale existants (référence [8]).
2. Partie résiduelle ($F_{p,\infty}$) : Représente l'erreur de troncature. L'objectif est de montrer que la variance de cette partie devient négligeable lorsque $p \to \infty$.

C. Estimation de la Variance

Un point crucial est l'estimation de la variance $\text{Var}(N_t(T_n))$. Les auteurs démontrent que sous une condition de moment forte, la variance croît linéairement en $n$. Ils utilisent l'inégalité de Minkowski et des estimations précises sur les termes d'erreur pour prouver que la variance de l'erreur de troncature tend vers 0 uniformément.

3. Résultats Principaux

Théorème 1 : Normalité Asymptotique

Sous l'hypothèse que la distribution de descendance $\xi$ satisfait la condition de moment :
$$E[\xi^{2\Delta(t)+1}] < \infty$$
où $\Delta(t)$ est le degré sortant maximal dans l'arbre $t$, les auteurs prouvent que :

1. Espérance : $E[N_t(T_n)] = \mu n + o(\sqrt{n})$, où $\mu = E[n_t(\hat{T})]$.
2. Variance : $\text{Var}(N_t(T_n)) = \gamma^2 n + o(n)$, avec $\gamma \ge 0$.
3. Convergence en loi : Si $\gamma > 0$ (cas non dégénéré), alors :
   $$\frac{N_t(T_n) - \mu n}{\gamma \sqrt{n}} \xrightarrow{d} \mathcal{N}(0, 1)$$

Conditions de Non-Dégénérescence (Section 4)

Les auteurs caractérisent les cas où $\gamma = 0$ (variance bornée).

• Proposition 8 : $\gamma > 0$ si l'on peut trouver deux arbres $\tau_1$ et $\tau_2$ de même taille, ayant la même structure jusqu'à la hauteur de $t$, mais un nombre d'occurrences de $t$ différent.
• Proposition 9 : Si $\gamma = 0$, alors $N_t(T)$ est essentiellement une fonction linéaire de la taille de l'arbre et des comptes de ses sous-arbres "franges" (fringe subtrees).
• Cas dégénérés : Des exemples incluent les chemins de longueur fixe ou des distributions $\xi$ non apériodiques.

Optimalité de la Condition de Moment (Section 5)

Les auteurs montrent que la condition $E[\xi^{2\Delta+1}] < \infty$ est proche de l'optimalité :

• Exemple 11 (Arbre en chemin) : Si $E[\xi^3] = \infty$ (alors que $E[\xi^{3-\epsilon}] < \infty$), la variance de $N_t(T_n)$ pour un chemin de longueur 2 diverge plus vite que linéairement, et la convergence normale échoue.
• Exemple 12 (Arbre étoile) : Si $E[\xi^{2\Delta}] = \infty$ (alors que $E[\xi^{\Delta+2}] < \infty$), la variance croît de manière super-linéaire ($\text{Var}(N_t(T_n))/n \to \infty$).

4. Contributions Clés

1. Confirmation d'une conjecture de Janson : L'article résout une conjecture ouverte (Janson [9]) affirmant que la normalité centrale s'applique aux comptes de sous-arbres généraux sous des conditions de moments raisonnables, étendant les résultats précédents qui ne couvraient que les distributions de descendance bornées.
2. Généralité du modèle : Contrairement aux études antérieures sur les "sous-arbres franges" (fringe subtrees), ce travail traite des sous-arbres généraux (embeddings), ce qui est techniquement plus complexe car la fonction de péage $n_t(T)$ n'est pas locale pour des arbres de hauteur $\ge 2$.
3. Analyse fine de la variance : La preuve fournit des estimations explicites de la variance et identifie précisément les mécanismes menant à la dégénérescence ou à la violation de la loi normale.
4. Optimalité des hypothèses : En fournissant des contre-exemples lorsque la condition de moment est violée, l'article délimite les frontières de validité du théorème central limite pour ces structures.

5. Signification et Impact

Ce travail est une avancée significative dans la théorie des arbres aléatoires. Il établit un cadre robuste pour l'analyse asymptotique de fonctionnelles additives complexes sur les arbres de Galton-Watson conditionnés.

• Théorique : Il unifie et généralise des résultats dispersés dans la littérature, prouvant que la normalité est la règle générique pour les comptes de motifs dans les arbres critiques, à condition que les queues de la distribution de descendance ne soient pas trop lourdes.
• Pratique : Les résultats s'appliquent à de nombreuses familles d'arbres classiques (arbres étiquetés, arbres plans, arbres de recherche binaires, etc.) dès lors que la distribution de descendance sous-jacente possède des moments d'ordre suffisant.
• Méthodologique : L'utilisation combinée de la troncature et de l'arbre de Kesten offre une méthode puissante pour traiter des fonctionnelles non-locales, ouvrant la voie à l'analyse d'autres paramètres structurels complexes.

En résumé, l'article démontre que, sauf dans des cas pathologiques spécifiques, le nombre d'occurrences d'un motif arborescent dans un grand arbre critique suit une loi normale, avec une moyenne et une variance proportionnelles à la taille de l'arbre, sous réserve d'une condition de moment sur la descendance.