🔢 mathematics

Random walk on sphere packings and Delaunay triangulations in arbitrary dimension

This paper establishes that random walks on a broad class of deterministic tilings in arbitrary dimensions, including Delaunay triangulations and sphere packings, converge to Brownian motion modulo time parameterization under mild regularity conditions, while also providing quantitative convergence bounds for finite volume schemes and a simplified proof for the two-dimensional case.

Original authors: Ahmed Bou-Rabee, Ewain Gwynne

Published 2026-10-06

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Ahmed Bou-Rabee, Ewain Gwynne

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a vast, empty room filled with a chaotic jumble of objects, from tiny pebbles to large boulders, all packed together until they touch. If you were to drop a marble into this pile and let it bounce from one object to the next, its path would be a frantic, unpredictable zigzag. In the world of physics and mathematics, this kind of random movement is a fundamental concept known as a random walk. For centuries, scientists have understood that if you zoom out far enough, this chaotic bouncing smooths out into a predictable, flowing motion called Brownian motion, which is the same jittery drift seen in pollen grains floating in water. This transition from disorder to order is a cornerstone of how we understand diffusion, heat, and the behavior of particles in nature. However, this smooth transition is well-understood only when the objects in the room are arranged in a regular, grid-like pattern. When the objects are scattered randomly, or when the space itself is warped and uneven, the rules change. The question of whether a random walk still settles into that smooth, flowing motion in these messy, irregular environments has been a stubborn puzzle, particularly in spaces with more than two dimensions.

A team of mathematicians has now solved this puzzle for a broad and important class of irregular arrangements. They proved that even when the "objects" are packed in a highly irregular, random way, a particle moving from one to the next will eventually behave like a standard Brownian motion, provided the particle is allowed to move at a speed that adjusts to the local geometry. Their work covers two major types of irregular structures: sphere packings, where objects are spheres of various sizes touching each other, and Delaunay triangulations, which are networks formed by connecting points in space to create a mesh of triangles or their higher-dimensional equivalents. The researchers showed that if you define the rules for how the particle moves based on the specific shape and size of the gaps between these objects, the particle's path will converge to the smooth, flowing motion of Brownian motion, regardless of how chaotic the underlying structure appears.

The key to their discovery lies in how the particle chooses its next step. In a simple, uniform grid, a particle might just pick a neighbor at random. But in a messy, irregular packing, a simple random choice would lead to a distorted path that never smooths out. Instead, the researchers used a specific set of rules where the likelihood of jumping to a neighbor depends on the size of the contact area between the two objects and the distance between their centers. This "tilted" probability ensures that the particle's movement remains balanced, acting like a mathematical scale that keeps the walk centered. Under these specific rules, the team demonstrated that as the objects in the packing become smaller and more numerous, filling the space more densely, the jagged, discrete path of the particle becomes indistinguishable from the smooth curve of a Brownian motion, once you account for the fact that the particle might speed up or slow down depending on the local density of the packing.

This result is significant because it applies to structures that are far from perfect. The researchers did not require the packing to be uniform or the objects to be the same size. Their proof holds true even for packings that are extremely uneven, such as those generated by random processes that mimic the complex, fractal-like geometries found in theoretical models of quantum gravity. They showed that as long as the packing does not contain infinitely small gaps or infinitely large voids, the random walk will still find its way to the smooth, Brownian limit. This provides a rigorous mathematical foundation for using these irregular networks as models for continuous space, suggesting that the smooth geometry of our universe might emerge from a fundamentally discrete and chaotic microscopic structure.

The team also addressed a critical limitation in previous thinking. They showed that if you ignore the specific geometry and simply let the particle jump to any neighbor with equal probability, the walk does not necessarily converge to Brownian motion, even in very regular-looking arrangements. In fact, they constructed a specific example in three dimensions where a simple, unbiased random walk fails to smooth out, proving that the careful choice of movement rules is essential. This distinction clarifies that the smoothness of the macroscopic world is not just a matter of having many small pieces, but of how those pieces interact. The researchers' work confirms that with the right interaction rules, the chaotic dance of a random walker on a messy, high-dimensional tiling inevitably resolves into the elegant, predictable flow of Brownian motion.

Technical Summary: Random Walk on Sphere Packings and Delaunay Triangulations in Arbitrary Dimension

Problem Statement
This paper investigates the large-scale behavior of random walks on a specific class of graphs embedded in $d$ -dimensional Euclidean space ( $\mathbb{R}^d$ ), termed orthogonal tilings. These graphs include:

Delaunay triangulations (duals of Voronoi tessellations).
Tangency graphs of sphere packings.

The central problem is to determine whether random walks on these discrete structures, equipped with a canonical choice of conductances derived from the geometry of the tiling, converge to Brownian motion (modulo time parameterization) as the mesh size tends to zero.

A critical distinction is made between the simple random walk (unit conductances) and the weighted random walk defined by the paper's specific conductance formula. The authors note that simple random walks on orthogonal tilings do not necessarily converge to Brownian motion, even under strong regularity assumptions. The paper focuses on the weighted walk where transition probabilities are determined by the ratio of the $(d-1)$ -dimensional volume of the shared facet between polytopes to the Euclidean distance between their centers.

Methodology
The authors employ a combination of discrete potential theory, geometric analysis, and probabilistic limit theorems. The core methodology involves:

Discrete PDE and Energy Estimates: The random walk is linked to the discrete Laplacian $\Delta^G_a$ . The authors establish that the Dirichlet energy of the difference between a continuum harmonic function and its discrete harmonic extension is small ( $L^2$ convergence). This relies on finite volume scheme theory (referencing Eymard et al. [2000]).
$L^2$ to $L^\infty$ Iteration: A major technical hurdle is that the operator $\Delta^G_a$ $Δ_{a}^{G}$ is not uniformly elliptic in general (conductances can vary wildly). To overcome this, the authors develop an iterative scheme to upgrade $L^2$ $L^{2}$ bounds to pointwise ( $L^\infty$ $L^{\infty}$ ) bounds.
- They utilize a Poincaré-type inequality to show that the discrete harmonic function is close to the continuum function on a dense set of "columns" (projections of the domain).
- For $d=2$ , the maximum principle and planarity allow this local closeness to imply global closeness immediately.
- For $d \ge 3$ , where planarity arguments fail, they introduce regularity hypotheses to control the "bad" set where the error might be large. They iterate the approximation, showing that the measure of the set where the error is large shrinks geometrically, provided the geometry does not degenerate too severely.
Black Box Theorem: The authors prove a general result (Theorem 4.1) stating that if the discrete Dirichlet problem converges uniformly to the continuum Dirichlet problem, then the associated random walk converges to Brownian motion modulo time parameterization. This separates the analytic difficulty (convergence of harmonic functions) from the probabilistic limit.

Key Contributions and Results

Main Theorem (Theorem A): Under nearly minimal regularity assumptions, the random walk on orthogonal tilings converges to Brownian motion modulo time parameterization. The assumptions required are:
- Planarity ( $d=2$ ): No additional geometric constraints beyond the tiling structure.
- Higher Dimensions ( $d \ge 3$ ): One of three conditions must hold:
  1. Planarity (trivially satisfied if $d=2$ ).
  2. Volume Lower Bound: The volume of the smallest tile is at least $\exp(-o(\epsilon_n^{-1}))$ , where $\epsilon_n$ is the maximum tile diameter.
  3. Geometric Ratio Bound: There exists $\alpha > 0$ such that the diameter of each tile is bounded by a power of the ratio of the edge length to the facet volume.
Dirichlet Problem Convergence (Theorem B): The discrete harmonic extension of a continuum harmonic function converges uniformly to the continuum function. The paper provides quantitative bounds on the rate of convergence for smooth boundary data.
Counterexample (Theorem 6.1): The authors construct a sphere packing in $d \ge 3$ where the simple random walk (unit conductances) fails to converge to Brownian motion. This highlights the necessity of the specific canonical conductances defined in the paper.
Application to Random Geometry: The results apply to Voronoi tessellations generated by point processes with intensity measures satisfying specific bounds, including Gaussian Multiplicative Chaos (GMC) measures. This establishes convergence for discretizations of higher-dimensional analogs of Liouville Quantum Gravity (LQG).

Significance and Claims
The paper positions itself as a foundational step in extending the theory of universality in statistical mechanics and discrete conformal geometry from two dimensions to arbitrary dimensions.

Universality: The work addresses questions raised by Smirnov [2010] regarding the generalization of results on isoradial graphs to higher dimensions and other graph classes. It suggests that sphere packings and Delaunay triangulations serve as discrete analogs of conformally flat Riemannian metrics in higher dimensions.
Numerical Analysis: Theorem B is framed as a uniform convergence statement for a class of finite volume approximation schemes for the Laplace equation. The authors note that prior convergence results for such schemes were limited to $L^2$ , which is insufficient for proving random walk convergence; this paper bridges that gap.
Higher-Dimensional LQG: The results provide evidence that random walks on discretizations of higher-dimensional LQG (via GMC measures) converge to Brownian motion modulo time change, analogous to known results for mated-CRT maps in two dimensions.
Modesty on Necessity: The authors explicitly state that while their regularity assumptions (II and III) are mild and satisfied by most models of interest (including fractal geometries), it is an open question whether these assumptions are strictly necessary for $d \ge 3$ . They do not claim to have proven the necessity of these conditions, only that the results hold under them.

Conclusion
The paper successfully establishes the convergence of weighted random walks on orthogonal tilings to Brownian motion in arbitrary dimensions, provided the tiling geometry does not degenerate too severely. It achieves this by developing a novel iteration technique to handle non-uniform ellipticity and by separating the analytic convergence of harmonic functions from the probabilistic convergence of the walk. The work extends the scope of discrete conformal geometry and universality results to $d \ge 3$ and provides a rigorous framework for analyzing random walks on random geometric structures like sphere packings and GMC-based tessellations.

Technical Summary: Random Walk on Sphere Packings and Delaunay Triangulations in Arbitrary Dimension

More like this