Exact Sampling via Markov Chains

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

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.