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

Speaker

Daniel Frishberg December 10, 2021.

Abstract

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.