Search Results

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 ≥ 2 and β < β_s, where β_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 Θ(log n) scans or, equivalently, in Θ(nlog n) single site updates. We in fact prove a sharper result; namely, that there exists a constant c(β,q) > 0 such that the mixing time is c(β,q)log n + Θ(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 Θ(1) time window. This result is tight in β as well since the dynamics mixes exponentially slowly for β > β_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.