CAREER: Markov Chain Monte Carlo Methods

马尔可夫链蒙特卡罗(MCMC)方法是各种领域中的重要算法工具。本项目研究了严格分析马尔可夫链的收敛性质的技术。重点是提炼概率、解析和组合工具(如耦合、LOG-Sobolev和典范路径)来改进现有算法和开发用于重要公开问题的高效算法。计算机科学、离散数学和物理学中出现的问题特别有趣，例如生成随机着色和独立的有界度图集、逼近永久图、估计凸体的体积和采样列联表。该项目还研究了统计物理模型中的相变和相关马尔可夫链的收敛性质之间的内在联系。研究人员正在开发一门新的关于MCMC方法的研究生课程。

Markov chain Monte Carlo (MCMC) methods are an importantalgorithmic device in a variety of fields. This project studiestechniques for rigorous analysis of the convergence properties ofMarkov chains. The emphasis is on refining probabilistic,analytic and combinatorial tools (such as coupling, log-Sobolev,and canonical paths) to improve existing algorithms and developefficient algorithms for important open problems.Problems arising in computer science, discrete mathematics,and physics are of particular interest, e.g., generating randomcolorings and independent sets of bounded-degree graphs,approximating the permanent, estimating the volume of aconvex body, and sampling contingency tables. The projectalso studies inherent connections between phasetransitions in statistical physics models and convergenceproperties of associated Markov chains.The investigator is developing a new graduate course on MCMC methods.