Skip to main content

Research Repository

Advanced Search

Mixing of the Glauber Dynamics for the Ferromagnetic Potts Model

Bordewich, Magnus; Greenhill, Catherine; Patel, Viresh

Mixing of the Glauber Dynamics for the Ferromagnetic Potts Model Thumbnail


Authors

Catherine Greenhill

Viresh Patel



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
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.
Related Public URLs http://arxiv.org/abs/1305.0776

Files

Published Journal Article (Advance online version) (250 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
Advance online version © 2015 The Authors Random Structures & Algorithms Published by Wiley Periodicals, Inc. This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.






You might also like



Downloadable Citations