AF: Small: Collaborative Research: The Physics of Markov Chains: Closing the Gap Between Theory and Practice

AF：小：协作研究：马尔可夫链物理学：缩小理论与实践之间的差距

• 批准号: 1219117
• 负责人: Cristopher Moore
• 金额: $ 8.8万
• 依托单位: Santa Fe Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1219117&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Physics

Markov chain Monte Carlo (MC) algorithms are important tools throughout the physical and biological sciences, with applications ranging from simulating new materials to reconstructing phylogenetic trees. They explore a space of states of a physical system, or potential solutions to a problem, by making a series of small changes. One of our main challenges is knowing whether the algorithm has run long enough to reach equilibrium, i.e., if it has spread throughout the space enough to obtain good estimates of important quantities. Here, there is a major divide between theoreticians and practitioners. Physicists use non-rigorous techniques that are much more optimistic than what theorists know how to prove. On the other hand, they are often based on deep ideas about the physical properties of these systems and their asymptotic behavior, and are backed up by numerical experiments. The main theme of the research under this award is to answer the question: how can we bridge the divide between these two camps?The PIs will focus on three areas where stronger bridges can be built. In two-dimensional spin systems, they will use power-law decay of correlations to prove polynomial mixing times at critical points, and to show that we can efficiently "remix from equilibrium" even below phase transitions where worst-case mixing times are exponential. They will give a rigorous understanding of the efficiency of cluster algorithms widely used in physics, which are believed to avoid or reduce the phenomenon of "critical slowing down" as we approach a phase transition. Finally, the PIs will go beyond traditional Markov chain analysis techniques on discrete state spaces, and prove new results on systems whose states are continuous, such as the hard-sphere model in the plane.This work is cross-disciplinary between physics and computer science. MC algorithms also offer an excellent opportunity to involve undergraduates in the research process: they can implement algorithms used in physics and computer science, and gain a "hands-on" feeling for their performance in theory and practice. They can also produce educational applets to let other students, in turn, see these algorithms in action.

马尔可夫链蒙特卡罗 (MC) 算法是整个物理和生物科学的重要工具，其应用范围从模拟新材料到重建系统发育树。他们通过进行一系列小的改变来探索物理系统的状态空间或问题的潜在解决方案。我们的主要挑战之一是了解算法是否运行了足够长的时间以达到平衡，即它是否已在整个空间中传播到足以获得重要数量的良好估计。在这里，理论家和实践者之间存在着重大分歧。物理学家使用的非严格技术比理论学家知道如何证明的技术要乐观得多。另一方面，它们通常基于关于这些系统的物理特性及其渐近行为的深刻想法，并得到数值实验的支持。该奖项研究的主题是回答这样的问题：我们如何弥合这两个阵营之间的分歧？PI将重点关注可以建立更牢固桥梁的三个领域。在二维自旋系统中，他们将使用相关性的幂律衰减来证明关键点处的多项式混合时间，并表明我们可以有效地“从平衡重新混合”，甚至在最坏情况混合时间呈指数级的相变之下也是如此。他们将对物理学中广泛使用的集群算法的效率进行严格的理解，这些算法被认为可以避免或减少当我们接近相变时出现的“临界减速”现象。最后，PI将超越离散状态空间上的传统马尔可夫链分析技术，并在状态连续的系统上证明新的结果，例如平面中的硬球模型。这项工作是物理学和计算机科学之间的跨学科。 MC算法还提供了一个让本科生参与研究过程的绝佳机会：他们可以实现物理和计算机科学中使用的算法，并对其在理论和实践中的表现获得“动手”感觉。他们还可以制作教育小程序，让其他学生依次看到这些算法的运行情况。