Dyer, Martin, Goldberg, Leslie Ann and Jerrum, Mark (2006) Dobrushin conditions and systematic scan. In: 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/10th International Workshop on Randomization and Computation, Barcelona, Spain, 28-30 Aug 2006. Published in: Lecture Notes in Computer Science, Volume 4110 pp. 327-338. ISBN 3-540-38044-2. ISSN 0302-9743.

Full text not available from this repository, contact author.

Request Changes to record.

Abstract

We consider Glauber dynamics on finite spin systems. The mixing time of Glauber dynamics can be bounded in terms of the influences of sites on each other. We consider three parameters bounding these influences - alpha, the total influence on a site, as studied by Dobrushin; alpha', the total influence of a site, as studied by Dobrushin and Shlosman; and alpha", the total influence of a site in any given context, which is related to the path-coupling method of Bubley and Dyer. It is known that if any of these parameters is less than 1 then random-update Glauber dynamics (in which a randomly-chosen site is updated at each step) is rapidly mixing. It is also known that the Dobrushin condition alpha < 1 implies that systematic-scan Glauber dynamics (in which sites are updated in a deterministic order) is rapidly mixing. This paper studies two related issues, primarily in the context of systematic scan: (1) the relationship between the parameters alpha, alpha' and alpha", and (2) the relationship between proofs of rapid mixing using Dobrushin uniqueness (which typically use analysis techniques) and proofs of rapid mixing using path coupling. We use matrix-balancing to show that the Dobrushin-Shlosman condition alpha' < 1 implies rapid mixing of systematic scan. An interesting question is whether the rapid mixing results for scan can be extended to the alpha = 1 or alpha' = 1 case. We give positive results for the rapid mixing of systematic scan for certain alpha = 1 cases. As an application, we show rapid mixing of systematic scan (for any scan order) for heat-bath Glauber dynamics for proper q-colourings of a degree-Delta graph G when q >= 2 Delta.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Series Name:	LECTURE NOTES IN COMPUTER SCIENCE
Journal or Publication Title:	Lecture Notes in Computer Science
Publisher:	Springer
ISBN:	3-540-38044-2
ISSN:	0302-9743
Editor:	Draz, J and Jansen, K and Rolim, JDP and Zwick, U
Official Date:	2006
Dates:	Date Event 2006 Published
Volume:	Volume 4110
Number of Pages:	12
Page Range:	pp. 327-338
Status:	Not Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/10th International Workshop on Randomization and Computation
Type of Event:	Workshop
Location of Event:	Barcelona, Spain
Date(s) of Event:	28-30 Aug 2006

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