Markov Chain Algorithms for Computational Problems from Physics and Biology

用于物理和生物学计算问题的马尔可夫链算法

• 批准号: 0105639
• 负责人: Dana Randall
• 金额: $ 22.15万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-01 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0105639&HistoricalAwards=false
• 关键词: Markov; Chain; Algorithms; Computational; Problems

C-CR 0105639Dana 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 ratesof 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 someof these simple models are explored with the goal of providing waysto 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.

C-CR 0105639 Dana Randall“Markov Chain Algorithms for Computational Problems from Physics and Biology“本研究在Markov chain Monte Carlo方法有三个主要目标：（i）开发新的，通用的技术，用于分析Markov chain的收敛速度;（ii）设计严格的，有效的算法，用于特定的计算应用，重点是统计物理学和生物学与计算机科学相关的问题;（iii）设计复杂的，复杂的计算问题。以及（iii）探讨物理模型的相结构与各种采样方法的固有局限性之间的联系。研究集中在这些领域。 1)耦合方法是一种基于局部更新的马尔可夫链收敛速度的边界估计方法，但它只适用于有限的条件。 热浴算法，它允许可能的非局部更新，似乎规避潜在的坏情况下产生的简单的链，但往往是过于复杂的分析。分解定理提供了一种新的工具，它允许马尔可夫链被分成几块，从而可以使用混合方法来分析每一块。研究人员研究如何将这些方法结合起来，以解决一些新的采样问题。 2)计算生物学家使用双链DNA开发了基于Wang tiles的图灵通用计算模型。 新的有效的采样算法，这些简单的模型进行了探索，目的是提供方法来测试模型预测的实验结果。3）该研究还探讨了快速混合的本地定义的马尔可夫链和吉布斯状态的唯一性的基础物理系统，也缺乏相变的特点之间的联系。 知识的相位结构是用来开发算法，这将允许采样低于临界点，当地马尔可夫链是低效的。