CAREER: Innovations in Markov Chains: Metrics, Duality and Liftings

马尔可夫链模拟是一种非常普遍的技术，应用于物理科学中广泛的问题。从物理和动态过程的显式模拟，如流体动力学和自旋系统，到从大量组合对象的概率分布中采样的算法，马尔可夫链无处不在。该项目将寻求改进这种算法的设计和分析，从而加快运行时间。理解马尔可夫链蒙特卡罗算法的性能包括证明它接近其极限或“平稳”分布的速度。由于任何马尔可夫链模拟中固有的随机性，通常没有可靠的经验准则来衡量这种收敛性；相反，人们必须依靠理论上的保证。PI将专注于如何重新设计马尔可夫链以更快地收敛，以及证明更好的收敛保证这两个长期存在的问题，这两个问题都允许我们更快地安全地终止MCMC模拟。在这项工作的过程中，这些目标将使用来自三个主要专题分组的技术来实现：1。在证明收敛界的“耦合方法”中，人们试图证明在状态空间的某些度量下，马尔可夫链的两个副本可以“彼此接近”。为了改进这种分析，PI试图找到更好的度量，即更好地定义两个状态之间的距离。几种不同的数学对偶概念在马尔可夫链的分析中起着重要的作用。例如，Ising模型的自旋系统和簇表征之间的对偶性，磁性材料的标准模型，平面图形上Potts模型的高温/低温对偶性，以及最近引入的称为进化集方法的强平稳对偶性。PI将尝试通过向状态添加额外的“动量”信息，将可逆马尔可夫链转换为不可逆的“提升”马尔可夫链。这些提升的链允许从原始分布中采样，但可以以二次速度运行。该项目将包括创建和部署一个免费的网络资源“马尔可夫链中心”，其中将包括一系列新的和现有的实验室小程序，用于模拟和试验马尔可夫链和各种收敛措施。这些小程序将帮助学生可视化马尔可夫链，并通过实验和游戏来理解它们。该项目还包括一项综合教育计划，其中规定广泛传播已产生的知识和教育材料。这项工作将支持本科生和研究生的研究和指导。将努力使妇女和少数民族学生最大限度地参与。

Markov chain simulation is a very general technique applied to a wide spectrum of problems in the physical sciences. From explicit simulations of physical and dynamical processes, such as fluid dynamics and spin systems, to algorithms for sampling from probability distributions over enormous sets of combinatorial objects, Markov chains are ubiquitous. This project will seek to improve the design and analysis of such algorithms, leading to faster running times.Understanding the performance of a Markov Chain Monte Carlo algorithm involves proving bounds on how quickly it approaches its limiting, or "stationary", distribution. Due to the inherent randomness in any Markov chain simulation, there is often no reliable empirical criterion for measuring this convergence; rather, one must rely on theoretical guarantees. The PI will focus on the twin long-standing problems of how to redesign Markov chains to actually converge faster, and of proving better convergence guarantees, both of which allow us to safely terminate MCMC simulations sooner. Over the course of this work, these goals will be approached using techniques from three main thematic groupings:1. In the "Coupling Method" for proving convergence bounds, one seeks to show that two copies of a Markov chain can be "made to approach each other" under some metric on the state space. To improve this kind of analysis, the PI seeks to find better metrics, i.e., better definitions of the distance between two states.2. Several different mathematical notions of duality have played important roles in the analysis of Markov chains. For example, the duality between the spin system and the cluster characterization of the Ising model, a standard model of magnetic materials, the high-temperature/low-temperature duality for the Potts model on a planar graph, and strong stationary duality, which underlies a recently introduced technique called the Evolving Sets method.3. The PI will attempt to convert reversible Markov chains into non-reversible "lifted" Markov chains, by adding additional "momentum" information to the states. These lifted chains allow sampling from the original distribution, but can run quadratically faster.The project will include the creation and deployment of a free web resource, "Markov Chains Central," which will include a collection of new and existing laboratory applets for simulating and experimenting with Markov chains and various measures of convergence. These applets will help students visualize Markov chains and understand them through experimentation and play. The project also features an integrated educational plan, which provides for wide dissemination of generated knowledge and educational materials. This work will support undergraduate and graduate student research and mentoring. Effort will be made to maximize involvement of women and minority students.