Uniform sampling through the Lovasz local lemma
Uniform sampling through the Lovasz local lemma
复制标题
DOI：
10.1145/3055399.3055410
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Heng Guo;M. Jerrum;Jingcheng Liu
中科院分区：
文献类型：
--
作者：
Heng Guo;M. Jerrum;Jingcheng Liu
我们提出了一个新的算法框架，称为“部分拒绝抽样”，完全从产品分布中抽取样本，条件是没有一些坏事件发生。我们的框架在Lovász局部引理的变量框架和一些经典的采样算法（如Wilson的有根生成树的“循环弹出”算法）之间建立了新的联系（也许令人惊讶）。在其他应用中，我们发现了新的算法来采样满足分配的k-CNF公式有界变量的出现。
We propose a new algorithmic framework, called “partial rejection sampling”, to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds (perhaps surprising) new connections between the variable framework of the Lovász Local Lemma and some clas- sical sampling algorithms such as the “cycle-popping” algorithm for rooted spanning trees by Wilson. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences.