AF: EAGER: Phase Transitions in Markov Chain Mixing Times

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This project studies Markov Chain Monte Carlo (MCMC) algorithms. MCMC algorithms are widely used in a variety of scientific fields, for instance, for Bayesian inference and for simulations of idealized models of physical systems. At the heart of an MCMC algorithm is a Markov chain whose equilibrium distribution is of particular interest. The efficiency of this Markov chain is measured by its mixing time, which is the requisite number of steps to reach this equilibrium distribution of interest. In this project the PI will design new tools for analyzing the mixing time of Markov chains to gain a better understanding of settings where MCMC algorithms are efficient. The work in this project will enhance scientific studies that rely on MCMC algorithms, and will strengthen ties between the study of randomized algorithms in theoretical computer science with the study of phase transitions in statistical physics. The PI will organize a workshop on topics related to this project, bringing together researchers from statistical physics, discrete mathematics and theoretical computer science. The project aims to connect the mixing time of well-studied Markov chains with phase transitions in the underlying system. In this project the PI will analyze Markov chains that are popular for statistical physics and combinatorial models. The goal is to understand the mixing time of these Markov chains and determine how the mixing time relates to phase transitions in the associated models. Of particular interest is analyzing the mixing time at the critical points of phase transitions.