The Library
Systematic scan for sampling colorings
Tools
UNSPECIFIED (2006) Systematic scan for sampling colorings. ANNALS OF APPLIED PROBABILITY, 16 (1). pp. 185-230. doi:10.1214/105051605000000683 ISSN 1050-5164.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1214/105051605000000683
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Journal or Publication Title: | ANNALS OF APPLIED PROBABILITY | ||||
Publisher: | INST MATHEMATICAL STATISTICS | ||||
ISSN: | 1050-5164 | ||||
Official Date: | February 2006 | ||||
Dates: |
|
||||
Volume: | 16 | ||||
Number: | 1 | ||||
Number of Pages: | 46 | ||||
Page Range: | pp. 185-230 | ||||
DOI: | 10.1214/105051605000000683 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |