Personal tools
You are here: Home Events Abstract Archives 2001 A lower bound for the mixing time of a class of Markov chains

A lower bound for the mixing time of a class of Markov chains

Martin Dyer University of Leeds 4pm, Tuesday 20 February 2001 Room 2511, JCMB, King's Buildings

Many Markov chain algorithms for generating random configurations in a graph (e.g. a random vertex-colouring or independent set) proceed by randomly modifying the label of a randomly selected vertex. It has long been regarded as "obvious" that such processes must always take $\Omega(n \log n)$ time to "get close" to the stationary distribution in an $n$-vertex graph. We will show how this intuition can be justified, and indicate why it is rather more difficult to prove than might first be supposed.

(Joint work with Leslie Goldberg and Eric Vigoda)

Document Actions