A counterexample to a mixing-time conjecture for repeated averages on graphs

Abstract

The repeated averages process is a stochastic averaging process on graphs whose mixing time is known for several structured families, but no general sharp expression is known for all connected graphs. It was conjectured that the $L^2\!\to\!L^1$ mixing time is of order $|E|\log n/\lambda_2$. We disprove this conjecture using the graph $G_n$ obtained by attaching one leaf to the complete graph $K_n$. We prove that $\lambda_2(G_n)=1$ and that \[ t_{\varepsilon,2\to1}(G_n)=\Theta_{\varepsilon}(\gamma(G_n))=\Theta_{\varepsilon}(n^2), \] with no additional $\log n$ factor. The example has a strongly localized Fiedler eigenvector: most of its squared $L^2$ mass lies on the leaf, while the balancing mass is spread across the clique.