Maxson Lectures - Phase Transitions in Sampling Algorithms and Applications

Date: April 25, 2022

Time: 4:00PM - 5:00PM

Location: BLOC 117

Speaker: Dana Randall, Georgia Institute of Technology

Description: Sampling algorithms based on Markov chains arise in many areas of computation, engineering and science. The idea is to perform a random walk among the elements in a large state space so that samples chosen from the stationary distribution are useful for the application. In order to get reliable results efficiently we require the chain to be rapidly mixing, or quickly converging to equilibrium. Often there is a parameter of the system (typically related to temperature of fugacity) so that at low values many natural chains converge rapidly while at high values they converge slowly, requiring exponential time. This dichotomy is often related to phase transitions in the underlying models. In this talk we will explain this phenomenon, giving examples form the natural and social sciences including magnetization, lattice gasses, colloids, and models of segregation.