Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
3  
If you search for "torpid mixing," you should find many examples. –  Douglas Zare Mar 2 '10 at 3:14
1  
arxiv.org/abs/1001.1613 –  Steve Huntsman Mar 2 '10 at 15:46
    
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. –  Steve Huntsman Mar 2 '10 at 15:48
1  
arxiv.org/abs/1001.1894 –  Steve Huntsman Mar 2 '10 at 15:50
add comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.