Abstract
Under the assumption that sequences of graphs equipped with resistances, associated measures, walks, and local times converge in a suitable Gromov-Hausdorff topology, we establish asymptotic bounds on the distribution of the $\varepsilon$-blanket times of the random walks in the sequence. The precise nature of these bounds ensures convergence of the $\varepsilon$-blanket times of the random walks if the $\varepsilon$-blanket time of the limiting diffusion is continuous at $\varepsilon$ with probability 1. This result enables us to prove annealed convergence in various examples of critical random graphs, including critical Galton-Watson trees and the Erdős-Rényi random graph in the critical window. We highlight that proving continuity of the $\varepsilon$-blanket time of the limiting diffusion relies on the scale invariance of a finite measure that gives rise to realizations of the limiting compact random metric space, and therefore we expect our results to hold for other examples of random graphs with a similar scale invariance property.
Introduction
In the study of stochastic processes on networks, a fundamental question is how long a random walker takes to explore the entire space. While the "cover time"—the first time every node has been visited at least once—is a common metric, it often fails to capture the depth of exploration. For applications such as decentralized information sharing or PageRank-style algorithms, we require the walker to spend an amount of time at each node proportional to its stationary distribution. This requirement defines the blanket time.
Specifically, the $\varepsilon$-blanket time is the first time the walk has spent at least an $\varepsilon$ fraction of the "expected" time at every single vertex. While blanket times have been studied for fixed graphs, this research addresses the more complex "critical" regime of random graphs. At criticality, these graphs are sparse and fractal-like, existing on the verge of forming a giant component. This paper establishes a rigorous mathematical framework to prove that these blanket times converge to a well-defined limit as the network size approaches infinity.
The Mathematical Challenge
Proving the convergence of blanket times as the number of vertices $n \to \infty$ is mathematically challenging because it requires tracking the "local time" (the time spent at each point) across a sequence of increasingly complex, random metric spaces. Standard geometric convergence tools, like the Gromov-Hausdorff (GH) topology, are insufficient because they only describe the shape of the space, not the dynamics of a walk or the accumulation of time upon it.
To bridge this gap, the author introduces an Extended Gromov-Hausdorff Topology. This framework handles quadruples consisting of:
- The Metric Space (the graph structure),
- The Measure (the importance of each node),
- The Random Walk Path, and
- The Local Time (the footprint of the walk).
By treating local time as an inherent part of the metric space's definition, the author transforms a dynamic problem into a static geometric convergence problem.
Methodology and Scale Invariance
The research employs a combination of stochastic analysis and metric geometry, focusing on "annealed convergence." This approach accounts for both the randomness of the walk and the randomness of the graph structure itself. A key innovation is the use of resistance metrics. By using the "effective resistance" between nodes as a distance metric—rather than standard shortest-path distance—the geometry becomes naturally suited to the behavior of random walks.
A critical insight of the paper is the "Continuity Bridge." The convergence of a global maximum (the blanket time) depends on the continuity of the local time process in the limit. By demonstrating that the limiting diffusion (such as Brownian motion on a fractal) has a scale-invariant measure, the author ensures that the blanket time does not "jump" at specific values of $\varepsilon$. This scale invariance is a property of the Brownian Continuum Random Tree (CRT) and other similar limiting objects.
Key Results and Scaling Laws
The paper provides a general convergence theorem (Theorem 1.1) and applies it to three fundamental random graph models, deriving specific scaling laws:
- Critical Galton-Watson Trees: For trees generated by a critical branching process, the blanket time scales as $n^{3/2}$.
- Erdős-Rényi Graphs ($G(n, p)$): Within the critical window where $p \approx 1/n$, the blanket time scales linearly with $n$.
- Configuration Models: For random graphs with prescribed degree sequences, the blanket time also scales linearly with $n$.
These results represent a significant advancement over previous "tightness" results. While earlier work could only show that blanket times stayed within certain bounds, this paper proves actual weak convergence to a specific distribution.
Conclusion and Future Work
This work suggests that blanket time convergence is a universal property for any sequence of graphs converging to a "nice" limiting metric measure space. However, some open questions remain. The current framework relies on the assumption that the $\varepsilon$-blanket time of the limiting diffusion is continuous with probability one. While this is proven for the CRT, verifying it for more exotic limiting spaces may be more difficult.
Furthermore, while blanket times and cover times are related, establishing the convergence of the rescaled cover time (the limit as $\varepsilon \to 0$) remains a more delicate problem. Future research may also extend these results to "stable trees"—Galton-Watson trees with heavy-tailed offspring distributions—which would further broaden the applicability of this universal scaling framework.
Summary updated