Abstract:
The Glauber dynamics are a family of Monte Carlo Markov chains arising from the study of phase transitions in statistical mechanics. Famous models of interest are the hardcore model, the Ising model, and the Potts model. In all three of these models, one is interested in sampling an assignment of spins to the vertices (viewed as "particles") in an input graph, according to a particular class of distributions. The Glauber dynamics is a random walk on these assignments, in which one iteratively chooses a particle at random and flips its spin.The random walk is known to converge, in the limit, to the desired distribution. A common question is how fast this convergence, or mixing, is. We introduce the relevant models, describe known results, and survey some known techniques for proving rapid mixing of Glauber dynamics.