He Bryan, De Sa Christopher, Mitliagkas Ioannis, Ré Christopher
Stanford University.
Adv Neural Inf Process Syst. 2016;29.
Gibbs sampling is a Markov Chain Monte Carlo sampling technique that iteratively samples variables from their conditional distributions. There are two common scan orders for the variables: random scan and systematic scan. Due to the benefits of locality in hardware, systematic scan is commonly used, even though most statistical guarantees are only for random scan. While it has been conjectured that the mixing times of random scan and systematic scan do not differ by more than a logarithmic factor, we show by counterexample that this is not the case, and we prove that that the mixing times do not differ by more than a polynomial factor under mild conditions. To prove these relative bounds, we introduce a method of augmenting the state space to study systematic scan using conductance.
吉布斯采样是一种马尔可夫链蒙特卡罗采样技术，它从变量的条件分布中迭代地进行采样。变量有两种常见的扫描顺序：随机扫描和系统扫描。由于硬件中局部性的优势，即使大多数统计保证仅适用于随机扫描，系统扫描仍被普遍使用。虽然有人推测随机扫描和系统扫描的混合时间相差不超过对数因子，但我们通过反例表明情况并非如此，并且我们证明在温和条件下混合时间相差不超过多项式因子。为了证明这些相对界限，我们引入了一种扩充状态空间的方法，以使用电导来研究系统扫描。
