Markov Chain Algorithms for Computational Problems from Physics and Biology

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

C-CR 0105639 Dana Randall "Markov Chain Algorithms for Computational Problems from Physics and Biology" This research in Markov chain Monte Carlo methods has three primary goals: (i) developing new, general techniques for analyzing convergence rates of Markov chains; (ii) designing rigorous, efficient algorithms for specific computational applications, focusing on problems from statistical physics and biology with relevance to computer science; and (iii) exploring the connections between the phase structure of physical models and the inherent limitations of various sampling methods. The research is concentrated in these areas. 1) Coupling has been a very popular method for bounding the convergence rates of Markov chains based on local updates, but only works in restrictive settings. Heat bath algorithms, which allow possibly nonlocal updates, appear to circumvent potentially bad situations arising from simpler chains, but tend to be prohibitively complex for analysis. Decomposition theorems provide a new tool which allow a Markov chain to be broken into pieces whereby a hybrid approach can be used to analyze each piece. The investigator studies how these methods can be used together to approach some new sampling problems. 2) Computational biologists have developed a Turing-universal model of computation based on Wang tiles using double-stranded DNA. New efficient sampling algorithms for some of these simple models are explored with the goal of providing ways to test the model predict outcomes of experiments. 3) The research additionally explores the connection between rapid mixing of locally defined Markov chains and the uniqueness of the Gibbs state of the underlying physical system, also characterized by the lack of a phase transition. Knowledge of this phase structure is used to develop algorithms which will allow sampling below the critical point, where local Markov chains are inefficient.