Markov Chain Algorithms for Computational Problems from Physics and Biology

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

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.