利用局部正确性设计完美仿真算法

作者：Mark Huber

摘要：考虑一种随机算法，该算法使用递归从分布中精确地绘制样本。这种算法被称为完美模拟，这里建立各种用于构建这种算法的方法都源自相同的结果：完美模拟的基本定理（FTPS）。 FTPS为递归概率算法的输出提供了两个必要且充分的条件，以准确地得出所需的分布。首先，算法必须以概率1终止。其次，算法必须是局部正确的，这意味着如果原始算法中的递归调用被从所需分布中抽取的oracles取代，那么这个新算法可以被证明是正确。虽然验证这些条件通常很简单，但它们却非常强大，给出了接受/拒绝的正确性，来自过去的耦合，随机性回收器，一次性读取CFTP，部分拒绝采样，部分递归接受拒绝以及各种伯努利工厂。我们通过为线性函数构建一个新的伯努利工厂来说明这种算法的使用，比前一种方法快41％。

原文标题：Designing Perfect Simulation Algorithms using Local Correctness

原文摘要：Consider a randomized algorithm that draws samples exactly from a distribution using recursion. Such an algorithm is called a perfect simulation, and here a variety of methods for building this type of algorithm are shown to derive from the same result: the Fundamental Theorem of Perfect Simulation (FTPS). The FTPS gives two necessary and sufficient conditions for the output of a recursive probabilistic algorithm to come exactly from the desired distribution. First, the algorithm must terminate with probability 1. Second, the algorithm must be locally correct, which means that if the recursive calls in the original algorithm are replaced by oracles that draw from the desired distribution, then this new algorithm can be proven to be correct. While it is usually straightforward to verify these conditions, they are surprisingly powerful, giving the correctness of Acceptance/Rejection, Coupling from the Past, the Randomness Recycler, Read-once CFTP, Partial Rejection Sampling, Partially Recursive Acceptance Rejection, and various Bernoulli Factories. We illustrate the use of this algorithm by building a new Bernoulli Factory for linear functions that is 41\% faster than the previous method.

地址：https://arxiv.org/abs/1907.06748