Pith. sign in

REVIEW 5 minor 28 references

Mixing and cutoff for the systematic scan dynamics of the mean-field ferromagnetic Potts model

T0 review · 0 major / 5 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Systematic scan for the mean-field Potts model mixes in c(β,q) log n scans and exhibits cutoff for all β below the metastability threshold.

desk verdict First clean cutoff theorem for systematic scan on a classical spin system, with matching constant and tight window; the three-phase coupling holds up. read the letter →

arxiv 2607.09841 v1 pith:ILICDXSV submitted 2026-07-10 math.PR cs.DM

Antonio Blanca , Md Tahmidur Rafid This is my paper · ORCID
classification math.PRcs.DM MSC 60J1082B2068W20
keywords mixingtimecutoffsystematicscanmean-fieldPottsmodelferromagneticnon-reversibleMarkovchainsGlauberdynamics
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that the systematic-scan Markov chain for the q-state ferromagnetic Potts model on the complete graph mixes in a sharp number of full scans once the inverse temperature is below the known metastability point β_s. Systematic scan updates every site in a fixed order, rather than choosing a random site each step; it is therefore global and non-reversible, two regimes in which cutoff has been hard to prove. The authors show that after a constant-length burn-in the chain enters a set of well-spread nearly-equiproportional configurations, after which the Hamming distance between two coupled copies contracts geometrically at a precise rate that yields the constant c(β,q). The resulting mixing time is therefore c(β,q) log n + Θ(1), which forces the total-variation distance to drop from nearly 1 to nearly 0 inside a window of constant width. The same threshold is tight: above β_s the chain is exponentially slow. The result supplies the first general cutoff theorem for systematic scan on a spin system and shows that the scan can be at least twice as fast as Glauber dynamics on the same model.

What carries the argument

A three-phase coupling that first drives both chains into the fine-grained set Σ_ ho^n of well-spread nearly-equiproportional configurations (via a one-dimensional drift-plus-supermartingale analysis controlled by a Maximal-Azuma inequality), then contracts Hamming distance and ℓ_{2} distance to equiproportion at the matching geometric rate γ_n determined by the characteristic equation of the linearised update map, and finally coalesces the chains in a single scan by a relative-entropy bound.

What would settle it

Compute or rigorously bound the total-variation distance of the systematic-scan chain after c(β,q) log n - κ scans for large fixed κ and moderate n (say n=10^4); if the distance remains bounded away from 1, or if the distance after c(β,q) log n + κ scans remains bounded away from 0, the claimed cutoff location is false.

Watch

Extended reading notes

Core claim

For every q ≥ 2 and every inverse temperature β < β_s there exists a positive constant c(β,q) such that the systematic-scan dynamics of the mean-field ferromagnetic Potts model has mixing time exactly c(β,q) log n + Θ(1) and therefore exhibits cutoff; the constant is 1/(2b) where b solves β(1-e^{-b})/(q b)=e^{-b}.

Load-bearing premise

After a fixed number of independent scans the chain must enter, and then stay inside, the set of configurations that are both nearly equiproportional and well-spread along the scan order; this rests on a custom concentration inequality for the spin-count supermartingale and on the drift function contracting toward 1/q precisely when β is below the metastability threshold.

Editorial extensions

If this is right

  • Systematic scan mixes at least twice as fast as Glauber dynamics on the same model for every β < β_s.
  • Cutoff can hold for a global non-reversible Markov chain on a classical spin system.
  • The leading constant c(β,q) is completely determined by the root of a simple transcendental equation and can be plotted explicitly against β/q.
  • At the critical value β=β_s the same methods suggest polynomial mixing of order n^c for some c<1 without cutoff.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same drift-plus-contraction analysis should extend to other mean-field models whose update map linearises to a contraction below a known metastability point.
  • If the well-spread condition can be verified under weaker spatial-mixing hypotheses, cutoff for systematic scan may hold on sparse graphs as well.
  • The factor-of-two speed-up relative to Glauber is consistent with the folklore that deterministic scanning halves the coupon-collector overhead; the paper supplies the first sharp confirmation for a non-trivial interacting system.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper proves that the heat-bath systematic scan dynamics for the q-state ferromagnetic mean-field Potts model, for every q≥2 and every inverse temperature β below the spinodal threshold β_s, has mixing time T_mix = c(β,q) log n + Θ(1) (measured in full scans) and therefore exhibits cutoff with an O(1) window. The constant c(β,q) is identified explicitly as 1/(2b) where b>0 solves β(1-e^{-b})/(q b)=e^{-b}. The argument is a three-phase coupling: an O(1)-scan burn-in that places both chains in a fine-grained set Σ_ ho^n of well-spread nearly-equiproportional configurations (Lemma 1.1), a subsequent c(β,q) log n phase that contracts Hamming distance to O(√n) while the proportions vectors contract to O(1/√n) of the equiproportion vector (Lemmas 1.2, 3.4, 5.1), and a final one-scan relative-entropy coupling that finishes coalescence (Lemma 1.3). A matching lower bound is obtained from the same contraction rate together with concentration of the Gibbs measure about equiproportion.

Significance. The result supplies the first general cutoff theorem for systematic scan dynamics of a spin system. Systematic scan is both global and non-reversible, two regimes in which cutoff remains poorly understood; the paper therefore contributes both to the concrete analysis of Potts models and to the broader theory of non-reversible Markov chains. The leading constant is shown to be at least a factor of two smaller than the corresponding Glauber constant, confirming a long-standing folklore speed-up. All proofs are self-contained (Sections 2–7), the constant c(β,q) is obtained from an explicit transcendental equation rather than fitted, and the argument is tight both in the cutoff window and in the temperature range β<β_s.

minor comments (5)
  1. Figure 1 caption and surrounding text: the comparison of c(β,q) with the Glauber constant čc(β,q) would be clearer if the asymptotic relation γ_n=1-b/n+O(n^{-2}) (Lemma 4.1) were referenced explicitly in the caption.
  2. Section 2.1, definition of G_{β,n}: the additive β/n correction is introduced without a one-line justification; a brief remark that it absorbs the mean-value error of Lemma 2.6 would help the reader.
  3. Lemma 2.3 (Maximal-Azuma): the constant 32 in the exponent is slightly looser than the classical Azuma constant; a parenthetical note that the factor arises from the Doob decomposition and the two-sided bound would remove any appearance of arbitrariness.
  4. Section 6, Fact 6.1: the O(∥s-s̃∥_2^{2}) relative-entropy bound is standard but the appendix proof is terse; expanding the Hessian remainder by one line would make the argument fully self-contained.
  5. Throughout: the notation Σ_ ho^n for the fine-grained set is overloaded with the ordinary configuration space Σ_n; a slightly more distinctive symbol (e.g., Σ_ ho^{spread}) would reduce cognitive load.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: pure first-principles multiphase coupling derivation of cutoff for systematic scan, with c(β,q) obtained from an explicit transcendental root of the known drift map.

full rationale

The paper is a self-contained mathematical analysis of the heat-bath systematic-scan chain on the mean-field Potts model. Theorem 1 (cutoff at c(β,q) log n + Θ(1) for β < β_s) is proved by a three-phase coupling: independent burn-in into the fine-grained set Σ_ρ^n (Lemma 1.1, via drift G_β,n plus a custom Maximal-Azuma supermartingale bound), geometric contraction of Hamming distance and proportions vectors at matching rate γ_n (Lemmas 1.2, 3.3–5.1, Sections 3–5), and a final one-scan relative-entropy coupling (Lemma 1.3). The leading constant is defined as 1/(2b) where b solves the explicit equation β(1-e^{-b})/(q b)=e^{-b} (Section 4); this is not fitted to data. β_s is taken from the classical fixed-point analysis of G_β (cited to Cuff et al. [9], independent of the authors). Self-citations appear only for comparison with Glauber mixing times and for standard technical tools; none is load-bearing for the central claim. No self-definitional loops, fitted-as-prediction steps, uniqueness theorems imported from the authors, or ansatz smuggling occur. The lower bound (Section 7) re-uses the same contraction rate plus concentration of μ, confirming tightness without circularity. Score 1 only for the minor, non-load-bearing self-citations that are normal in the literature.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The argument rests on standard Markov-chain coupling and martingale tools plus the classical mean-field Potts free-energy landscape that defines β_s. No free parameters are fitted; the constant c(β,q) is derived from an explicit algebraic equation. The only domain assumptions are the definition of the heat-bath update and the known location of the spinodal point.

assumptions (4)
  • domain assumption The spinodal point β_s is characterized by the first appearance of a second fixed point of the drift map G_eta(x)=e^{βx}/(e^{βx}+(q-1)e^{β(1-x)/(q-1)}) beyond x=1/q (standard for mean-field Potts).
    Invoked throughout to guarantee that G_eta(x)-x<0 on (1/q,1) and therefore that the recursive sequence G^ε_{β,n}(k) contracts into any neighborhood of 1/q after O(1) steps (Lemma 2.4).
  • domain assumption Heat-bath single-site updates are performed according to the conditional Gibbs measure; the resulting systematic-scan chain is ergodic and converges to μ.
    Standard definition of the dynamics; used from the first paragraph of Section 1.
  • standard math Maximal Azuma inequality for bounded-difference supermartingales (Lemma 2.3, adapted from Roch).
    Controls the fluctuation term D^{(ℓ)}_t uniformly over all intervals of length n inside each scan.
  • standard math Pinsker’s inequality relating total-variation distance to relative entropy.
    Converts the O((d_H)^2/n) relative-entropy bound of the final scan into a total-variation coalescence probability (Lemma 1.3).
invented entities (1)
  • The fine-grained configuration set Σ_ ho^n of “well-spread” nearly-equiproportional configurations
    purpose: Ensures that every intermediate configuration during a full scan remains balanced, which is necessary because systematic scan is order-dependent (unlike Glauber).
    Defined in Section 1.1; the burn-in and contraction arguments are proved only inside this set. No independent physical meaning outside the proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Mixing and cutoff for the systematic scan dynamics of the mean-field ferromagnetic Potts model." pith.science (2026). https://pith.science/paper/ILICDXSV

@misc{pith2026260709841,
  author       = {Pith},
  title        = {Pith review of: Mixing and cutoff for the systematic scan dynamics of the mean-field ferromagnetic Potts model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ILICDXSV}},
  note         = {Machine review of arXiv:2607.09841}
}
abstract

We study the mixing time of the systematic scan dynamics for the $q$-state ferromagnetic Potts model on the $n$-vertex complete graph, known as the mean-field model. This Markov chain updates vertices sequentially according to a fixed predetermined order, in contrast to the Glauber dynamics which updates a uniformly random vertex at each step. Systematic scan dynamics are attractive in practice as they often demonstrate strong empirical performance. However, their theoretical analysis remains far less developed than that of the Glauber dynamics. We take a step toward addressing this imbalance by showing that for every $q\ge 2$ and $\beta<\beta_s$, where $\beta_s$ is the metastability threshold associated with the onset of slow mixing for the Glauber dynamics, the systematic scan dynamics for the ferromagnetic mean-field Potts model mixes in $\Theta(\log n)$ scans or, equivalently, in $\Theta(n\log n)$ single site updates. We in fact prove a sharper result; namely, that there exists a constant $c(\beta,q) > 0$ such that the mixing time is $c(\beta,q)\log n + \Theta(1),$ which implies that the Markov chain exhibits the cutoff phenomenon, with the total variation distance to the stationary distribution dropping abruptly from nearly 1 to nearly 0 within a narrow $\Theta(1)$ time window. This result is tight in $\beta$ as well since the dynamics mixes exponentially slowly for $\beta > \beta_s$. To the best of our knowledge, this is the first general cutoff result for the systematic scan dynamics in the context of spin systems. The result may also be of independent interest in the theory of Markov chains, since the systematic scan dynamics is both global and non-reversible, two settings in which cutoff remains poorly understood.

Figures

Figures reproduced from arXiv: 2607.09841 by the authors.

Figure 1
Figure 1. Comparison of mixing times of Glauber (blue curve) and systematic scan dynamics (black curve). [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 3 linked inside Pith

  1. [1]

    Sequential sweeps and high dimensional expansion.arXiv preprint arXiv:2312.02089, 2023

    Vedat Levi Alev and Ori Parzanchevski. Sequential sweeps and high dimensional expansion.arXiv preprint arXiv:2312.02089, 2023

    arXiv 2023

  2. [2]

    Convergence properties of the Gibbs sampler for perturbations of Gaussians.The Annals of Statistics, 24(1):122–140, 1996

    Yali Amit. Convergence properties of the Gibbs sampler for perturbations of Gaussians.The Annals of Statistics, 24(1):122–140, 1996

    1996

  3. [3]

    Spatial mixing and nonlocal Markov chains.Random Structures & Algorithms, 55(3):584–614, 2019

    Antonio Blanca, Pietro Caputo, Alistair Sinclair, and Eric Vigoda. Spatial mixing and nonlocal Markov chains.Random Structures & Algorithms, 55(3):584–614, 2019. Extended abstract appeared SODA 2018

    2019

  4. [4]

    Mean-field Potts and random-cluster dynamics from high-entropy initializations.The Annals of Applied Probability, 36(1):393 – 450, 2026

    Antonio Blanca, Reza Gheissari, and Xusheng Zhang. Mean-field Potts and random-cluster dynamics from high-entropy initializations.The Annals of Applied Probability, 36(1):393 – 450, 2026. Extended abstract appeared SODA 2018

    2026

  5. [5]

    Cutoff for the Swendsen–Wang Dynamics on the Complete Graph

    Antonio Blanca and Zhezheng Song. Cutoff for the Swendsen–Wang Dynamics on the Complete Graph. In45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025), pages 17–1, 2025

    2025

  6. [6]

    Rapid Mixing of Global Markov Chains via Spectral Indepen- dence: The Unbounded Degree Case.Algorithmica, 88(1):19, 2026

    Antonio Blanca and Xusheng Zhang. Rapid Mixing of Global Markov Chains via Spectral Indepen- dence: The Unbounded Degree Case.Algorithmica, 88(1):19, 2026. Extended abstract appeared RANDOM 2023

    2026

  7. [7]

    The statistical mechanics of lattice gases: Vol

    J Bricmont. The statistical mechanics of lattice gases: Vol. 1. B. Simon, Princeton University Press, Princeton, New Jersey, 1993, 1996

    1993

  8. [8]

    Solidarity of Gibbs Samplers: the spectral gap.The Annals of Applied Probability, 35(1):142–157, 2025

    Iwona Chlebicka, Krzysztof Latuszy ´nski, and B la˙ zej Miasojedow. Solidarity of Gibbs Samplers: the spectral gap.The Annals of Applied Probability, 35(1):142–157, 2025

    2025

Show all 28 references
  1. [9]

    P. Cuff, J. Ding, O. Louidor, E. Lubetzky, Y. Peres, and A. Sly. Glauber Dynamics for the Mean-Field Potts Model.Journal of Statistical Physics, 149(3):432–477, 2012

    2012

  2. [10]

    Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques.Michigan Mathematical Journal, 48(1):157–190, 2000

    Persi Diaconis and Arun Ram. Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques.Michigan Mathematical Journal, 48(1):157–190, 2000. 37

    2000

  3. [11]

    Censored Glauber dynamics for the mean field Ising model

    Jian Ding, Eyal Lubetzky, and Yuval Peres. Censored Glauber dynamics for the mean field Ising model. Journal of Statistical Physics, 137(3):407–458, 2009

    2009

  4. [12]

    The mixing time evolution of Glauber dynamics for the mean-field Ising model.Communications in Mathematical Physics, 289(2):725–764, 2009

    Jian Ding, Eyal Lubetzky, and Yuval Peres. The mixing time evolution of Glauber dynamics for the mean-field Ising model.Communications in Mathematical Physics, 289(2):725–764, 2009

    2009

  5. [13]

    Systematic Scan for Sampling Colorings.The Annals of Applied Probability, pages 185–230, 2006

    Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Systematic Scan for Sampling Colorings.The Annals of Applied Probability, pages 185–230, 2006

    2006

  6. [14]

    Dobrushin conditions and systematic scan

    Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Dobrushin conditions and systematic scan. Combinatorics, Probability and Computing, 17(6):761–779, 2008

    2008

  7. [15]

    Matrix norms and rapid mixing for spin systems

    Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Matrix norms and rapid mixing for spin systems. The Annals of Applied Probability, 19(1):71 – 107, 2009

    2009

  8. [16]

    Comparison theorems for the mixing times of systematic and random scan dynamics

    Jason Gaitonde and Elchanan Mossel. Comparison theorems for the mixing times of systematic and random scan dynamics. InProceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2575–2587. SIAM, 2026

    2026

  9. [17]

    Swendsen-Wang algorithm on the mean-field Potts model.Random Structures & Algorithms, 54(1):82–147, 2019

    Andreas Galanis, Daniel ˇStefankoviˇc, and Eric Vigoda. Swendsen-Wang algorithm on the mean-field Potts model.Random Structures & Algorithms, 54(1):82–147, 2019. Extended abstract appeared in RANDOM 2015

    2019

  10. [18]

    Layerwise systematic scan: Deep Boltzmann machines and beyond

    Heng Guo, Kaan Kara, and Ce Zhang. Layerwise systematic scan: Deep Boltzmann machines and beyond. InInternational Conference on Artificial Intelligence and Statistics, pages 178–187. PMLR, 2018

    2018

  11. [19]

    A simple condition implying rapid mixing of single-site dynamics on spin systems

    Thomas P Hayes. A simple condition implying rapid mixing of single-site dynamics on spin systems. InProceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 39–46. IEEE, 2006

    2006

  12. [20]

    Scan order in Gibbs sampling: Models in which it matters and bounds on how much

    Bryan D He, Christopher M De Sa, Ioannis Mitliagkas, and Christopher R ´e. Scan order in Gibbs sampling: Models in which it matters and bounds on how much. InProceedings of Advances in Neural Information Processing Systems (NeurIPS), volume 29, 2016

    2016

  13. [21]

    Systematic scanning Glauber dynamics for the mean-field Ising model.arXiv preprint arXiv:2307.10127, 2023

    Sanghak Jeon. Systematic scanning Glauber dynamics for the mean-field Ising model.arXiv preprint arXiv:2307.10127, 2023

    2023 arXiv

  14. [22]

    Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability.Probability Theory and Related Fields, 146(1):223, 2010

    David A Levin, Malwina J Luczak, and Yuval Peres. Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability.Probability Theory and Related Fields, 146(1):223, 2010

    2010

  15. [23]

    Levin, Yuval Peres, and Elizabeth L

    David A. Levin, Yuval Peres, and Elizabeth L. Wilmer.Markov chains and mixing times. American Mathematical Society, 2006

    2006

  16. [24]

    Cutoff Phenomenon for Cyclic Dynamics on Hypercube.arXiv preprint arxiv:2010.01756, 2024

    Keunwoo Lim. Cutoff Phenomenon for Cyclic Dynamics on Hypercube.arXiv preprint arxiv:2010.01756, 2024

    2010 arXiv

  17. [25]

    Can extra updates delay mixing?Communications in Mathematical Physics, 323(3):1007–1016, 2013

    Yuval Peres and Peter Winkler. Can extra updates delay mixing?Communications in Mathematical Physics, 323(3):1007–1016, 2013

    2013

  18. [26]

    Surprising Convergence Properties of Some Simple Gibbs Samplers under Various Scans.International Journal of Statistics and Probability, 5(4):112–121, 2016

    Gareth O Roberts and Jeffrey S Rosenthal. Surprising Convergence Properties of Some Simple Gibbs Samplers under Various Scans.International Journal of Statistics and Probability, 5(4):112–121, 2016. 38

    2016

  19. [27]

    Cambridge Series in Statistical and Probabilistic Mathematics

    Sebastien Roch.Modern Discrete Probability: An Essential Toolkit. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2024

    2024

  20. [28]

    Towards high-throughput Gibbs sampling at scale: A study across storage managers

    Ce Zhang and Christopher R ´e. Towards high-throughput Gibbs sampling at scale: A study across storage managers. InProceedings of the 2013 ACM SIGMOD international conference on management of data, pages 397–408, 2013. A Relative entropy bound Proof of Fact 6.1.We can verify t...

    2013

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.