Exact Sampling via Markov Chains

对于许多统计物理例子，如随机Ising模型，人们寻求从一个巨大的状态空间的概率分布中抽样，但是由于无法计算适当的归一化常数，基本抽样被排除在外。在计算机科学中，当人们试图从一个大的组合空间中随机抽样时，也会出现类似的困难，而这个组合空间的精确大小在任何合理的时间内都无法确定。马尔可夫链蒙特卡罗（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.