A general lower bound for mixing of single-site dynamics on graphs
A general lower bound for mixing of single-site dynamics on graphs
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)$, where $n$ is the number of vertices. Our bound applies to the so-called ``Glauber dynamics'' that has been used extensively in algorithms for …