CAREER: Markov Chain Monte Carlo Methods

点击翻译按钮获取中文摘要

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.