Markov Chain Monte Carlo Algorithms

马尔可夫链蒙特卡罗算法

基本信息

批准号：
0830298
负责人：
Eric Vigoda
金额：
$ 30万
依托单位：
Georgia Tech Research Corporation
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2008
资助国家：
美国
起止时间：
2008-08-01 至 2012-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830298&HistoricalAwards=false
关键词：
Markov Chain Monte Carlo Algorithms

项目摘要

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.

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