Informatics Report Series
Report
 EDI-INF-RR-0479
 Related Pages Report (by Number) Index Report (by Date) Index Author Index Institute Index Home
Title:Systematic scan for sampling colourings
Authors: Martin Dyer ; Leslie Ann Goldberg ; Mark Jerrum
Date: 2006
Publication Title:Annals of Applied Probability
Publisher:The Institute of Mathematical Statistics
Publication Type:Journal Article Publication Status:Published
Volume No:# 16(1) Page Nos:185-230
DOI:10.1214/105051605000000683
Abstract:
We address the problem of sampling colourings of a graph~$G$ by Markov chain simulation. For most of the article we restrict attention to proper $q$-colourings of a path on $n$~vertices (in statistical physics terms, the $1$-dimensional $q$-state Potts model at zero temperature), though in later sections we widen our scope to general $H$-colourings'' 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 {\it systematic scan}. The mixing time of systematic scan seems more difficult to analyse than that of random updates, and little is currently known. In this article, we go some way towards 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.
Bibtex format
@Article{EDI-INF-RR-0479,
author = { Martin Dyer and Leslie Ann Goldberg and Mark Jerrum },
title = {Systematic scan for sampling colourings},
journal = {Annals of Applied Probability},
publisher = {The Institute of Mathematical Statistics},
year = 2006,
volume = {# 16(1)},
pages = {185-230},
doi = {10.1214/105051605000000683},
url = {http://dx.doi.org/10.1214/105051605000000683},
}

 Please mail with any changes or corrections. Unless explicitly stated otherwise, all material is copyright The University of Edinburgh