Repeated averaging on random d-regular graphs
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Repeated averaging on random d-regular graphs".
Title and authors: Ada: So we're looking at this paper, "Repeated averaging on random d-regular graphs," by Dong Yao and Lingfu Zhang. It sounds like they’re taking something simple—repeatedly averaging numbers on a graph—and seeing how that relates to bigger ideas like consensus formation or how information spreads through a network.
Emmy: Exactly. The title itself points to the core idea: repeated averaging on random d-regular graphs. When we talk about random regular graphs, we're usually thinking about highly connected networks, which is what many real-world systems, like social media or communication lines, often resemble.
Ada: But the authors are tackling a question that’s been around since the 80s—the L1 cutoff question for repeated averaging on general graphs <ref:2609.25729#pg1>. They’re trying to figure out if this process ever truly settles down into a steady state where the differences between all the numbers eventually become very small in an average sense.
Emmy: And what they do is establish a criterion based on size-biased sampling and build a whole framework specifically for sparse expanders, which are these particular types of graphs that have good mixing properties. They’re showing that for any degree d greater than or equal to three, they can prove an L1 cutoff with a Gaussian profile across all starting vertices.
Ada: That Gaussian profile is pretty interesting because it suggests a very specific kind of decay in how fast things converge, and the fact that it works uniformly over all starting vertices is something they're pushing for. It’s not just about one specific spot on the graph; it holds true everywhere.
Kolya: From a probabilistic standpoint, what this means is they are setting a very high bar for convergence in these complex systems. They're showing that even in these random structures, you get a predictable way the variance shrinks over time. I wonder if those constants they derive are strong enough to apply to really messy, real-world data where the graph isn't perfectly random.
Ada: That’s a good question about robustness. The paper seems focused on establishing that this cutoff happens predictably, and it sets up the next part of the argument by showing *when* it happens relative to other processes.
Emmy: Right, because establishing the cutoff itself is just half the battle; knowing how long it takes is what really unlocks the structural understanding of these systems. This paper lays out that connection between different types of random processes on these graphs.
The paper's summary: Ada: To summarize what they’ve done, this research tackles three main questions: first, does repeated averaging exhibit an L1 cutoff at all? second, if it does, what is the exact time when this cutoff occurs? and third, if it happens, what is the size of that window and what shape does its profile take?
Emmy: They’re showing that for sparse expanders like random d-regular graphs with degree d bigger than or equal to three, the answer to the first question is yes—it exhibits L1 cutoff. More specifically, they prove it happens with a Gaussian profile across all starting vertices.
Ada: The really deep part is their prediction for the second and third questions. They show that this cutoff time coincides exactly with what we call the entropic time of a typical quenched mass on the infinite d-regular tree, and that window size has a square root of the mixing time, along with that Gaussian shape.
Emmy: And they don't just stop there; they prove something about how this compares to other processes. The cutoff time they find is strictly larger than both the random walk cutoff time and any universal lower bound found on complete graphs, which reveals an unexpected entropy gap in the system’s behavior.
Ada: An entropy gap sounds like a significant finding because it suggests that repeated averaging takes longer to settle down than we might expect based on simpler models. Kolya, what does that imply about the dynamics?
Kolya: It implies that the mixing rate of this process is slower than what a standard random walk would predict for convergence. If you were modeling information flow, this paper suggests that the system retains more structure or memory for longer before it fully homogenizes across all vertices. The fact they compare it to random walks is key because random walks are often simpler to analyze probabilistically.
Emmy: Exactly. When they compare the repeated averaging profile X t with the random walk profile W t, Proposition four point one shows a logarithmic correlation between them, which hints at some underlying fractal behavior in how these two processes evolve together on the infinite d-regular tree.
The paper's improvements: Ada: Now let’s talk about what they suggest as further developments or refinements to this framework. The authors are developing a general criterion for L1 decay by analyzing the size-biased mass using coupled walks and spectral gap assumptions, which converts threshold estimates for size-biased weights into an L1 cutoff via Proposition three point two <ref:2609.25729#pg1>.
Emmy: This sounds like they are building a more versatile tool. They aren't just proving it for one type of graph anymore; they’re creating a method that can be applied to any sparse expander, provided you satisfy those size-biased mass conditions and have good spectral gaps in the underlying structure.
Ada: So, it moves from being a specific result on random d-regular graphs to a more general methodology for analyzing these types of convergence problems across different graph families. It’s about finding the necessary and sufficient conditions for this L1 cutoff behavior.
Kolya: I’m interested in how they handle those size-biased mass estimates. In probabilistic terms, what does that mean for the tails of the distribution? Are we talking about light tails or something heavier because of that sampling method?
Emmy: They are using coupled walks to analyze this, which is a powerful technique for looking at correlations between different stochastic processes. It allows them to rigorously establish bounds on how close these two types of averages can get, which is crucial for understanding the convergence window size.
Ada: And they’re also exploring the behavior as d gets very large. They show that the lower bound for kappa star, which governs this decay rate, approaches log(two) as the degree d goes to infinity, which they connect back to analyzing zero-weight vertices over time intervals <ref:2609.25729#pg2>.
Conclusion: Ada: So, to wrap up this paper on "Repeated averaging on random d-regular graphs," we established that L1 cutoff with a Gaussian profile exists for any degree d greater than or equal to three, uniformly over all starting vertices. This happens at an entropic time related to the infinite tree, and it beats the random walk cutoff time and lower bounds from complete graphs.
Emmy: The implication here is that for these sparse expanders, we have a very precise picture of how information settles down in a network—it converges predictably, not just vaguely. It provides a solid structural foundation for understanding consensus or information spreading dynamics on these large networks.
Kolya: I think the entropy gap they found is the most important part to emphasize. It tells us that convergence isn't as fast as we might assume from simpler models, and that this slower rate is tied directly to the specific geometry of the underlying graph structure itself.
Ada: Absolutely. And Kolya, just one final thing on your side: what’s the immediate next step for you in applying these kinds of bounds to more complex systems?
Kolya: I think checking if those constants survive when you move from random graphs to slightly less random but still well-behaved structures is where the real challenge lies. You need to know if those theoretical bounds hold up under real-world noise.
Emmy: And for me, the structural insight is that they’ve successfully mapped a complex averaging process onto a known geometric object—the infinite tree—which gives us a template to study other related dynamics.
Ada: Well, this work on "Repeated averaging on random d-regular graphs" really solidifies the tools we have for analyzing convergence in these settings. Thanks for joining us.
Dong Yao, Lingfu Zhang
School of Mathematics and Statistics/RIMS, Jiangsu Normal University · Caltech
math.PR
Submitted: 2026-09-22
Updated: 2026-11-18
Comments: 53 pages. v2: title changed; removed discussion of companion papers due to a change of plans; main results unchanged
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 99/100
The gist: Repeated averaging on graphs is presented as a natural prototype for local stochastic exchange, which models phenomena such as consensus formation, information spreading, and wealth redistribution.
Key concepts
- Size-biased sampling
- This technique involves sampling nodes in a graph based on their degree rather than uniformly. It helps analyze phenomena like wealth redistribution or consensus by focusing the analysis on more influential nodes, which is crucial for establishing the $L_1$ cutoff criterion.
- $L_1$ cutoff with Gaussian profile
- This result shows that after a certain time, the average value of repeated averaging converges to a specific threshold ($1/n$) with an error bounded by a Gaussian distribution. This provides a precise characterization of how quickly information spreads or consensus forms.
- Entropic time
- This is the specific time at which the cutoff occurs, determined by the statistical properties of a typical mass on an infinite $d$-regular tree. It serves as a universal benchmark for when repeated averaging stabilizes, linking graph dynamics to simpler tree structures.
- Entropy gap
- This refers to the finding that the cutoff time for repeated averaging is strictly larger than both random walk cutoff times and universal lower bounds on complete graphs. This gap indicates a fundamental difference in how these processes evolve on different graph structures.
Terminology
Summary
Repeated averaging on graphs is presented as a natural prototype for local stochastic exchange, which models phenomena such as consensus formation, information spreading, and wealth redistribution. p. 0 The research establishes a criterion based on size-biased sampling and develops a general framework specifically for sparse expanders. p. 0 A key result demonstrated is the proof of an L 1 cutoff with a Gaussian profile on random d-regular graphs for any degree d at least 3, uniformly across all starting vertices. p. 0 The cutoff time is shown to coincide with the entropic time of a typical quenched mass on the infinite d-regular tree, and the corresponding cutoff window exhibits a square-root window size accompanied by a Gaussian profile. p. 2 Crucially, the authors prove that this cutoff time is strictly greater than both the random walk cutoff time and any universal lower bound attained on complete graphs, thereby revealing an unexpected entropy gap. p. 0
The theoretical framework employed in this work incorporates concepts from polymer representations, random geometry, universal-cover lifting, and adaptive revealing techniques. p. 0 The primary result for random d-regular graphs is formalized in Theorem 1. p. 51: For a fixed d at least 3, as the number of vertices n to infinity through integers where nd is even, if G n = (V n, E n) is a uniformly random simple connected d-regular graph on n vertices, and we consider the vector of numbers at time t, denoted as X(n,v) t, starting from an initial condition where X(n,v) 0(u) = 1[u=v], then there exist constants kappa* and sigma > 0, dependent only on d, such that for any a in R and epsilon > 0, the probability that the maximum value of X(n,v) tau n(a) - 1/n exceeds 2 phi(-a) is greater than epsilon. p. 2
Furthermore, Proposition 4. p. 21 establishes the strict inequality kappa* < kappa RW on the infinite d-regular tree T d, which implies a logarithmic correlation between the profile of repeated averaging, X t, and that of a random walk, W t, thereby revealing fractal behavior in the profile. p. 5 The central limit theorem for - X t(W t) is proven in Theorem 5. p. 55: as t to infinity, - X t(W t) - kappa* t sqrt t converges in distribution to a normal distribution N(0, sigma 2), where sigma squared is shown to be strictly positive in Proposition 6. p. 56. The comparison between the repeated averaging process on a large finite simple d-regular graph and the infinite d-regular tree is detailed in Section 7, showing that for any delta-good graph G n with a root, and time t satisfying condition (69), the probability bound P X* t(pi) e at most X* t(pi n) at most 2X* t(pi) + e C delta-2 ((n)) 4/n at least 1 - C delta - o(1) is established. p. 5 The lower bound for kappa* in regular graphs is shown to be 0 < kappa* < (2), derived from (5) of Theorem 1. p. 23, and its convergence to (2) as d to infinity is demonstrated in Section 9. p. 12, where the inequality 0 < kappa* < kappa RW is reiterated as a consequence of Proposition 4. p. 21 and (5) of Theorem 1. p. 13.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
System can rigorously establish L1 cutoff for repeated averaging on general sparse expanders by developing a framework based on size-biased sampling and polymer representations. This allows for proving L1 cutoff with a Gaussian profile uniformly over starting vertices for any d greater than or equal to 3.
-
The system can predict the exact time of L1 cutoff, showing it occurs at the entropic time of a typical quenched mass on the infinite d-regular tree, and quantify how this time relates to random walk cutoff times and universal lower bounds.
-
The system can provide a general criterion for L1 decay by analyzing the size-biased mass using coupled walks and spectral gap assumptions, converting threshold estimates for size-biased weights into L1 cutoff via Proposition 3.2.
-
The system can rigorously prove that the cutoff time is strictly larger than the random walk cutoff time by showing that
the quenched mass has a decay rate strictly smaller than the random walk transition probability decay rate.
-
The system can characterize the Gaussian profile of the L1 distance by establishing a central limit theorem for - log X t(W t) on the infinite d-regular tree, yielding a limiting distribution N(0, sigma squared).
-
The system can prove that for random d-regular graphs, there exists a coupling of two walks (one from the finite graph and one from its universal cover) such that the ratio of their weights is bounded by constants related to delta and log n.
-
The system can verify the conditions for a random d-regular graph to be delta good with high probability, including uniform spectral gap and logarithmic random walk transition probability decay, which are essential for applying the main cutoff result.
-
The system can establish that the lower bound of kappa star on regular graphs approaches log(2) as the degree d goes to infinity by analyzing the renewal structure of zero-weight vertices in time intervals.
Sources
- Convergence of the KMP model to the KPZ equation
- Repeated Block Averages: entropic time and mixing profiles
- A universal cutoff phenomenon for mean-field exchange models
- $L^2$-cutoff for the averaging process on random regular graphs
- The critical KPZ scale for the Averaging Process
- Concentration and central limit theorem for the averaging process on $\mathbb{Z}^{d}$
- A central limit theorem for m-dependent variables
- Total variation cutoff for Kac's walk on the sphere
- The local product condition implies cutoff
- Edge-averaging dynamics on finite graphs: moment dependence
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves
- A zero-one law for swap-invariant events in uniform spanning forests