Repeated averages on graphs (Q6616875)

An averaging process is defined on an undirected connected finite graph using random choices of edges to replace a state vector \(v(t)\) of weights on the nodes with an updated state vector \(v(t+1)\) in such a way that the sum of the coordinates of \(v\) is invariant. The main results here are concerned with the speed of convergence to the vector \(\tilde{v}\) with all coordinates equal, and this is expressed in terms of an `\(\epsilon\)-mixing time'. The first result gives lower bounds that (in conjuction with other known results in the literature) show in particular that the complete graph asymptotically mixes fastest in the \(L^1\) metric among all graphs. Further results describe lend support to conjectured more precise estimates for the mixing time. The paper includes a discussion of the multiple motivations for studying this kind of averaging procedure and a review of the existing literature.