Markov Chain Monte Carlo Algorithms

马尔可夫链蒙特卡罗算法被用于各种科学领域。此类方法的典型应用依赖于启发式方法来测试收敛性，因此不能保证后续计算的准确性。本项目力求对MCMC方法的一些重要应用进行严格的分析，为一些重要的开放性问题设计新的MCMC算法，并探索MCMC算法的效率与统计物理中的相变之间的联系。我们的工作将集中在以下几个方面：分析统计物理学中关注的Glauber动力学及其与相变的联系；分析进化生物学中用于系统发育重建的MCMC算法；设计统计学中重要的随机抽样列联表的有效算法。这个项目本质上是跨学科的，这个项目的一个重点是应用理论计算机科学的工具来分析统计物理学、进化生物学和统计学中使用的算法。此外，通过探索某些局部算法的效率和相变之间的联系，我们将有助于增加统计物理，离散数学和理论计算机科学研究人员之间的协同作用。我们在系统发育重建的MCMC算法分析方面的工作将为生命之树的研究提供理论基础，这是生物学的中心目标。

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.