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

职业：马尔可夫链的创新：度量、对偶性和提升

• 批准号: 1150281
• 负责人: Thomas Hayes
• 金额: $ 43.08万
• 依托单位: University of New Mexico
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2020-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1150281&HistoricalAwards=false
• 关键词: CAREER; Innovations; Markov; Chains; Metrics

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.

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