Return probability on Bienaymé-Galton-Watson trees and spectral asymptotics of sparse Erdős-Rényi random graphs

Cet article établit une borne supérieure sous-exponentielle pour la probabilité de retour sur les arbres de Bienaymé-Galton-Watson supercritiques, résolvant ainsi un problème ouvert et permettant de déduire une queue de Lifshits pour le Laplacien des graphes aléatoires d'Erdős-Rényi supercritiques dans le cas d'une distribution de descendance de Poisson.

L'essentiel

Imaginez que vous êtes un explorateur perdu dans une forêt infinie et étrange. Cette forêt n'est pas comme les nôtres : elle grandit de manière aléatoire. Chaque arbre peut avoir zéro branche, une, dix ou cent, selon les lois du hasard. C'est ce qu'on appelle un arbre de Bienaymé-Galton-Watson.

Les auteurs de ce papier, Markus Heydenreich, Peter Müller et Sara Terveer, se posent une question très précise : Si vous marchez au hasard dans cette forêt, quelle est la probabilité que vous reveniez exactement au point de départ après un certain temps ?

Voici les deux grandes découvertes de leur voyage, expliquées avec des métaphores.

1. Le retour du randonneur perdu (La probabilité de retour)

Imaginez que vous marchez dans cette forêt. Parfois, la forêt est très dense et vous vous éloignez vite. Mais parfois, il y a des zones très "lentes" : des longs couloirs droits, des impasses, ou des zones où les arbres sont si clairsemés que vous vous y enfilez comme dans un labyrinthe sans issue.

• Le problème : Si vous tombez dans l'une de ces zones "lentes" (des branches linéaires ou des feuilles isolées), vous mettez beaucoup de temps à en sortir. Cela augmente vos chances de revenir au point de départ, car vous restez bloqué dans le coin.
• L'ancienne théorie : Avant ce papier, les mathématiciens savaient que cette probabilité de retour était faible, mais ils ne savaient pas exactement à quelle vitesse elle devenait faible. Ils avaient des estimations un peu floues.
• La découverte : Les auteurs ont prouvé que cette probabilité de retour décroît très vite, mais pas de façon "exponentielle" (comme une chute libre), mais de façon un peu plus lente, appelée "sous-exponentielle".
  • L'analogie : Imaginez que la probabilité de retour est comme une bougie qui fond. Les anciens disaient : "Elle fond vite, mais on ne sait pas trop à quelle vitesse". Les auteurs disent : "Non, on sait exactement ! Elle fond selon une règle précise : la vitesse de fonte dépend de la racine cubique du temps ($t^{1/3}$)."
  • Pourquoi c'est important ? C'est la réponse définitive à un problème ouvert depuis 1998. Ils ont montré que même si la forêt a des zones piégeuses, la probabilité de revenir au départ s'effondre très rapidement, et ils ont trouvé la formule exacte pour cette chute.

2. Les vibrations de la forêt (Les valeurs propres du Laplacien)

Maintenant, changeons de perspective. Au lieu de marcher, imaginez que la forêt entière est une immense cloche ou un instrument de musique géant. Si vous la frappez, elle vibre. Chaque vibration a une fréquence (une note). En mathématiques, ces fréquences s'appellent des valeurs propres.

• Le contexte : Les chercheurs étudient les "notes graves" de cette forêt (les petites valeurs propres).
• La découverte : Ils ont découvert que les très basses notes (presque le silence) sont extrêmement rares dans les forêts géantes qui survivent (les forêts "supercritiques").
• L'analogie : Imaginez que vous cherchez une aiguille dans une botte de foin. Ici, c'est encore pire : chercher une très basse fréquence, c'est comme chercher un fantôme dans une tempête. La probabilité de trouver une telle note est si faible qu'elle suit une règle mathématique très spécifique (appelée "queue de Lifshits").
  • Cela signifie que pour avoir une note très grave, il faudrait que la forêt ait des parties infiniment longues et droites, ce qui est statistiquement presque impossible dans une forêt qui grandit de manière aléatoire.
• Le lien avec la réalité : Ce résultat s'applique aussi aux réseaux sociaux ou aux réseaux internet (modélisés par des graphes d'Erdős-Rényi). Cela aide à comprendre comment l'information ou les ondes se propagent (ou ne se propagent pas) dans ces réseaux.

En résumé

Ce papier est comme un guide de survie pour les mathématiciens qui étudient le hasard dans les structures infinies.

1. Pour le randonneur : Ils ont trouvé la formule exacte pour dire à quelle vitesse il est "improbable" de revenir au point de départ dans une forêt aléatoire, même si la forêt a des pièges.
2. Pour le musicien : Ils ont prouvé que les "notes graves" dans ces forêts aléatoires sont si rares qu'elles disparaissent presque totalement, suivant une loi mathématique très précise.

C'est un travail de précision qui ferme un chapitre de l'histoire des mathématiques (résolvant un problème vieux de 25 ans) et ouvre la porte à une meilleure compréhension de la façon dont les réseaux complexes (comme Internet ou les réseaux neuronaux) se comportent.

Résumé technique

1. Problématique et Contexte

L'article s'attaque à deux problèmes fondamentaux liés dans le domaine de la probabilité et de la théorie spectrale des graphes aléatoires :

1. Probabilité de retour sur les arbres de Bienaymé–Galton–Watson (BGW) :
   L'objectif est de déterminer le comportement asymptotique de la probabilité de retour à la racine d'une marche aléatoire simple (discrete-time) sur un arbre BGW supercritique, conditionnée à la non-extinction.

   • Contexte : Pour les arbres sans feuilles ($\mu(0)=0$), Piau (1998) avait établi des bornes exponentielles. Cependant, lorsque la distribution des descendants $\mu$ autorise des feuilles ($\mu(0)>0$) ou des branches linéaires ($\mu(1)>0$), Piau avait prouvé une borne inférieure sous-exponentielle de la forme $\exp(-c't^{1/3})$. La borne supérieure correspondante restait ouverte ou sous-optimale (exposants $1/5$ ou $1/6$ selon la distribution).

2. Asymptotiques spectrales des graphes d'Erdős–Rényi (ER) :
   L'article étudie la distribution des valeurs propres du Laplacien de graphes ER supercritiques ($\lambda > 1$) avec un degré moyen fini ($Np(N) \to \lambda$).

   • Problème : Comprendre le comportement de la densité d'états (mesure $\sigma_\lambda$) près de la bordure spectrale inférieure ($E=0$). Il s'agit de prouver un comportement de "queue de Lifshits" (Lifshits tail), c'est-à-dire une décroissance exponentielle très rapide de la probabilité d'avoir des valeurs propres très petites.

2. Méthodologie

Les auteurs utilisent une approche combinant l'analyse probabiliste des arbres aléatoires et la théorie spectrale des opérateurs de marche aléatoire.

A. Analyse des arbres BGW conditionnés

• Conditionnement : L'étude se concentre sur l'arbre conditionné à la survie ($|T|=\infty$). Les auteurs utilisent la décomposition de l'arbre en individus "survivants" (type S, descendance infinie) et "extincts" (type E, descendance finie).
• Propriété de Markov arborescente : Ils exploitent l'indépendance conditionnelle entre l'ascendance et la descendance d'un nœud, une fois son type (S ou E) fixé.

B. Isopérimétrie et "Mauvaises Régions"

• Cœurs isolés (Isolated Cores) : L'analyse repose sur la notion de "cœurs isolés" $q$-isoles, définis comme des sous-graphes finis ayant un rapport isopérimétrique (nombre d'arêtes de bord / volume) très faible. Ces régions ralentissent la marche aléatoire.
• Océans et Îles : L'arbre est décomposé en "îles" (les cœurs isolés) et "océans" (le reste).
• Marche induite : Les auteurs définissent une marche aléatoire "induite" sur les océans, qui saute par-dessus les îles. Grâce aux propriétés d'expansion ancrée (anchored expansion) des arbres BGW supercritiques, ils montrent que la norme de l'opérateur de Markov sur les océans est strictement inférieure à 1, garantissant une décroissance exponentielle rapide de la probabilité de retour si la marche évite les grandes îles.

C. Estimation de la probabilité de visite des îles

• Le cœur de la preuve du Théorème 1.1 consiste à montrer que, sous la mesure "annealed" (moyenne sur les arbres et les marches), la probabilité que la marche aléatoire visite une île de taille supérieure à $t^{1/3}$ avant le temps $t$ est très faible.
• Ils utilisent une analyse conjointe de l'arbre et de la trajectoire pour borner cette probabilité par $\exp(-c t^{1/3})$.

D. Lien avec le spectre du Laplacien

• Pour le théorème spectral (Théorème 1.3), ils utilisent le fait que la limite faible locale des graphes ER est l'arbre BGW de Poisson.
• Ils relient la probabilité de retour de la marche aléatoire (via le noyau de chaleur) à la fonction de répartition spectrale du Laplacien normalisé.
• Une inégalité clé (Lemme 5.1) permet de transférer les bornes du Laplacien normalisé $\tilde{\Delta}$ vers le Laplacien standard $\Delta$.

3. Résultats Principaux

Théorème 1.1 : Bornes optimales pour la probabilité de retour

Pour une distribution de descendants $\mu$ avec une espérance finie $\lambda > 1$ :
$$\mathbb{E}_\mu \left[ P_o^T(X_t = o) \right] \leq \exp\left( -c t^{1/3} \right)$$

• Signification : Cette borne supérieure est optimale en termes de puissance de $t$ dans l'exposant. Elle complète les résultats de Piau (1998) et de Müller & Terrier (2025) en établissant l'exposant $1/3$ pour toutes les distributions $\mu$ (y compris celles avec des feuilles), et non seulement pour les distributions à support fini ou sans feuilles.
• Cas Poissonien : Ce résultat s'applique spécifiquement aux arbres BGW de Poisson, cruciaux pour les graphes ER.

Théorème 1.3 : Queue de Lifshits pour les graphes Erdős–Rényi

Pour les graphes ER supercritiques ($\lambda > 1$), la densité d'états $\sigma_\lambda$ du Laplacien satisfait, pour $E$ petit :
$$\exp\left( -c' E^{-1/2} \right) \leq \sigma_\lambda(]0, E]) \leq \exp\left( -c E^{-1/2} \right)$$

• Résolution d'un problème ouvert : Cela répond à une question posée il y a 20 ans par Khorunzhy, Khoruzhenko et Pastur (2006).
• Interprétation physique : La décroissance en $E^{-1/2}$ indique que les petites valeurs propres proviennent principalement de longues chaînes linéaires (branches) dans le graphe, qui agissent comme des pièges pour la marche aléatoire.

Corollaire 1.5 : Marche en temps continu

Les résultats s'étendent aux marches aléatoires en temps continu (générées par le Laplacien ou le Laplacien normalisé), avec la même décroissance $\exp(-c s^{1/3})$.

4. Contributions Clés

1. Optimalité de l'exposant $1/3$ : La preuve démontre que l'exposant $1/3$ est universel pour les arbres BGW supercritiques, indépendamment de la présence de feuilles ou de branches linéaires, résolvant ainsi un problème ouvert depuis 1998.
2. Nouvelle technique d'analyse : L'article introduit une flexibilité dans le traitement des régions "mauvaises" (les îles) en utilisant la mesure annealed. Cela permet de traiter des distributions de descendants générales sans hypothèses de décroissance rapide.
3. Lien Spectral-Probabiliste : L'article établit un pont rigoureux entre la probabilité de retour sur les arbres aléatoires et le comportement spectral des graphes ER à degré moyen fini, un régime où les méthodes spectrales classiques (valables pour $Np \to \infty$) échouent.
4. Preuve concise : Contrairement aux travaux antérieurs complexes, la preuve du Théorème 1.1 est décrite comme "surprenamment courte et simple", reposant sur des propriétés isopérimétriques et la structure de Markov de l'arbre.

5. Signification et Impact

• Théorie des probabilités : Ce travail affine considérablement notre compréhension de la dynamique des marches aléatoires sur les structures arborescentes aléatoires, en particulier dans le régime où la structure locale n'est pas uniforme (présence de feuilles).
• Physique Mathématique et Science des Réseaux : Les résultats sur les queues de Lifshits sont fondamentaux pour la théorie des systèmes désordonnés. La décroissance $\exp(-c E^{-1/2})$ est un indicateur de la localisation des états propres aux basses énergies, liée à la présence de défauts topologiques (les branches linéaires) dans le réseau.
• Limites de la sparsité : L'article pousse les frontières de l'analyse spectrale vers des graphes très clairsemés (degré moyen fini), un domaine où les outils matriciels standards (comme la méthode des moments ou l'analyse de Stieltjes) sont moins efficaces que les approches basées sur la limite faible locale (Benjamini-Schramm).

En résumé, cet article fournit une solution complète et optimale au problème de la probabilité de retour sur les arbres BGW et en déduit des résultats profonds sur le spectre des graphes aléatoires, unifiant ainsi la théorie des arbres de branchement et la théorie spectrale des graphes aléatoires.