Systematic scan for sampling colorings

DOI10.1214/105051605000000683MaRDI QIDQ2494577zbMATH OpenOpenAlexWikidataFDO

Authors Leslie Ann Goldberg, Martin Dyer, Mark Jerrum

Publication date 29 June 2006

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0603323

zbMATH Keywords

Glauber dynamicsgraph homomorphismsmixing timePotts modelspin systems

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: We address the problem of sampling colorings of a graph $G$ by Markov chain simulation. For most of the article we restrict attention to proper $q$-colorings of a path on $n$ vertices (in statistical physics terms, the one-dimensional $q$-state Potts model at zero temperature), though in later sections we widen our scope to general ``$H$-colorings of arbitrary graphs $G$. Existing theoretical analyses of the mixing time of such simulations relate mainly to a dynamics in which a random vertex is selected for updating at each step. However, experimental work is often carried out using systematic strategies that cycle through coordinates in a deterministic manner, a dynamics sometimes known as systematic scan. The mixing time of systematic scan seems more difficult to analyze than that of random updates, and little is currently known. In this article we go some way toward correcting this imbalance. By adapting a variety of techniques, we derive upper and lower bounds (often tight) on the mixing time of systematic scan. An unusual feature of systematic scan as far as the analysis is concerned is that it fails to be time reversible.

Review text

The systematic scan for some spin system is studied. The most part of the paper is devoted to proper \(q\)-colorings of a path of \(n\) vertices (the one-dimensional \(q\)-state Potts model at zero temperature). Tight (i.e., matching within a constant factor) upper and lower bounds on mixing time are provided. Measuring mixing time in terms of the number of updates of individual vertices (so that one scan equal to \(n\) updates), the authors show that when \(q=3,\) mixing occurs in \(\Theta(n^3\log n)\) updates, whether Glauber dynamics or systematic scan is used; while when \(q\geq 4\), mixing occurs in \(\Theta(n\log n)\) updates, again independently of whether Glauber or scan is used. Also for ``\(H\)-colorings model arbitrary spin systems with symmetric ``hard constraints it is shown that for any \(H\), Glauber mixes in \(O(n^5)\) updates and scan in \(O(n^6)\) updates.

Recommendations

• On systematic scan for sampling H-colorings of the path
• Dobrushin Conditions for Systematic Scan with Block Dynamics
• A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID
• Dobrushin Conditions and Systematic Scan
• Dobrushin Conditions and Systematic Scan

Cites work

• A uniqueness condition for Gibbs measures, with application to the 2- dimensional Ising antiferromagnet
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• An extension of path coupling and its application to the Glauber dynamics for graph colorings
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Comparison theorems for reversible Markov chains
• Convergence properties of the Gibbs sampler for perturbations of Gaussians
• Coordinate selection rules for Gibbs sampling
• Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
• Geometric bounds for eigenvalues of Markov chains
• scientific article; zbMATH DE number 48363 (Why is no real title available?)
• scientific article; zbMATH DE number 2151251 (Why is no real title available?)
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Markov chain algorithms for planar lattice structures
• Markov chain comparison
• Mixing times of lozenge tiling and card shuffling Markov chains
• Mixing times of the biased card shuffling and the asymmetric exclusion process
• On Counting Independent Sets in Sparse Graphs
• On Markov chains for randomly H-coloring a graph
• Random sampling of 3‐colorings in ℤ²
• Some Inequalities for Reversible Markov Chains
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• Time-Dependent Statistics of the Ising Model
• Weighted sums of certain dependent random variables

Cited in

(20)

• Matrix norms and rapid mixing for spin systems
• Frozen colourings of bounded degree graphs
• What can be sampled locally?
• Hit and run as a unifying device
• A general lower bound for mixing of single-site dynamics on graphs
• On systematic scan for sampling H-colorings of the path
• The Glauber dynamics for edge-colorings of trees
• Dobrushin Conditions for Systematic Scan with Block Dynamics
• A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID
• Can extra updates delay mixing?
• Frozen (+1)-colourings of bounded degree graphs
• Fixed Precision MCMC Estimation by Median of Products of Averages
• Phase coexistence and torpid mixing in the 3-coloring model on \({\mathbb Z}^d\)
• Dobrushin Conditions and Systematic Scan
• Dobrushin Conditions and Systematic Scan
• Some circumstances where extra updates can delay mixing
• Rapid mixing of global Markov chains via spectral independence: the unbounded degree case
• Expanderizing higher-order random walks
• Expanderizing higher-order random walks
• Optimal mixing for randomly sampling edge colorings on trees down to the max degree

This page was built for publication: Systematic scan for sampling colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2494577)