It is well-known that the Glauber dynamics will converge in polynomial time to the Gibbs distribution for, say, the Ising model on a d-regular graph at high enough temperatures $T>T_c$. There are also some explicit bounds on how high this temperature has to be. But how about the slow mixing regime? I only know explicit bounds on the mixing time for the complete graph. Is there anything known for d-regular graphs? i.e. a bound of the form if $T<T_c$, then the mixing time is at most $\textrm{exp}(c(T)n)$, with $c(T)$ an explicit constant depending on the temperature? Intuitively, I would expect that the exponent of the mixing time should depend on the temperature and hopefully be smaller than 2 for temperatures mildly below the critical one.

I would also be happy with the results of this type for other Monte Carlo algorithms such as annealing. That is, a resulting stating that an exponential annealing schedule would give me a sample from the distribution at temperatures above the critical one. Thanks in advance!

  • 2
    $\begingroup$ +1. Nice question! $\endgroup$ – user1271772 Jul 31 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.