Repeated averaging on expanders I: random d-regular graph
Abstract
Repeated averaging on graphs is a natural prototype of local stochastic exchange, modeling consensus formation, information spreading, and wealth redistribution. Its convergence has attracted longstanding interest, from Bourgain's complete-graph L1 cutoff question in the 80s (answered in recent years by Chatterjee, Diaconis, Sly, and Zhang) and the systematic study of Aldous and Lanoue. Addressing the still outstanding and widely asked L1-cutoff question on general graphs, we establish a criterion based on size-biased sampling, and develop a general framework for sparse expanders. Specifically, we prove L1 cutoff with a Gaussian profile on random d-regular graphs, for any d≥ 3 and uniformly over starting vertices. Remarkably, although the expected mass profile agrees exactly with the corresponding random-walk distribution, cutoff occurs strictly later than both the random walk cutoff time and the universal lower bound attained on complete graphs, revealing an unexpected entropy gap. The framework is robust, involving ideas of polymer representations, random geometry, universal-cover lifting, and adaptive revealing. Our companion work will extend it to Ramanujan graphs and bounded-degree configuration models.
Related
- Small circumference in regular sublinear expanders
- New tools for sparse graph embeddings: Hybrid expanders and application to nested cycles
- Blind Random Search with Noisy Loss Measurements: Averaging, Thresholding, and Almost Sure Convergence
- Growing-time trace fluctuations and self-averaging form factors of Grover walks on random lifts
- Edge universality of random regular graphs of growing degrees
BibTeX
@misc{yao2026repeated,
title = {{Repeated averaging on expanders I: random $d$-regular graph}},
author = {Dong Yao and Lingfu Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25729},
eprint = {2609.25729},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25729},
}
RIS
TY - UNPB
TI - Repeated averaging on expanders I: random d-regular graph
AU - Dong Yao
AU - Lingfu Zhang
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.25729
UR - https://arxiv.org/abs/2609.25729
AB - Repeated averaging on graphs is a natural prototype of local stochastic exchange, modeling consensus formation, information spreading, and wealth redistribution. Its convergence has attracted longstanding interest, from Bourgain's complete-graph L^1 cutoff question in the 80s (answered in recent years by Chatterjee, Diaconis, Sly, and Zhang) and the systematic study of Aldous and Lanoue. Addressing the still outstanding and widely asked L^1-cutoff question on general graphs, we establish a criterion based on size-biased sampling, and develop a general framework for sparse expanders. Specifically, we prove L^1 cutoff with a Gaussian profile on random d-regular graphs, for any d≥ 3 and uniformly over starting vertices. Remarkably, although the expected mass profile agrees exactly with the corresponding random-walk distribution, cutoff occurs strictly later than both the random walk cutoff time and the universal lower bound attained on complete graphs, revealing an unexpected entropy gap. The framework is robust, involving ideas of polymer representations, random geometry, universal-cover lifting, and adaptive revealing. Our companion work will extend it to Ramanujan graphs and bounded-degree configuration models.
ER -