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 or 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 discrete models of segregation.

Dana Randall is Director of the Algorithms and Randomness Center and the ADVANCE Professor of Computing at the Georgia Institute of Technology. She received her undergraduate degree in Mathematics from Harvard University, her Ph.D. in Computer Science from the University of California at Berkeley, and held postdoctoral positions at the Institute for Advanced Study (IAS) and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) in Princeton. She is a Fellow of the AMS, a National Associate of the National Academies, and has been the recipient of an NSF CAREER award and a Sloan Foundation Fellowship. She currently serves on the Committee for the Advancement of Theoretical Computer Science, the SIAM Symposium on Discrete Algorithms Steering Committee, is co-chair of the next biennial SIAM Conference on Discrete Mathematics in 2016, and is co-chairing the Georgia Tech Strategic Initiative in Data Engineering and Science.