Nikash Gupta

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

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...