LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Bordewich, Magnus; Greenhill, Catherine; Patel, Viresh (2016)
Publisher: Wiley-Blackwell
Types: Article
Subjects: Potts model, Mathematics - Combinatorics, Mathematical Physics, Computer Science - Discrete Mathematics, Ferromagnetic., Glauber dynamics, Mixing time
Identifiers:doi:10.1002/rsa.20569
We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interaction strength, we study the interplay between the maximum degree ($\Delta$) of the underlying graph and the number of colours or spins ($q$) in determining whether the dynamics mixes rapidly or not. We find a lower bound $L$ on the number of colours such that Glauber dynamics is rapidly mixing if at least $L$ colours are used. We give a closely-matching upper bound $U$ on the number of colours such that with probability that tends to 1, the Glauber dynamics mixes slowly on random $\Delta$-regular graphs when at most $U$ colours are used. We show that our bounds can be improved if we restrict attention to certain types of graphs of maximum degree $\Delta$, e.g. toroidal grids for $\Delta = 4$.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] N. Alon, A. Frieze, and D. J. A. Welsh, Polynomial time randomised approximation schemes for Tutte-Grothendieck invariants: the dense case, Random Structures and Algorithms 6 (1995), 459-478.
    • [2] B. Bollob´as, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European Journal of Combinatorics 1 (1980), 311-316.
    • [3] C. Borgs, J. T. Chayes, J. H. Kim, A. Frieze, P. Tetali, E. Vigoda and V. H. Vu, Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics, In 40th Annual Symposium on Foundations of Computer Science, IEEE, New York, 1999, pp. 218-229.
    • [4] R. Bubley and M. Dyer, Path coupling: a technique for proving rapid mixing in Markov chains. In 38th Annual Symposium on Foundations of Computer Science, IEEE, Los Alimitos, 1997, pp. 223-231.
    • [5] C. Choua, and S. Lib, Spin systems and Political Districting Problem, Journal of Magnetism and Magnetic Materials 310:2-3 (2007), 2889-2891.
    • [6] M. Dyer, L. Goldberg, C. Greenhill, and M. Jerrum, On the relative complexity of approximate counting problems, Algorithmica 38:3 (2003), 471-500.
    • [7] M. Dyer, L.A. Goldberg, M. Jerrum and R. Martin, Markov chain comparison, Probability Surveys 3 (2006), 89-111.
    • [8] M. Dyer and C. Greenhill, A more rapidly mixing Markov chain for graph colourings, Random Structures and Algorithms 13 (1998), 285-317.
    • [9] H. Finner, A generalisation of H¨older's inequality and some probability inequalities, The Annals of Probability 20 (1992), 1893-1901.
    • [15] T. Hayes, A simple condition implying rapid mixing of single-site dynamics on spin systems, In 47th Annual Symposium on Foundations of Computer Science, IEEE, Berkeley, California, 2006, pp.39-46.
    • [16] F. Jaeger, D. Vertigan and D.J.A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Camb. Phil. Soc. 108 (1990), 35-53.
    • [17] M. R. Jerrum, A very simple algorithm for estimating the number of k-colourings of a low-degree graph, Random Structures and Algorithms 7:2 (1995), 157-165.
    • [18] M. Jerrum and A. Sinclair, Approximating the permanent, SIAM Journal on Computing 18 (1989), 1149-1178.
    • [19] M. R. Jerrum and A. Sinclair, Polynomial-time approximation algorithms for the Ising model, SIAM Journal of Computing 22 (1993), 1087-1116.
    • [20] M. Jerrum and A. Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems, (Dorit Hochbaum, ed.), PWS, 1996.
    • [21] D. Karger, A randomised fully polynomial time approximation scheme for the all terminal network reliability problem, SIAM Journal of Computing 29:2 (1999), 492- 514.
    • [22] F. Martinelli, Lectures on Glauber dynamics for discrete spin models, Lectures on Probability Theory and Statistics (Saint-Flour, 1997), Lecture Notes in Math. 1717, 93-191, Springer, Berlin, 1999.
    • [23] R. B. Potts, Some generalized order-disorder transformations, Proc. Cambridge Philos. Soc. 48 (1952), 106-109.
    • [24] J. Salas and A. Sokal, Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem, Journal of Statistical Physics 86:3-4 (1997), 551-579.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article