Tech Reports

ULCS-08-003

On Systematic Scan (PhD Thesis)

Kasper Pedersen

Abstract

In this thesis we study the mixing time of systematic scan Markov chains on finite spin systems. A systematic scan Markov chain is a Markov chain which updates the sites in a deterministic order and this type of Markov chain is often seen as intuitively appealing in terms of implementation to scientists conducting experimental work. Until recently systematic scan Markov chains have largely resisted analysis and a gap in the parameters that imply rapid mixing has developed between systematic scan Markov chains and the more frequently studied random update Markov chains. We reduce this gap in this thesis by improving the parameters for which systematic scan mixes when applied to several well-known spin systems.

The main contribution of this thesis is the introduction of a new technique for proving rapid mixing of systematic scan Markov chains. It is known that, in a single-site setting, the mixing time of systematic scan can be bounded in terms of the influence that sites have on each other. We generalise this technique for bounding the mixing time of systematic scan to block dynamics, a setting in which a (constant size) set of sites are updated simultaneously. In particular we introduce a parameter corresponding to the maximum influence on any site and show that if this parameter is sufficiently small, then the corresponding systematic scan Markov chain mixes rapidly.

We present several applications of this new proof technique. In particular we show that systematic scan mixes rapidly on spin systems corresponding to proper q-colourings of (1) general graphs, (2) trees, and (3) the grid for improved parameters than were previously known. We also obtain rapid mixing of systematic scan Markov chains for sampling H-colourings of the n-vertex path for a restricted family of H using this technique. The H-colouring result is extended to general graphs H by placing more restrictions on the scan and using path coupling, a well-established technique for bounding mixing times of Markov chains. Path coupling is also used to prove rapid mixing of a single-site systematic scan for sampling proper q-colourings of bipartite graphs.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.