A general lower bound for mixing of single-site dynamics on graphs

Thomas P. Hayes, Alistair Sinclair

We prove that any Markov chain that performs local, reversible updates on randomly chosen vertices of a bounded-degree graph necessarily has mixing time at least $\Omega (n\log n)$, wher…