Edge-averaging dynamics on finite graphs: moment dependence
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917479066894336 |
|---|---|
| author | Zuo, Junchi |
| author_facet | Zuo, Junchi |
| contents | 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 $ε$-convergence time $τ_ε$ as the first time when the maximum and the minimum of $f_t$ differ by at most $ε$. It is known that if the initial opinions $(f_0(v))_{v \in V}$ are bounded in $L^\infty$, then $\mathbb{E}(τ_ε)$ is at most $C_ε\log^2 n$ for $ε\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 $ε\in (0, 1]$, and show that $\mathbb{E}(τ_ε) = \widetilde{O}(n^{β_p})$ up to logarithmic terms, where $β_p := \max(3 - p, 2/p)$. Moreover, this power law is tight on cycle graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_08783 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Edge-averaging dynamics on finite graphs: moment dependence Zuo, Junchi Probability 60J10 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 $ε$-convergence time $τ_ε$ as the first time when the maximum and the minimum of $f_t$ differ by at most $ε$. It is known that if the initial opinions $(f_0(v))_{v \in V}$ are bounded in $L^\infty$, then $\mathbb{E}(τ_ε)$ is at most $C_ε\log^2 n$ for $ε\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 $ε\in (0, 1]$, and show that $\mathbb{E}(τ_ε) = \widetilde{O}(n^{β_p})$ up to logarithmic terms, where $β_p := \max(3 - p, 2/p)$. Moreover, this power law is tight on cycle graphs. |
| title | Edge-averaging dynamics on finite graphs: moment dependence |
| topic | Probability 60J10 |
| url | https://arxiv.org/abs/2605.08783 |