Anchored expansion, speed and the Poisson–Voronoi tessellation in symmetric spaces

Itaï Benjamini, Elliot Paquette, Joshua PfefferThe Annals of Probability 2018 · DOI

Abstract

We show that a random walk on a stationary random graph with positive anchored expansion and exponential volume growth has positive speed. We also show that two families of random triangulations of the hyperbolic plane, the hyperbolic Poisson–Voronoi tessellation and the hyperbolic Poisson–Delaunay triangulation, have $1$-skeletons with positive anchored expansion. As a consequence, we show that the simple random walks on these graphs have positive hyperbolic speed. Finally, we include a section of open problems and conjectures on the topics of stationary geometric random graphs and the hyperbolic Poisson–Voronoi tessellation.

Introduction

In the study of stochastic processes on graphs, a fundamental question is the behavior of a simple random walk over time. Specifically, researchers are interested in the "speed" of the walker—the rate at which it moves away from its starting position. While walkers on Euclidean lattices like a simple grid tend to linger near their origin (zero speed), graphs with "expansion" properties often push walkers outward at a linear rate (positive speed).

Historically, proving positive speed required the graph to have a bounded degree—a maximum limit on the number of edges connected to any single vertex. However, many natural models of random graphs, particularly those arising in hyperbolic geometry, do not satisfy this constraint. This paper bridges that gap by establishing a link between the geometric property of "anchored expansion" and positive speed for a broader class of stationary random graphs.

Theoretical Framework: Trading Bounded Degree for Stationarity

The core theoretical contribution of this work is Theorem 1.1, which provides a new criterion for positive speed. The authors demonstrate that the restrictive bounded degree assumption can be replaced by the assumption of stationarity. A random graph is stationary if its statistical properties remain invariant as one moves along the path of a random walk.

By combining stationarity with exponential volume growth and positive anchored expansion, the authors prove that the limit $s = \lim_{k \to \infty} d(\rho, X_k)/k$ exists and is strictly greater than zero. This implies that the walker escapes "traps" or dense local clusters and eventually moves into the expansive regions of the graph.

Furthermore, the paper establishes a "zero-infinity" law for harmonic functions (Theorem 1.2). It proves that a stationary random graph either possesses only trivial (constant) bounded harmonic functions or an infinite-dimensional space of them, with no intermediate state possible.

Stochastic Geometry in the Hyperbolic Plane

The general theory is applied to two significant models in stochastic geometry: the hyperbolic Poisson–Voronoi tessellation and the hyperbolic Poisson–Delaunay triangulation. These structures are formed by partitioning the hyperbolic plane ($\mathbb{H}$) based on a Poisson point process.

Hyperbolic Poisson–Voronoi tessellations with different intensity parameters $\lambda$. (A) $\lambda = 0.2$ and $r = 0.9995$; (B) $\lambda = 1$ and $r = 0.9975$.

The authors prove that the 1-skeletons (the networks of edges) of these tessellations exhibit positive anchored expansion almost surely (Theorem 1.4). This proof requires delicate geometric estimates to ensure that the random cells do not become excessively small or thin, which would compromise the expansion properties. A key result of this expansion is that random walks on these hyperbolic graphs not only have positive speed but also converge to a specific point on the "ideal boundary" (the circle at infinity) of the hyperbolic plane.

Future Directions and Conjectures

The paper concludes by identifying several open problems that remain at the frontier of this field:

  • Higher-Dimensional Generalization: While the current proof for Poisson–Voronoi expansion is specific to the 2D hyperbolic plane, the authors conjecture that these properties hold in $d$-dimensional hyperbolic space $\mathbb{H}^d$.
  • Determinism of Speed: Although the speed $s(\lambda)$ is proven to be positive, it remains to be formally established as a deterministic constant, though this is strongly suspected.
  • Singularity of the Exit Measure: The authors hypothesize that the "exit measure"—the probability distribution of the walk's hitting point on the boundary—is singular with respect to the standard Lebesgue measure. This suggests that the random walk may favor certain fractal-like subsets of the boundary.

This work provides a robust mathematical foundation for understanding how geometric expansion dictates the long-term dynamics of random processes in non-Euclidean spaces.

Summary updated

Abstract

We show that a random walk on a stationary random graph with positive anchored expansion and exponential volume growth has positive speed. We also show that two families of random triangulations of the hyperbolic plane, the hyperbolic Poisson–Voronoi tessellation and the hyperbolic Poisson–Delaunay triangulation, have $1$-skeletons with positive anchored expansion. As a consequence, we show that the simple random walks on these graphs have positive hyperbolic speed. Finally, we include a section of open problems and conjectures on the topics of stationary geometric random graphs and the hyperbolic Poisson–Voronoi tessellation.
BibTeX
@article{benjamini2018anchored,
  author = {Itaï Benjamini and Elliot Paquette and Joshua Pfeffer},
  title = {{Anchored expansion, speed and the Poisson–Voronoi tessellation in symmetric spaces}},
  journal = {The Annals of Probability},
  year = {2018},
  doi = {10.1214/17-aop1216},
}
Figure