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

graph homomorphismsmixing timePotts modelspin systemsGlauber dynamics

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15) 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.

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

• 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?)
• 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
• 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

(16)

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

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)