A constant comparison between systematic and random Ising updates
Let $\pi$ be a zero-field ferromagnetic Ising measure on a finite graph with $n$ vertices, $\pi(\sigma) \propto \exp\bigl(\sum_{uv \in E} J_{uv} \sigma_u \sigma_v\bigr)$ on $\{-1, 1\}^V$ with finite couplings $J_{uv} \ge 0$. For a vertex $v$ let $K_v$ be the heat-bath update at $v$, which resamples the spin at $v$ from its conditional law under $\pi$ given the other spins. Let $P = n^{-1} \sum_v K_v$ be the Glauber dynamics and, for a permutation $\alpha$ of the vertices, let $P_\alpha = K_{\alpha(1)} \cdots K_{\alpha(n)}$ be the systematic scan, one step of which is a complete sweep. For a kernel $Q$ let $$t_{\rm mix}(Q) = \min\Bigl\{t \in \mathbb{N} : \max_\sigma \bigl\|Q^t(\sigma, \cdot) - \pi\bigr\|_{\rm TV} \le 1/4\Bigr\}.$$ For an arbitrary distribution $\pi$ on a finite product space, with $P$ and $P_\alpha$ defined in the same way, Gaitonde and Mossel proved $t_{\rm mix}(P_\alpha) \le C\, n\, t_{\rm mix}(P) \log(4/\pi_{\min})$ for an absolute constant $C$, where $\pi_{\min}$ is the smallest positive value of $\pi$, and that in this generality the bound is tight up to the logarithmic factor.
Problem. Is there an absolute constant $C < \infty$ such that $$n\, t_{\rm mix}(P_\alpha) \le C\, t_{\rm mix}(P)$$ for every graph, every finite set of couplings $J_{uv} \ge 0$ and every permutation $\alpha$?
Source: Levin and Peres (2017), Chapter 26, Question 3(i), for Glauber dynamics of the Ising model. Stated by AIM — Open Applied Problems for every zero-field ferromagnetic Ising measure, with an absolute constant.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- MP
- Keywords
- AIM Open Applied Problems, Glauber dynamics, Ising model, mixing times
References
@book{levin2017,
author = {Levin, David A. and Peres, Yuval},
title = {Markov Chains and Mixing Times},
edition = {Second},
note = {With contributions by Elizabeth L. Wilmer},
publisher = {American Mathematical Society},
address = {Providence, RI},
year = {2017},
doi = {10.1090/mbk/107},
}
@inproceedings{gaitonde2026,
author = {Gaitonde, Jason and Mossel, Elchanan},
title = {Comparison theorems for the mixing times of systematic and random scan dynamics},
booktitle = {Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
publisher = {SIAM},
year = {2026},
pages = {2575--2587},
doi = {10.1137/1.9781611978971.93},
eprint = {2410.11136},
archivePrefix = {arXiv},
}
@misc{aim-ising-systematic-scan,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{A constant comparison between systematic and random Ising updates}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/267-ising-systematic-scan.md},
note = {Entry 267 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00446, "A constant comparison between systematic and random Ising updates", clopen.solutions.