Source-linked AI summary
Optimal mixing of the systematic scan dynamics via approximate tensorization of entropy
Antonio Blanca, Md Tahmidur Rafid
TL;DR
The paper asks whether weak-dependence conditions that support fast Glauber dynamics also guarantee fast convergence when coordinates are updated in a fixed order. It proves systematic-scan mixing and relaxation guarantees from approximate tensorization, with applications in specified spin-system regimes.
Problem
Whether weak dependence and local interactions that support optimal Glauber mixing also guarantee optimal mixing for systematic scans remains largely open.
Source: §1 · p. 2Method
The paper uses approximate tensorization of entropy and variance to analyze systematic scans, proving mixing bounds and variance contraction across scan orders.
Source: §1 · p. 3Results
O(log n) mixing holds for every scan order under the entropy theorem’s stated assumptions, while the additive and multiplicative reversibilizations have relaxation time at most 2(1 + C∆^2).
Source: §1 · pp. 3–4Takeaways & Limitations
The tensorization regimes align with the tree-uniqueness region for hard-core and antiferromagnetic Ising models and the subcritical regime for ferromagnetic Potts models on square boxes.
Source: §1 · p. 5The entropy mixing guarantee assumes single-coordinate conditional probabilities bounded away from zero and connectivity preserved under conditioning.
Source: §1 · p. 4
Abstract
from arXiv · showhide
We study the mixing time of the systematic scan dynamics for high-dimensional discrete distributions. This Markov chain updates coordinates sequentially according to a fixed predetermined order, in contrast to the Glauber dynamics that updates coordinates selected uniformly at random. The systematic scan is often favored in practice because it exhibits strong empirical performance, but its theoretical analysis remains far less developed than that of Glauber dynamics. We take a step toward addressing this imbalance by showing that two standard functional notions of weak dependence between the coordinates of the distribution provide strong convergence guarantees for the systematic scan dynamics. First, we show that approximate tensorization of entropy implies optimal $O(\log n)$ mixing time for every scan order under standard marginal, connectivity, and bounded interaction degree assumptions about the distribution. Second, we show that approximate tensorization of variance yields a constant-factor contraction of the variance functional per scan, which in turn implies an optimal $O(1)$ relaxation time for the natural additive and multiplicative reversibilizations of the systematic scan dynamics. Compared with our entropy result, the variance bound improves the dependence on the maximum interaction degree from exponential to quadratic and requires weaker assumptions on the distribution. As concrete applications of our results, we establish optimal $O(\log n)$ mixing of the systematic scan dynamics for bounded-degree antiferromagnetic two-spin systems in the tree-uniqueness region and for the ferromagnetic $q$-state Potts model on square boxes in $\mathbb{Z}^2$ throughout its subcritical regime.
1 Introduction
The paper studies conditions that yield convergence guarantees for systematic-scan dynamics, linking approximate tensorization, spectral independence, and strong spatial mixing. It also presents applications to spin systems and lattice and edge-variable settings, including logarithmic-time mixing in stated regimes.
1 Introduction
- Variance tensorization gives every scan order a variance contraction and additive and multiplicative reversibilizations relaxation time at most 2(1 + C∆^2).When C and ∆ are independent of n, the relaxation-time bound is O(1).Source: §1 · p. 3
- Entropy tensorization yields O(log n) mixing for every scan order when the distribution is totally connected, b-marginally bounded, and has bounded-degree commutation graph.The theorem assumes C-approximate tensorization of entropy; the logarithmic bound follows when C and ∆ are bounded independently of n and b stays bounded away from zero.Source: §1 · p. 4
1.1 Proof ideas
- The variance proof peels commuting updates from conditional-variance terms, while entropy uses a related contraction argument and controls neighboring updates through pairwise conditional entropy.The entropy proof’s neighboring-update bound is weaker than the variance case and uses b-marginal boundedness and total connectedness.Source: §1.1 · pp. 5–6
1.2 Applications to spin systems
- The spin-system applications use known criteria including spectral independence, which implies approximate tensorization of variance and entropy and thereby certifies fast systematic-scan mixing.The paper also identifies strong spatial mixing as a principal criterion for approximate tensorization in spin systems.Source: §1.2 · p. 6, §1.2.1 · p. 7
1.2.1 Spectral independence
- Systematic scan mixes in O(log n) for hard-core models below the tree-uniqueness threshold, proper colorings when q ≥ (11/6 − ε0)∆, and antiferromagnetic two-spin systems within the tree-uniqueness region.The two-spin result assumes a fixed gap from the tree-uniqueness boundary.Source: §1.2.1 · p. 8
- The ferromagnetic q-state Potts model also has O(log n) systematic-scan mixing.The passage states this result for the model on a graph, without specifying a further parameter condition.Source: §1.2.1 · p. 8
- O(∆²) relaxation time follows for general antiferromagnetic two-spin systems in the tree-uniqueness region with fixed gap δ > 0 and η-spectral independence independent of ∆ or n.The variance tensorization theorem has quadratic dependence on degree.Source: §1.2.1 · p. 8
1.2.2 Strong spatial mixing on lattices
- Strong spatial mixing gives approximate tensorization of variance and entropy for every finite box and pinning, with constants independent of box dimensions and pinning.The constants depend on dimension, the SSM constants, and the spin-system specification.Source: §1.2.2 · p. 9
- O(log n) mixing holds for every scan order and exterior pinning in the ferromagnetic q-state Potts model on square boxes in Z² for β < βc(q) = log(1 + √q).The bound is sharp in its dependence on n already for q = 2, by an Ω(log n) lower bound that transfers from a multiplicative reversibilization to the corresponding systematic scan.Source: §1.2.2 · p. 9
1.3 Applications to edge-variable models
- O(log |F|) mixing holds for deterministic edge orders in bounded-degree Holant families including monomer–dimer models [CLV23, Theorem 2.10], log-concave models [CG24, Theorem 13], and subgraph world models.Log-concave models include weighted b-matchings and antiferromagnetic two-spin edge models.Source: §1.3 · pp. 9–10
2 Preliminaries
The preliminaries define the systematic scan and set out how variance or entropy contraction connects to convergence guarantees. They also establish the operator and spectral-gap framework used for those connections.
2 Preliminaries
- The scan applies coordinate updates in a fixed order; its transition operator acts on functions in reverse order, and under global connectedness it is ergodic with stationary distribution µ.Consequently, it converges to µ from every initial state.Source: §2 · p. 10
2.1 Spectral gap
- For an ergodic chain, the relaxation time is the inverse absolute spectral gap.The section also introduces the Dirichlet-form framework for discussing spectral gaps.Source: §2.1 · pp. 10–11
2.2 Contraction of variance, entropy, and mixing times
- Variance contraction yields spectral-gap bounds for the additive and multiplicative reversibilizations of a chain.The section also defines entropy contraction and states a mixing-time consequence when the adjoint contracts entropy.Source: §2.2 · p. 11
3 Contraction of variance under the systematic scan dynamics
Approximate tensorization of variance gives a variance-contraction result for systematic scans under a bounded-degree commutation graph. The proof controls how neighboring updates affect coordinate-wise Dirichlet forms.
3 Contraction of variance under the systematic scan dynamics
- Approximate tensorization of variance and a commutation graph of maximum degree at most ∆ yield variance contraction for every scan order.The theorem applies to every real-valued function.Source: §3 · p. 12
- A coordinate update commuting with another update allows its effect to be peeled away when bounding a coordinate-wise conditional variance.Approximate tensorization of variance is expressed through the sum of coordinate-wise Dirichlet forms.Source: §3 · p. 12
- For neighboring updates, the square root of a coordinate's Dirichlet form increases by at most the neighbor's own form; iterating and summing yields the bound.The proof uses the maximum degree ∆ to bound the number of earlier neighbors and telescopes the resulting sum.Source: §3 · pp. 12–13
4 Contraction of entropy under the systematic scan dynamics
The section establishes entropy contraction for systematic scans under approximate tensorization and stated marginal, connectivity, and commutation-graph assumptions. It also proves the commuting-update entropy monotonicity used in the argument.
4 Contraction of entropy under the systematic scan dynamics
- Conditional entropy Ent_A(f) is the entropy remaining after fixing spins outside A, averaged over those outside configurations.The section introduces this quantity alongside standard entropy-functional properties used in the proof.Source: §4 · p. 14
4.1 Monotonicity of entropy under commuting updates: proof of Lemma 4.3
- For commuting heat-bath updates, applying the log-sum inequality proves that an update cannot increase the relevant conditional entropy.The proof uses commutation of the conditional-expectation operators; the paper includes this argument to establish Lemma 4.3.Source: §4 · p. 14, §4.1 · p. 16
4 Contraction of entropy under the systematic scan dynamics
- Under approximate tensorization of entropy, marginal boundedness, total connectedness, and maximum commutation-graph degree Δ, entropy contracts for every scan order.The result is stated for every nonnegative function.Source: §4 · p. 14
- The proof controls local entropy terms by iterating bounds across earlier scan neighbors, whose number is at most Δ.The argument assumes without loss of generality that the marginal bound b is at most 1/2.Source: §4 · p. 15