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 0105639Dana Randall“用于物理和生物学计算问题的马尔可夫链算法”这项马尔可夫链蒙特卡罗方法的研究具有三个主要目标：（i）开发用于分析马尔可夫链收敛率的新的通用技术； (ii) 为特定计算应用设计严格、高效的算法，重点关注与计算机科学相关的统计物理学和生物学问题； (iii)探索物理模型的相结构与各种采样方法的固有局限性之间的联系。研究集中在这些领域。 1）耦合是一种非常流行的基于局部更新限制马尔可夫链收敛速度的方法，但仅适用于限制性设置。 热浴算法允许可能的非本地更新，似乎可以避免由较简单的链引起的潜在不良情况，但分析起来往往过于复杂。分解定理提供了一种新工具，可以将马尔可夫链分解为多个片段，从而可以使用混合方法来分析每个片段。研究人员研究如何结合使用这些方法来解决一些新的抽样问题。 2) 计算生物学家使用双链 DNA 开发了基于 Wang 瓦片的图灵通用计算模型。 针对其中一些简单模型探索了新的有效采样算法，目的是提供测试模型预测实验结果的方法。3）该研究还探讨了局部定义的马尔可夫链的快速混合与吉布斯状态的独特性之间的联系。底层物理系统，其特征还在于缺乏相变。 这种阶段结构的知识用于开发算法，该算法允许在局部马尔可夫链效率低下的临界点以下进行采样。