从空间混合中采样效果更好

作者：Weiming Feng,Heng Guo,Yitong Yin

摘要：我们的研究结果表明强烈的空间混合速度比邻域的增长速度快，这意味着旋转系统存在有效的完美采样器。 我们新的基于重采样的算法绕过了这条线的先前工作的主要障碍，即我们的算法适用于一般旋转系统，并且不需要问题的其他结构。 此外，我们的框架自然地结合了空间混合属性以获得线性预期运行时间。 使用这种新技术，我们为有界度图和带有指数邻域增长的图中的着色提供了当前最佳的完美采样算法。

原文标题：Perfect sampling from spatial mixing

原文摘要：We show that strong spatial mixing with a rate faster than the growth of neighborhood implies the existence of efficient perfect samplers for spin systems. Our new resampling based algorithm bypasses a major barrier of previous work along this line, namely that our algorithm works for general spin systems and does not require additional structures of the problem. In addition, our framework naturally incorporates spatial mixing properties to obtain linear expected running time. Using this new technique, we give the currently best perfect sampling algorithms for colorings in bounded degree graphs and in graphs with sub-exponential neighborhood growth.

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