Recognition: 2 theorem links
· Lean TheoremEdge-averaging dynamics on finite graphs: moment dependence
Pith reviewed 2026-05-12 00:51 UTC · model grok-4.3
The pith
Initial opinions with L^p norm at most 1 lead to expected ε-convergence time Õ(n to the power max(3-p, 2/p)) in edge averaging.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We assume instead that the L^p norm of f_0(v) is at most 1 for every v ∈ V. For fixed ε ∈ (0,1], we show that E(τ_ε) = Õ(n^{β_p}) up to logarithmic terms, where β_p := max(3-p, 2/p). Moreover, this power law is tight on cycle graphs.
What carries the argument
The ε-convergence time τ_ε, the first time max f_t minus min f_t drops to ε, whose expectation is bounded using the L^p assumption on the initial i.i.d. opinions.
If this is right
- For any fixed p the scaling is polynomial in n, in contrast to the logarithmic bound under L^∞ assumptions.
- The exponent β_p equals 3-p when p ≤ 2 and equals 2/p when p ≥ 3.
- The upper bound is achieved on cycle graphs, so the power cannot be improved for general graphs without stronger assumptions.
- As p tends to infinity the exponent tends to zero, recovering the logarithmic regime in the limit.
Where Pith is reading between the lines
- The same moment-dependent scaling may govern convergence in other linear averaging or gossip algorithms on graphs.
- On graphs with smaller diameter than cycles the actual exponent could be strictly smaller than max(3-p, 2/p).
- Relaxing the i.i.d. assumption to weak dependence is unlikely to change the leading power.
Load-bearing premise
The initial opinions are i.i.d. with each vertex opinion having L^p norm at most 1, and the graph is finite and connected.
What would settle it
Simulate the edge-averaging process on cycle graphs of increasing size with i.i.d. initial opinions of unit p-norm and verify whether the observed growth of expected convergence time matches n to the power max(3-p, 2/p).
read the original abstract
We study the edge-averaging process on a finite, connected graph $G = (V, E)$. Initially, the vertices in $V$ are endowed with i.i.d.\ real-valued opinions $(f_0(v))_{v \in V}$. Edges are activated according to i.i.d.\ Poisson clocks of rate $1$; when an edge is activated, the opinions at its endpoints are replaced by their average. Let $f_t(v)$ denote the opinion at $v$ at time $t$.Define the $\epsilon$-convergence time $\tau_\epsilon$ as the first time when the maximum and the minimum of $f_t$ differ by at most $\epsilon$. It is known that if the initial opinions $(f_0(v))_{v \in V}$ are bounded in $L^\infty$, then $\mathbb{E}(\tau_\epsilon)$ is at most $C_\epsilon \log^2 n$ for $\epsilon \in (0, 1]$. We assume instead that the $L^p$ norm of $f_0(v)$ is at most $1$ for every $v \in V$. For fixed $\epsilon \in (0, 1]$, and show that $\mathbb{E}(\tau_\epsilon) = \widetilde{O}(n^{\beta_p})$ up to logarithmic terms, where $\beta_p := \max(3 - p, 2/p)$. Moreover, this power law is tight on cycle graphs.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript analyzes the edge-averaging process on a finite connected graph with i.i.d. initial opinions satisfying ||f_0(v)||_p ≤ 1 for all v. It establishes that the expected ε-convergence time satisfies E(τ_ε) = Õ(n^{β_p}) with β_p := max(3-p, 2/p), and proves that this power is tight on cycle graphs. This extends the known polylogarithmic bound that holds under L^∞ bounded initial opinions.
Significance. If the claimed bounds hold, the work gives a sharp characterization of how the moment parameter p governs the convergence time of averaging dynamics, with the matching lower bound on cycles providing a concrete optimality result. The combination of moment bounds, tail estimates, and graph mixing times is a standard and effective approach in this area.
minor comments (3)
- Abstract: the sentence beginning 'For fixed ε ∈ (0,1], and show that' is grammatically incomplete and should be rephrased for clarity.
- The notation Õ is used without explicit definition; a brief clarification of the logarithmic factors absorbed would aid readability.
- The assumption that the graph is finite and connected is stated but could be emphasized earlier when defining the process and τ_ε.
Simulated Author's Rebuttal
We thank the referee for the positive assessment of our manuscript and the recommendation for minor revision. We appreciate the recognition that the combination of moment bounds and graph mixing yields a sharp characterization of convergence time.
Circularity Check
No significant circularity; derivation self-contained
full rationale
The paper derives upper and lower bounds on E(τ_ε) for the edge-averaging process under the assumption that initial opinions are i.i.d. with ||f_0(v)||_p ≤ 1. The upper bound is obtained from moment bounds on the process, tail estimates from the L^p assumption, and graph mixing times, while the matching lower bound on cycles follows from balancing rare large initial values against diffusion timescales. No load-bearing step reduces by construction to a fitted parameter, self-referential definition, or self-citation chain; the argument relies on standard stochastic process analysis and is independent of the target result.
Axiom & Free-Parameter Ledger
axioms (3)
- domain assumption The graph G is finite and connected.
- domain assumption Initial opinions f_0(v) are i.i.d. with ||f_0(v)||_p ≤ 1.
- standard math Edges are activated by independent rate-1 Poisson clocks.
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclearWe assume instead that the L^p norm of f_0(v) is at most 1 for every v ∈ V. ... E(τ_ε) = Õ(n^{β_p}) ... β_p := max(3-p, 2/p). Moreover, this power law is tight on cycle graphs.
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclearTheorem 2.4 ... P(Q_t ≥ 6 t^{-1/2}_*) ≤ exp(-t_*/30) ... fragmentation process
Reference graph
Works this paper leans on
-
[1]
A lecture on the averaging process.Probab
David Aldous and Daniel Lanoue. A lecture on the averaging process.Probab. Surv., 9:90–102, 2012
work page 2012
-
[2]
Gideon Amir, Fedor Nazarov, and Yuval Peres. Convergence rate ofℓ p-energy minimiza- tion on graphs: sharp polynomial bounds and a phase transition atp= 3. arXiv Preprint, arXiv:2508.19411, 2025
-
[3]
Randomized gossip algo- rithms.IEEE transactions on information theory, 52(6):2508–2530, 2006
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algo- rithms.IEEE transactions on information theory, 52(6):2508–2530, 2006. 18
work page 2006
-
[4]
arXiv Preprint, arXiv:2603.00705, 2026
Pietro Caputo, Matteo Quattropani, and Federico Sau.L 2-cutoff for the averaging process on random regular graphs. arXiv Preprint, arXiv:2603.00705, 2026
-
[5]
A phase transition for repeated averages.Ann
Sourav Chatterjee, Persi Diaconis, Allan Sly, and Lingfu Zhang. A phase transition for repeated averages.Ann. Probab., 50(1):1–17, 2022
work page 2022
-
[6]
Reaching a consensus.Journal of the American Statistical association, 69(345):118–121, 1974
Morris H DeGroot. Reaching a consensus.Journal of the American Statistical association, 69(345):118–121, 1974
work page 1974
-
[7]
The asynchronous DeGroot dynamics.Random Structures Algorithms, 65(4):857–895, 2024
Dor Elboim, Yuval Peres, and Ron Peretz. The asynchronous DeGroot dynamics.Random Structures Algorithms, 65(4):857–895, 2024
work page 2024
-
[8]
Dor Elboim, Yuval Peres, and Ron Peretz. The edge-averaging process on graphs with random initial opinions.Proceedings of the National Academy of Sciences, 122(33):e2423947122, 2025
work page 2025
-
[9]
The averaging process on infinite graphs.ALEA, Lat
Nina Gantert and Timo Vilkas. The averaging process on infinite graphs.ALEA, Lat. Am. J. Probab. Math. Stat., 22(1):815–823, 2025
work page 2025
-
[10]
J. Pascal Gollin, Kevin Hendrey, Hao Huang, Tony Huynh, Bojan Mohar, Sang-il Oum, Ningyuan Yang, Wei-Hsuan Yu, and Xuding Zhu. Sharing tea on a graph. arXiv Preprint, arXiv:2405.15353, 2025
-
[11]
Properties, emergence, and estimation, volume 53 ofCamb
Jayakrishnan Nair, Adam Wierman, and Bert Zwart.The fundamentals of heavy tails. Properties, emergence, and estimation, volume 53 ofCamb. Ser. Stat. Probab. Math.Cambridge University Press, 2022. 19
work page 2022
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.