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

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

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.