AF: EAGER: Phase Transitions in Markov Chain Mixing Times

AF：EAGER：马尔可夫链混合时间中的相变

• 批准号: 1555579
• 负责人: Eric Vigoda
• 金额: $ 10万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1555579&HistoricalAwards=false
• 关键词: AF; EAGER; Phase; Transitions; Markov

This project studies Markov Chain Monte Carlo (MCMC) algorithms. MCMC algorithms are widely used in a variety of scientific fields, for instance, for Bayesian inference and for simulations of idealized models of physical systems. At the heart of an MCMC algorithm is a Markov chain whose equilibrium distribution is of particular interest. The efficiency of this Markov chain is measured by its mixing time, which is the requisite number of steps to reach this equilibrium distribution of interest. In this project the PI will design new tools for analyzing the mixing time of Markov chains to gain a better understanding of settings where MCMC algorithms are efficient. The work in this project will enhance scientific studies that rely on MCMC algorithms, and will strengthen ties between the study of randomized algorithms in theoretical computer science with the study of phase transitions in statistical physics. The PI will organize a workshop on topics related to this project, bringing together researchers from statistical physics, discrete mathematics and theoretical computer science.The project aims to connect the mixing time of well-studied Markov chains with phase transitions in the underlying system. In this project the PI will analyze Markov chains that are popular for statistical physics and combinatorial models. The goal is to understand the mixing time of these Markov chains and determine how the mixing time relates to phase transitions in the associated models. Of particular interest is analyzing the mixing time at the critical points of phase transitions.

该项目研究马尔可夫链蒙特卡洛（MCMC）算法。 MCMC算法被广泛用于各种科学领域，例如用于贝叶斯推断，并用于模拟理想的物理系统模型。 MCMC算法的核心是Markov链，其平衡分布特别感兴趣。 马尔可夫链的效率是通过其混合时间来衡量的，这是达到这种均衡分布的必要步骤。 在这个项目中，PI将设计新工具，用于分析马尔可夫链的混合时间，以更好地了解MCMC算法有效的设置。 该项目的工作将增强依赖MCMC算法的科学研究，并通过研究统计物理学的相位过渡的理论计算机科学研究中随机算法的研究。 PI将组织一个与该项目相关的主题的研讨会，将统计物理学，离散数学和理论计算机科学的研究人员聚集在一起。该项目旨在将经过深思熟虑的马尔可夫链的混合时间与基础系统中的相位转变联系起来。 在该项目中，PI将分析Markov连锁店在统计物理和组合模型中流行的链条。 目的是了解这些马尔可夫链的混合时间，并确定混合时间与相关模型中的相变的关系。 特别有趣的是分析相变临界点的混合时间。