Systematic scan for sampling colorings

DOI10.1214/105051605000000683zbMATH Open1095.60024arXivmath/0603323OpenAlexW2014487253WikidataQ56323916 ScholiaQ56323916MaRDI QIDQ2494577FDOQ2494577

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)

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.

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

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

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)

Cites Work

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

Cited In (16)

• Can extra updates delay mixing?
• Frozen \((\Delta+1)\)-colourings of bounded degree graphs
• Dobrushin Conditions for Systematic Scan with Block Dynamics
• Dobrushin Conditions and Systematic Scan
• Fixed Precision MCMC Estimation by Median of Products of Averages
• 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)