$L^2$-cutoff for the averaging process on random regular graphs

Abstract

We study the mixing time of the averaging process on a large random $d$-regular graph, $d\ge 3$, and prove an $L^2$-cutoff with an explicit cutoff time. Somewhat surprisingly, we uncover a phase transition at the finite, fixed degree $d=10$: for small degrees, i.e., $d\le 10$, the averaging process mixes as fast as the corresponding random walk on the same graph, whereas for $d>10$ its $L^2$-mixing is governed by a different, slower mechanism. Our proof relies on a detailed asymptotic analysis of an auxiliary biased birth-and-death chain with a slow bond. We also briefly discuss an analogous phase transition for the $L^1$-mixing.

16 pages, 3 figures