CAREER: Markov Chain Monte Carlo Methods

职业：马尔可夫链蒙特卡罗方法

• 批准号: 0455666
• 负责人: Eric Vigoda
• 金额: $ 29.75万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2009-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0455666&HistoricalAwards=false
• 关键词: CAREER; Markov; Chain; Monte; Carlo

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.

马尔可夫链蒙特卡罗（MCMC）方法是多种领域中重要的算法装置。 该项目研究严格分析马尔可夫链收敛特性的技术。 重点是完善概率、分析和组合工具（例如耦合、对数索博列夫和规范路径），以改进现有算法并为重要的开放问题开发有效的算法。计算机科学、离散数学和物理学中出现的问题尤其如此兴趣，例如，生成随机着色和独立的有界度图集、近似常量、估计凸体的体积以及对列联表进行采样。 该项目还研究统计物理模型中的相变与相关马尔可夫链的收敛特性之间的内在联系。研究人员正在开发一门关于 MCMC 方法的新研究生课程。