CAREER: Markov Chain Monte Carlo Methods

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

• 批准号: 0237834
• 负责人: Eric Vigoda
• 金额: $ 40万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-01 至 2004-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0237834&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）方法在许多领域都是一种重要的算法手段。这个项目研究的技术严格分析马尔可夫链的收敛性质。重点是改进概率、分析和组合工具（如耦合、log-Sobolev和规范路径），以改进现有算法并开发用于重要开放问题的高效算法。在计算机科学、离散数学和物理学中出现的问题是特别感兴趣的，例如，生成随机着色和有界度图的独立集，近似永久，估计凸体的体积，以及抽样列联表。该项目还研究了统计物理模型中的相变与相关马尔可夫链的收敛性之间的内在联系。研究者正在开发一门关于MCMC方法的新研究生课程。