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

This paper establishes an optimal subexponential upper bound for the annealed return probability of simple random walks on supercritical Bienaymé-Galton-Watson trees and applies this result to derive a Lifshits tail for the empirical eigenvalue distribution of the graph Laplacian on supercritical Erdős-Rényi random graphs.

The Gist

Imagine you are lost in a massive, ever-growing forest. This isn't a normal forest with a fixed map; it's a magical forest that grows randomly. Every time you stand at a tree, that tree might sprout 0, 1, 2, or even 100 new branches (trees) in the next generation. Some branches might die out immediately, while others grow into massive, infinite jungles.

This is the world of Bienaymé–Galton–Watson trees (BGWTs). It's a mathematical model for how things branch out, like family trees, viral infections, or the structure of the internet.

Now, imagine a tiny ant (a random walker) starting at the very bottom of this forest (the root). The ant takes steps randomly, choosing any neighboring branch with equal chance. The big question the authors ask is: How likely is it that the ant returns to the starting point after a long time?

Here is the story of their discovery, broken down into simple concepts.

1. The "Bad" Forests and the "Good" Forests

In a perfectly balanced forest where every tree has at least two children, the ant gets lost very quickly. The forest expands so fast that the ant's chance of finding its way back drops exponentially (like a lightbulb turning off instantly).

But what if the forest has "dead ends"?

• Some trees might have no children (leaves).
• Some might have only one child (a long, thin line).

If the forest is full of these long, thin lines, the ant can get stuck walking back and forth on a straight path for a long time. This makes it much harder to prove that the ant will get lost. In fact, previous mathematicians knew the ant would eventually get lost, but they couldn't pin down exactly how fast the probability of returning drops when these "thin lines" exist. They had a loose upper bound, but it wasn't the best possible answer.

The Paper's Breakthrough:
The authors proved that even in a forest full of these tricky, thin lines, the ant's chance of returning home drops at a very specific, predictable speed. It doesn't drop instantly (exponentially), but it drops sub-exponentially.

Think of it like this:

• Exponential decay: Like a firework fading away in a split second.
• Sub-exponential decay (their result): Like a slow-burning fuse. It takes longer to fade, but it does fade.

They found the "fuse" burns at a rate related to the cube root of time ($t^{1/3}$). This is the "optimal" speed; you can't make the ant get lost any slower than this, no matter how many dead ends the forest has.

2. The "Annealed" View: Looking at the Average Forest

The authors didn't just look at one specific forest. They looked at the average of all possible forests.

• Quenched: "Here is this specific forest. How does the ant do?"
• Annealed: "If we build a million random forests and watch an ant in each one, what is the average chance of returning?"

They proved that even when you average out all the weird, unlucky forests with long dead ends, the "return probability" still follows that $t^{1/3}$ rule. This solved a puzzle that had been open for over 20 years.

3. The Connection to Random Networks (Erdős–Rényi Graphs)

Why does this matter? Because these branching trees are actually the "local blueprint" for Erdős–Rényi random graphs.

Imagine a party where $N$ people are invited. Every pair of people flips a coin to decide if they will shake hands. If the coin is biased just right, the party forms a giant cluster of connected people (a "giant component") and some small, isolated groups.

Mathematicians study the spectrum (the "notes") of these networks. Specifically, they look at the Laplacian, a mathematical object that describes how "vibrations" or "information" flow through the network.

• Low notes (eigenvalues near 0): These correspond to parts of the network that are very rigid or isolated (like those long, thin lines in the forest).
• High notes: These correspond to the busy, connected parts.

The authors used their "ant in the forest" result to predict the behavior of these low notes. They showed that the number of these "low notes" drops off incredibly fast as you get closer to zero. This is called a Lifshits tail.

The Analogy:
Imagine a piano made of random strings. Most strings are tight and produce high notes. But some strings are very loose (the "dead ends" in the forest). The authors proved that the chance of finding a string so loose it produces a near-silent note is vanishingly small, and they calculated exactly how small.

4. Why is this a Big Deal?

• Solving a Mystery: They closed a 20-year-old gap in math where previous methods failed because the "forest" had too many dead ends.
• New Tools: They developed a clever way to handle the "bad" parts of the forest (the long lines) by treating the forest and the ant as a single, combined system.
• Real-World Impact: This helps us understand the stability and behavior of complex networks, from social media connections to the structure of the internet, especially when they are sparse (not everyone is connected to everyone).

Summary in One Sentence

The authors proved that even in a randomly growing, messy forest full of dead ends, a wandering ant will almost certainly get lost at a precise, predictable speed, and this discovery helps us understand the hidden "vibrations" of massive, random networks.

Technical Summary

1. Problem Statement

The paper addresses two interconnected problems in probability theory and spectral graph theory:

1. Return Probability on BGWTs: Determining the precise asymptotic decay rate of the annealed return probability for a simple random walk on a supercritical Bienaymé–Galton–Watson tree (BGWT) conditioned on non-extinction. Specifically, the authors aim to resolve the case where the offspring distribution allows for leaves ($\mu(0)>0$) or linear chains ($\mu(1)>0$). Previous work by Piau (1998) established a lower bound of $\exp(-ct^{1/3})$ and an upper bound of $\exp(-ct^{1/6})$ for general distributions, leaving a gap in the exponent.
2. Spectral Asymptotics of Erdős–Rényi Graphs: Investigating the Lifshits tail behavior (the behavior of the density of states near the bottom of the spectrum, $E=0$) for the graph Laplacian of sparse Erdős–Rényi random graphs $G(N, \lambda/N)$ with finite mean degree $\lambda > 1$. This regime is mathematically challenging because standard spectral methods for dense graphs ($Np \to \infty$) do not apply due to the vanishing row/column sums of the Laplacian.

2. Methodology

The authors employ a combination of probabilistic coupling, isoperimetric analysis, and spectral theory.

A. Analysis of Random Walks on Trees (Theorem 1.1)

To derive the optimal upper bound for the return probability, the authors utilize a geometric decomposition of the tree based on isoperimetric properties:

• Isolated Cores and Islands: They define "bad" regions in the tree called $q$-isolated cores (subgraphs with a small edge boundary relative to their volume). The union of these forms $q$-islands. The complement is the $q$-ocean.
• Induced Random Walk: They construct an induced random walk on the $q$-ocean that "jumps over" the islands. By proving that the operator norm of the Markov kernel on the ocean is strictly bounded away from 1 (Theorem 3.7), they establish exponential decay for walks that stay within the ocean.
• Annealed Measure and Tree Markov Property: The core innovation is the joint analysis of the random tree and the random walk under the annealed measure (averaging over both tree realizations and walk paths). They utilize the tree Markov property conditioned on survival (distinguishing between "survivor" and "extinct" types of vertices) to decouple the ancestry and progeny of the vertex where the walk hits a bad region.
• Estimation of "Bad" Events: They prove that the probability of the random walk hitting a large ($>t^{1/3}$) island before time $t$ decays as $\exp(-ct^{1/3})$. This is achieved by showing that the existence of such large low-isoperimetric regions is exponentially rare in supercritical BGWTs.

B. Spectral Theory and Lifshits Tails (Theorem 1.3)

To connect the random walk results to the spectrum of the Laplacian:

• Local Weak Limit: They leverage the fact that the local weak limit of sparse Erdős–Rényi graphs is the BGWT with Poisson offspring distribution.
• Normalization: They relate the standard graph Laplacian $\Delta$ to the normalized graph Laplacian $\tilde{\Delta}$. Using a Min-Max theorem argument (Lemma 5.1), they show that the spectral projection of $\Delta$ is bounded by that of $\tilde{\Delta}$.
• Tauberian Arguments: They use the return probability bounds (Theorem 1.1) to bound the heat kernel of the normalized Laplacian. Through Laplace transform techniques and optimization of time parameters, they translate the time-decay $\exp(-ct^{1/3})$ into an energy-decay $\exp(-cE^{-1/2})$ for the spectral density near zero.
• Decomposition: The total spectral measure is decomposed into contributions from the finite (extinct) trees and the infinite (surviving) trees. The finite part is handled by existing literature (KKM06), while the infinite part relies on the new Theorem 1.1.

3. Key Contributions and Results

Theorem 1.1: Optimal Return Probability Bound

• Result: For a supercritical BGWT with offspring distribution $\mu$ having a finite first moment $\lambda > 1$, the annealed return probability satisfies:
  $$\mathbb{E}_\mu \left[ P^T_o (X_t = o) \right] \leq \exp(-c t^{1/3})$$
  for all $t \in \mathbb{N}_0$.
• Significance: This closes the gap left by Piau (1998) and recent improvements (MS25). It proves that the exponent $1/3$ is optimal for all offspring distributions (including those with leaves or linear chains), not just those without leaves. The proof is notably shorter and more flexible than previous approaches, relying on the annealed measure's ability to treat the tree and walk jointly.

Theorem 1.3: Lifshits Tail for Erdős–Rényi Graphs

• Result: For the graph Laplacian on supercritical Erdős–Rényi graphs ($G(N, \lambda/N)$ with $\lambda > 1$), the integrated density of states $\sigma_\lambda$ near zero satisfies:
  $$\exp(-c' E^{-1/2}) \leq \sigma_\lambda((0, E]) \leq \exp(-c E^{-1/2})$$
  for small $E > 0$.
• Significance: This resolves an open question from KKM06 (2006). The $E^{-1/2}$ decay indicates that small eigenvalues are dominated by long linear segments (chains) in the graph, which act as "traps" for the random walk. The result extends to the supercritical phase, a regime previously difficult to analyze due to the presence of a giant component.

Corollary 1.5: Continuous-Time Random Walks

• The authors extend their discrete-time results to continuous-time random walks (both standard and normalized), establishing the same $t^{1/3}$ decay rate for the annealed return probability.

4. Significance and Impact

1. Resolution of a Long-Standing Open Problem: The paper provides a complete solution to the return probability problem on BGWTs, confirming the universality of the $t^{1/3}$ exponent regardless of the specific offspring distribution (provided $\lambda > 1$).
2. Bridging Discrete and Spectral Analysis: It successfully bridges the gap between probabilistic properties of random walks (return probabilities) and spectral properties of random operators (Laplacian eigenvalues) in the sparse regime.
3. Methodological Innovation: The technique of analyzing the "bad" regions (islands) under the annealed measure, rather than conditioning on a fixed tree, offers a powerful new tool for studying random walks on random graphs. This approach allows for efficient handling of general offspring distributions where previous "quenched" (fixed tree) methods struggled.
4. Applications to Physics and Network Science: The results on Lifshits tails are crucial for understanding the low-energy behavior of quantum systems on random networks and the dynamics of diffusion processes in sparse, heterogeneous environments. The specific $E^{-1/2}$ scaling provides insight into how structural heterogeneity (leaves and chains) affects spectral gaps.

In summary, this work unifies the study of random walks on branching processes and the spectral theory of sparse random graphs, providing sharp, optimal bounds that were previously out of reach.