Mixing of the Glauber Dynamics for the Ferromagnetic Potts Model

Bordewich, Magnus; Greenhill, Catherine; Patel, Viresh

Abstract

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 (Δ) 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 Δ-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 Δ, e.g. toroidal grids for Δ = 4.

Citation

Bordewich, M., Greenhill, C., & Patel, V. (2016). Mixing of the Glauber Dynamics for the Ferromagnetic Potts Model. Random Structures and Algorithms, 48(1), 21-52. https://doi.org/10.1002/rsa.20569

• Journal Article Type: Article
• Acceptance Date: Apr 14, 2014
• Online Publication Date: Sep 4, 2014
• Publication Date: Jan 1, 2016
• Deposit Date: Apr 24, 2015
• Publicly Available Date: Sep 23, 2015
• Journal: Random Structures and Algorithms
• Print ISSN: 1042-9832
• Electronic ISSN: 1098-2418
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 48
• Issue: 1
• Pages: 21-52
• DOI: https://doi.org/10.1002/rsa.20569
• Keywords: Glauber dynamics, Mixing time, Potts model, Ferromagnetic.
• Public URL: https://durham-repository.worktribe.com/output/1409745
• Related Public URLs: http://arxiv.org/abs/1305.0776