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算法进行系统发育重建的分析工作将有助于生命树研究的理论基础，这是生物学的一个中心目标。