Markov Chain Monte Carlo Algorithms

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Markov Chain Monte Carlo algorithms are used in a variety of scientific fields. Typical applications of such methods rely on heuristic methods to test convergence, and hence there are no guarantees on the accuracy of the subsequent calculations. This project strives for rigorous analysis of some important applications of MCMC methods, to devise new MCMC algorithms for notable open problems, and to explore connections between the efficiency of MCMC algorithms and phase transitions in Statistical Physics. Our work will focus on the following aims: analyzing the Glauber dynamics which is of interest in Statistical Physics and connections therein to phase transitions, analyzing MCMC algorithms used for phylogenetic reconstruction in Evolutionary Biology, and designing an efficient algorithm for randomly sampling contingency tables which is important in Statistics. This project is interdisciplinary in nature, and a focus of this project is on the application of tools from Theoretical Computer Science to analyze algorithms of use in Statistical Physics, Evo- lutionary Biology, and Statistics. Moreover, by exploring connections between the efficiency of certain local algorithms and phase transitions we will contribute to increased synergy between researchers in Statistical Physics, Discrete Mathematics and Theoretical Computer Science. Our work on the analysis of MCMC algorithms for phylogenetic reconstruction will contribute to the theoretical underpinnings for the study of the tree of life, which is a central goal in Biology.