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

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

• 批准号: 1219115
• 负责人: Thomas Hayes
• 金额: $ 11.2万
• 依托单位: University of New Mexico
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1219115&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将超越传统的Markov链分析技术在离散状态空间上，并在状态连续的系统中获得了新的结​​果，例如飞机中的硬球模型。这项工作是物理学和计算机科学之间的跨学科。 MC算法还提供了一个极好的机会，可以使本科生参与研究过程：他们可以实施物理和计算机科学中使用的算法，并为其在理论和实践中的表现而获得“动手”感觉。他们还可以生产教育小程序，以使其他学生依次看到这些算法。