Glauber Dynamics, expander graphs, and rapid mixing, a survey of problems and techniques


Daniel Frishberg December 10, 2021.


Monte Carlo Markov chains are a versatile tool used in areas such as statistical physics and probabilistic graphical models. We survey a certain class of Markov chain known as the Glauber dynamics. Although motivated by modeling the behavior of magnets, Glauber dynamics are of interest for a number of classical combinatorial counting and sampling problems. In this presentation, we discuss the motivating example of ferromagnetism, then explore the combinatorial applications of Glauber dynamics, and give intuition for two well-established proof techniques: coupling and multicommodity flows. We also survey known results and mention some recent directions of research.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Depth Tradeoffs for Clique and Connectivity
  • A better-than-3 log n depth lower bound for De Morgan formulas with restrictions on top gates
  • Brooks' Theorem in Graph Streams, A Single-Pass Semi-Streaming Algorithm for Δ-Coloring
  • Algorithms and Barriers for Fast Matrix Multiplication
  • Machine Learning for Quantum Many-body Physics