Case Studies in Torpid Mixing: Annotated Bibliography
M. Jerrum
2001, v.7, Issue 1, 75-76
ABSTRACT
A Markov chain is rapidly mixing if, loosely, it converges to equilibrium in a number of steps that is polynomial in the size of its description. Torpid mixing is the opposite: it describes a situation in which convergence requires an exponential, or at least super-polynomial number of steps. I will cover some cases of provable torpidity, including the ``hard core gas'' or independent sets model (with Glauber dynamics and its relatives), and the Potts model (with Swendsen - Wang dynamics).
COMMENTS
Please log in or register to leave a comment
There are no comments yet