Mixing of the Averaging process on graphs
The Averaging process (a.k.a. repeated averages) is a mass redistribution model over the vertex set of a graph. Given a graph G, the process starts with a non-negative mass associated to each vertex. The edges of G are equipped with Poissonian clocks: when an edge rings, the masses at the two extremes of the edge are equally redistributed on these two vertices. Clearly, as time grows to infinity, the state of the system will converge (in some sense) to a flat configuration in which all the vertices have the same mass. This very simple process has been introduced to the probabilistic community by Aldous and Lanoue in 2012. However, up to few years ago, there was no graph for which sharp quantitative results on the time needed to reach equilibrium were available. Indeed, the analysis of this process requires different tools compared to the classical Markov chain framework, and even in the case of seemingly straightforward geometries—such as the complete graph or the 1-d torus—it can be handled only by means of non trivial probabilistic and functional analytic techniques. Based on joint work with P. Caputo (Roma Tre) and F. Sau (Università di Trieste)
Area: IS18 - Mixing times (Federico Sau)
Keywords: Random walks, cutoff phenomenon, redistribution models
Please Login in order to download this file