专栏首页算法和应用利用局部正确性设计完美仿真算法
原创

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

作者: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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 关于无意识匹配问题

    作者:Zhihao Gavin Tang,Xiaowei Wu,Yuhao Zhang

    罗大琦
  • 泛洪算法过程的终端

    摘要:泛洪是所有分布式网络算法中最简单和最基本的算法之一。节点通过向其所有相邻节点发送消息来开始该过程,在下一轮中将消息转发给他们未从其接收消息的所有相邻节点,...

    罗大琦
  • Googol的双面博弈与基于样本的先知不等式

    作者:José Correa,Andrés Cristi,Boris Epstein,José A. Soto

    罗大琦
  • hdu----149850 years, 50 colors(最小覆盖点)

    50 years, 50 colors Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 3276...

    Gxjun
  • 具有细粒度模式的表示学习(cs.CV)

    随着计算能力和数据收集技术的发展,在基准数据集上,深度学习比许多现有算法展现出了更为卓越的性能。在研究深度学习机制方面,我们付出了许多努力。一个重要的观察是,深...

    Donuts_choco
  • POJ-1276-Cash Machine(多重背包)

    Cash Machine Time Limit: 1000MS Memory Limit: 10000K Total Submissions:...

    ShenduCC
  • CF--思维练习--CodeForces - 220C Little Elephant and Shifts (STL模拟)

    ACM思维题训练集合 The Little Elephant has two permutations a and b of length n, consis...

    风骨散人Chiam
  • 聊聊flink的Broadcast State

    flink-core-1.7.0-sources.jar!/org/apache/flink/api/common/state/MapStateDescript...

    codecraft
  • hdu----(1075)What Are You Talking About(trie之查找)

    What Are You Talking About Time Limit: 10000/5000 MS (Java/Others)    Memory Lim...

    Gxjun
  • LeetCode — (1)

      Nim Game、WordPattern、Move zeros、First Bad version、Ugly Number五个算法的python实现。

    oYabea

扫码关注云+社区

领取腾讯云代金券