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 算法的核心是马尔可夫链，其均衡分布特别令人感兴趣。该马尔可夫链的效率是通过其混合时间来衡量的，这是达到这种利益平衡分布所需的步骤数。在这个项目中，PI 将设计新工具来分析马尔可夫链的混合时间，以便更好地了解 MCMC 算法有效的设置。该项目的工作将加强依赖 MCMC 算法的科学研究，并将加强理论计算机科学中的随机算法研究与统计物理学中的相变研究之间的联系。 PI 将组织一个与该项目相关主题的研讨会，汇集来自统计物理学、离散数学和理论计算机科学的研究人员。该项目旨在将经过充分研究的马尔可夫链的混合时间与底层系统中的相变联系起来。在这个项目中，PI 将分析统计物理和组合模型中流行的马尔可夫链。目标是了解这些马尔可夫链的混合时间，并确定混合时间与相关模型中的相变的关系。特别令人感兴趣的是分析相变临界点的混合时间。