AF: EAGER: Phase Transitions in Markov Chain Mixing Times

本项目研究马尔可夫链蒙特卡罗（MCMC）算法。 MCMC算法广泛应用于各种科学领域，例如，用于贝叶斯推理和用于物理系统的理想模型的模拟。 MCMC算法的核心是一个马尔可夫链，其均衡分布是特别感兴趣的。 这个马尔可夫链的效率是通过它的混合时间来衡量的，混合时间是达到这个利益均衡分布所需的步骤数。 在这个项目中，PI将设计新的工具来分析马尔可夫链的混合时间，以更好地了解MCMC算法有效的设置。 该项目的工作将加强依赖MCMC算法的科学研究，并将加强理论计算机科学中随机算法研究与统计物理学中相变研究之间的联系。 PI将组织一次与该项目相关主题的研讨会，汇集统计物理、离散数学和理论计算机科学的研究人员。该项目旨在将已充分研究的马尔可夫链的混合时间与底层系统中的相变联系起来。 在这个项目中，PI将分析统计物理和组合模型中流行的马尔可夫链。 我们的目标是了解这些马尔可夫链的混合时间，并确定混合时间如何与相关联的模型中的相变。 特别感兴趣的是分析在相变的临界点的混合时间。

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.