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寻求找到更好的指标，即，更好地定义两个状态之间的距离。 几种不同的数学对偶概念在马尔可夫链的分析中发挥了重要作用。 例如，伊辛模型（磁性材料的标准模型）的自旋系统和团簇表征之间的二元性、平面图上波茨模型的高温/低温二元性以及强定态二元性，这是最近引入的一种技术的基础，称为演化集方法。3. PI将尝试通过向状态添加额外的“动量”信息，将可逆马尔可夫链转换为不可逆的“提升”马尔可夫链。 该项目将包括创建和部署一个免费的网络资源“Markov Chains Central”，其中将包括一系列新的和现有的实验室小程序，用于模拟和试验Markov链和各种收敛性措施。这些小程序将帮助学生可视化马尔可夫链，并通过实验和游戏来理解它们。该项目还包括一项综合教育计划，广泛传播所产生的知识和教育材料。这项工作将支持本科生和研究生的研究和指导。将努力使妇女和少数民族学生最大限度地参与。