Edge-averaging dynamics on finite graphs: moment dependence

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 $\hat{I}\mu$-convergence time $\ddot{I}{„}_{\hat{I}}\mu$ as the first time when the maximum and the minimum of $f_t$ differ by at most $\hat{I}\mu$. It is known that if the initial opinions $(f_0(v){)}_{v\in V}$ are bounded in $L^{\infty }$, then $\mathbb{E}(\ddot{I}{„}_{\hat{I}}\mu )$ is at most $C_{\hat{I}}\mu {\log }^{2}n$ for $\hat{I}\mu \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 $\hat{I}\mu \in (0,1]$, and show that $\mathbb{E}(\ddot{I}{„}_{\hat{I}}\mu )=\tilde{O}(n^{{\hat{I}}_p^2})$ up to logarithmic terms, where ${\hat{I}}_p^2:=\max (3-p,2/p)$. Moreover, this power law is tight on cycle graphs.

19 pages