7
$\begingroup$

This should probably be community wiki, but I don't know how to set that myself.

I'm looking for examples or Markov chains that are used in statistics or statistical physics, and which are known to mix slowly. For example, does the standard chain on the hardcore model mix extremely slowly on any interesting graphs? Are there bad row/column sums for which the Diaconis/Sturmfels design walk mixes slowly? Are there interesting families of graphs for which the Broder/Aldous algorithm gets stuck?

I apologize that there is obviously not going to be a single 'right answer' here. I need some pathological examples, and don't know of any that are considered interesting these days.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ If you search for "torpid mixing," you should find many examples. $\endgroup$
    – Douglas Zare
    Commented Mar 2, 2010 at 3:14
  • 1
    $\begingroup$ arxiv.org/abs/1001.1613 $\endgroup$
    – Steve Huntsman
    Commented Mar 2, 2010 at 15:46
  • $\begingroup$ Also I seem to recall there are slowly mixing Anosov systems (I can't recall references offhand): now, consider the associated subshift of finite type given by a Markov partition. $\endgroup$
    – Steve Huntsman
    Commented Mar 2, 2010 at 15:48
  • 1
    $\begingroup$ arxiv.org/abs/1001.1894 $\endgroup$
    – Steve Huntsman
    Commented Mar 2, 2010 at 15:50

2 Answers 2

Reset to default
1
$\begingroup$

The Swendsen-Wang process does not always mix rapidly and this was used later in the paper The "Burnside Process" Converges Slowly that was mentioned to the answer to the question that I asked (here) which has other really good references for mixing times of chains.

Improve this answer
$\endgroup$
0
$\begingroup$

For the Hard-Core model, the existence of rapid mixing Markov Chains depends on the degree of the graph and the activity parameter of the partition function, see http://arxiv.org/abs/1105.5131, Theorem 1.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .