56 citations · 79 across the 7 of their papers we have counts for
Showing math.PRShow all
2 papers · 1 filter
math.PR2006★ 56 cited
Coupling with the stationary distribution and improved sampling for colorings and independent sets
Thomas P. Hayes, Eric Vigoda
We present an improved coupling technique for analyzing the mixing time of Markov chains. Using our technique, we simplify and extend previous results for sampling colorings and in…
math.PR2005
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 , wher…