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算法的效率与统计物理学中的相变效率之间的联系。我们的工作将重点放在以下目的上：分析在其与相过渡的统计物理学和连接中感兴趣的GLAUBER动力学，分析用于进化生物学的系统发育重建的MCMC算法，并设计有效的算法，以随机采样统计学中的有效算法。 该项目本质上是跨学科的，该项目的重点是从理论计算机科学中应用工具来分析统计物理学，审查生物学和统计数据中使用算法。此外，通过探索某些局部算法的效率与相变的效率之间的联系，我们将有助于在统计物理学，离散数学和理论计算机科学领域的研究人员之间增加协同作用。 我们在分析系统发育重建的MCMC算法方面的工作将有助于研究生命之树的理论基础，这是生物学的核心目标。