Seminar: The Averaging Process on Finite Graphs

Consider the following discrete-time random process run on a finite, connected graph $G$: beginning with a unit mass placed on some vertex in $G$, at each step we independently choose an edge $vw$ of $G$ uniformly at random, and replace the masses on both $v$ and $w$ with $(mass(v) + mass(w)) / 2$, leaving all other vertex masses unchanged. After many steps of the process, the mass will be nearly uniformly distributed across the vertices of $G$ (with reasonably high probability). It is conventional in this setting to measure distance between distributions with the $L^1$ norm, and we think of the decay of the $L^1$ distance of the mass distribution to uniform as the mixing of the process, in analogy with the study of finite Markov chains.

In this talk, we'll survey some recent work on the asymptotic mixing of the averaging process on a variety of families of graphs, starting with a very precise result of Chatterjee, Diaconis, Sly, and Zhang from 2018 pertaining to the complete graph $K_n$. We'll also list some cases which remain open or for which only partial results are known, and save some time at the end for discussion.