Mixing of the Glauber dynamics for the ferromagnetic Potts model.

Article, Preprint OPEN
Bordewich, Magnus ; Greenhill, Catherine ; Patel, Viresh (2016)
  • Publisher: Wiley-Blackwell
  • Related identifiers: doi: 10.1002/rsa.20569
  • Subject: Potts model | Mathematics - Combinatorics | Mathematical Physics | Computer Science - Discrete Mathematics | Ferromagnetic. | Glauber dynamics | Mixing time

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$.
  • References (19)
    19 references, page 1 of 2

    [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.

  • Metrics
    No metrics available
Share - Bookmark