Abstract: This paper investigates the behavior of random walks on stationary random graphs, specifically focusing on the speed of movement in hyperbolic spaces. The authors prove that positive anchored expansion combined with exponential volume growth ensures positive speed for random walks, even in graphs with unbounded degrees. These results are applied to the hyperbolic Poisson Voronoi (HPV) and Delaunay triangulations, confirming that random walks on these structures converge to the hyperbolic boundary with a linear rate of escape.
Introduction
In the study of stochastic processes on graphs, "speed" (or drift) measures the rate at which a random walker moves away from its starting point. A central question is identifying which geometric properties guarantee positive speed, where the distance from the origin grows linearly with time.
Previous research established that "anchored expansion"—a property where every finite set of vertices containing the origin has a boundary proportional to its volume—implies positive speed for graphs with a bounded maximum degree. However, many important random graph models, such as those derived from Poisson point processes, naturally feature vertices with arbitrarily high degrees. This paper bridges that gap by replacing the bounded degree requirement with two conditions: stationarity and exponential volume growth.
Theoretical Framework: Stationarity and Expansion
The authors utilize ergodic theory and discrete potential theory to handle the challenges of unbounded degrees. By leveraging the stationarity of the random graph (the property that the graph's statistical structure remains invariant from the walker's perspective), they demonstrate that a random walk spends sufficient time in regions of high expansion.
Key theoretical results include:
- Theorem 1.1: Any stationary random graph with positive anchored expansion and exponential growth supports a simple random walk with a limit speed $s > 0$ almost surely.
- Harmonic Function Dichotomy: The paper establishes that stationary graphs either possess only constant bounded harmonic functions (the Liouville property) or an infinite-dimensional space of such functions, with no intermediate state.
Hyperbolic Poisson Tessellations
The core application of this theory is the Hyperbolic Poisson Voronoi (HPV) tessellation. In this model, the hyperbolic plane $\mathbb{H}$ is partitioned into cells based on the proximity to points generated by a Poisson process. The negative curvature of hyperbolic space inherently promotes expansion, and the authors prove that this geometric expansion is robust enough to survive the randomness of the Poisson process.
By comparing the hyperbolic area of connected triangle collections to their vertex count, the authors show that the 1-skeletons of HPV and Delaunay triangulations possess positive anchored expansion (Theorem 1.4). Consequently, random walks on these graphs are transient and converge almost surely to a point on the ideal boundary of the hyperbolic plane.
Conjectures and Future Directions
While the existence of positive speed is proven, several open questions remain regarding its specific behavior. One primary conjecture involves the intensity parameter $\lambda$ of the underlying Poisson process.
As $\lambda$ increases, the graph becomes denser and more "Euclidean-like" at small scales. The authors conjecture that the speed $s(\lambda)$ is a strictly decreasing function of $\lambda$. Other future work includes extending these results to $d$-dimensional hyperbolic spaces and determining whether the resulting harmonic measure on the boundary is absolutely continuous or singular with respect to the Lebesgue measure.
Summary updated