Anchored expansion, speed, and the hyperbolic Poisson Voronoi tessellation

Itaï Benjamini, Elliot Paquette, Joshua PfefferarXiv 2014 · DOI · arXiv

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.

A visualization of a hyperbolic Poisson tessellation within the Poincaré disk model, illustrating the complex 1-skeleton analyzed in the paper.

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.

Comparison of hyperbolic tessellations at different intensities: (A) $\lambda = 0.2$ and (B) $\lambda = 1$. The authors conjecture that as $\lambda$ increases, the speed of the random walk decreases.

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

Abstract

We show that 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 speed. We include a section of open problems and conjectures on the topics of stationary geometric random graphs and the hyperbolic Poisson Voronoi tessellation.
BibTeX
@misc{benjamini2014anchored,
  author = {Itaï Benjamini and Elliot Paquette and Joshua Pfeffer},
  title = {{Anchored expansion, speed, and the hyperbolic Poisson Voronoi tessellation}},
  year = {2014},
  eprint = {1409.4312},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1409.4312},
}
Figure