Exact Sampling via Markov Chains

通过马尔可夫链进行精确采样

• 批准号: 9626756
• 负责人: James Fill
• 金额: $ 6.4万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-07-01 至 1998-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9626756&HistoricalAwards=false
• 关键词: Exact; Sampling; via; Markov; Chains

9626756 Fill ABSTRACT For many statistical physics examples, such as the stochastic Ising model, one seeks to sample from a probability distribution on an enormously large state space, but elementary sampling is ruled out by the infeasibility of calculating an appropriate normalizing constant. Similar difficulties arise in computer science when one seeks to sample randomly from a large combinatorial space whose precise size cannot be ascertained in any reasonable amount of time. The Markov chain Monte Carlo (MCMC) approximate sampling approach to such a problem is to construct and run "for a long time" a Markov chain with long-run distribution equal to the given distribution. But determining how long is long enough can be both analytically and empirically difficult. Very recently, researchers have devised an algorithm to use the same Markov chains to produce exact samples from the desired distribution. However, the running time of the algorithm is unbounded and not independent of the state sampled, so a user with limited patience will introduce systematic bias by aborting a long run. The investigator assesses the extent of this bias, implements and studies (via a certain "duality" theory) the performance of a new algorithm he devises to eliminate the bias, and establishes bounds on the performance of any such Markov-chain-based algorithm. Physicists are interested in models for ferromagnetism and for phase transitions (such as freezing and thawing). In such statistical mechanics problems, in image processing (the cleaning up of noisy or blurred images), and in computer science, much can be learned by studying certain probability distributions on sets having enormously large numbers of elements. The standard "Monte Carlo" approach to studying a distribution is to draw a (representative) random sample, but this approach is computationally infeasible for problems of such large size. To handle such problems, researchers use computers to simulate certain probabilistic processes, called Mar kov chains, which, in a certain precise sense, "settle down" to the distribution of interest "in the long run." But determining how long is long enough to run the chain in order to approximate the distribution sufficiently closely can be difficult to assess, both theoretically and empirically. Very recently, researchers have devised an algorithm to use the same Markov chains to produce exact samples from the desired distribution. However, the running time of the algorithm is sometimes very large, and the distribution of the output can depend on the running time, so a user with limited patience will introduce systematic bias by aborting a long run. The investigator, a probabilist, assesses the extent of this bias, implements and analyzes the performance of a new algorithm he devises to eliminate the bias, and considers how well any such Markov-chain-based algorithm can perform.

9626756 填写摘要 对于许多统计物理示例，例如随机伊辛模型，人们试图从极大的状态空间上的概率分布中进行采样，但基本采样因无法计算适当的归一化常数而被排除。 当人们试图从一个大的组合空间中随机采样时，在计算机科学中也会出现类似的困难，而该组合空间的精确大小无法在任何合理的时间内确定。解决此类问题的马尔可夫链蒙特卡罗 (MCMC) 近似采样方法是构造并“长时间”运行一个长期分布等于给定分布的马尔可夫链。 但确定多长的时间才算足够长，在分析和经验上都可能很困难。最近，研究人员设计了一种算法，使用相同的马尔可夫链从所需的分布中生成精确的样本。 然而，算法的运行时间是无限的，并且与采样的状态无关，因此耐心有限的用户会通过中止长期运行而引入系统偏差。 研究人员评估这种偏差的程度，实施和研究（通过某种“对偶”理论）他设计的用于消除偏差的新算法的性能，并为任何此类基于马尔可夫链的算法的性能建立界限。 物理学家对铁磁性和相变（例如冻结和融化）模型感兴趣。 在此类统计力学问题、图像处理（清理噪声或模糊图像）以及计算机科学中，通过研究具有大量元素的集合上的某些概率分布可以学到很多东西。 研究分布的标准“蒙特卡罗”方法是抽取（代表性）随机样本，但对于如此大尺寸的问题，这种方法在计算上是不可行的。 为了解决这些问题，研究人员使用计算机来模拟某些概率过程，称为马尔可夫链，从某种精确意义上讲，“从长远来看”“稳定”到利益的分配。 但无论从理论上还是从经验上来说，确定运行链的时间足够长才能足够接近分布可能都很难评估。 最近，研究人员设计了一种算法，使用相同的马尔可夫链从所需的分布中生成精确的样本。 然而，算法的运行时间有时非常长，并且输出的分布可能取决于运行时间，因此耐心有限的用户会通过中止长时间运行来引入系统偏差。调查员是一名概率学家，评估这种偏差的程度，实施并分析他设计的消除偏差的新算法的性能，并考虑任何此类基于马尔可夫链的算法的性能。