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

马尔可夫链蒙特卡罗（MC）算法是物理和生物科学中的重要工具，其应用范围从模拟新材料到重建系统发育树。它们通过一系列微小的变化来探索物理系统的状态空间，或问题的潜在解决方案。我们的主要挑战之一是知道算法是否运行了足够长的时间以达到平衡，即，如果它在整个空间中的分布足以获得重要量的良好估计。在这方面，理论家和实践者之间存在重大分歧。物理学家使用的非严格技术比理论家知道如何证明的要乐观得多。另一方面，它们通常基于对这些系统的物理性质及其渐近行为的深刻认识，并得到数值实验的支持。该奖项的研究主题是回答这个问题：我们如何弥合这两个阵营之间的分歧？PI将集中在三个可以建造更坚固桥梁的领域。在二维自旋系统中，他们将使用相关性的幂律衰减来证明临界点处的多项式混合时间，并表明我们甚至可以在最坏情况下混合时间为指数的相变下有效地“从平衡态重新混合”。他们将对物理学中广泛使用的聚类算法的效率进行严格的理解，这些算法被认为可以避免或减少当我们接近相变时的“临界减速”现象。最后，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.