# Scan Order in Gibbs Sampling: Models in Which it Matters and Bounds on How Much

arXiv: https://arxiv.org/abs/1606.03432 · HTML: https://mlsanity.com/paper/1606.03432/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2016.

## Built on by (most cited first, 12 of 12)

- [Invariance Principle Meets Information Bottleneck for Out-of-Distribution Generalization](https://mlsanity.com/paper/2106.06607/) (2021)
- [Glauber Generative Model: Discrete Diffusion Models via Binary Classification](https://mlsanity.com/paper/2405.17035/) (2024)
- [Quantum-enhanced Markov chain Monte Carlo](https://mlsanity.com/paper/2203.12497/) (2022)
- [Cascading and Proxy Membership Inference Attacks](https://mlsanity.com/paper/2507.21412/) (2025)
- [Principled Gradient-based Markov Chain Monte Carlo for Text Generation](https://mlsanity.com/paper/2312.17710/) (2023)
- [Scalability of Metropolis-within-Gibbs schemes for high-dimensional Bayesian models](https://mlsanity.com/paper/2403.09416/) (2024)
- [Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds](https://mlsanity.com/paper/2111.07372/) (2021)
- [Linear Complexity Gibbs Sampling for Generalized Labeled Multi-Bernoulli Filtering](https://mlsanity.com/paper/2211.16041/) (2022)
- [Reconsidering Dependency Networks from an Information Geometry Perspective](https://mlsanity.com/paper/2107.00871/) (2021)
- [Accelerated Markov Chain Monte Carlo Using Adaptive Weighting Scheme](https://mlsanity.com/paper/2408.12888/) (2024)
- [A fast non-reversible sampler for Bayesian mixture models](https://mlsanity.com/paper/2510.03226/) (2025)
- [Reconsidering Dependency Networks from an Information Geometry Perspective](https://mlsanity.com/paper/2604.01117/) (2026)

## Abstract (arXiv)

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.