We give a systematic development of the application of matrix norms to rapid mixing in spin systems. We show that rapid mixing of both random update Glauber dynamics and systematic scan Glauber dynamics occurs if any matrix norm of the associated dependency matrix is less than 1. We give improved analysis for the case in which the diagonal of the dependency matrix is 0 (as in heat bath dynamics). We apply the matrix norm methods to random update and systematic scan Glauber dynamics for coloring various classes of graphs. We give a general method for estimating a norm of a symmetric nonregular matrix. This leads to improved mixing times for any class of graphs which is hereditary and sufficiently sparse including several classes of degree-bounded graphs such as nonregular graphs, trees, planar graphs and graphs with given tree-width and genus. 1. Introduction. A spin system consists of a finite set of sites and a finite set of spins. A configuration is an assignment of a spin to each site. Sites interact locally, and these interactions specify the relative likelihood of possible (local) subconfigurations. Taken together, these give a well-defined probability distribution π on the set of configurations. Glauber dynamics is a Markov chain whose states are configurations. In the transitions of the Markov chain, the spins are updated one at a time. The Markov chain converges to the stationary distribution π. During each transition of random update Glauber dynamics, a site is chosen uniformly at random and a new spin is chosen from an appropriate probability distribution (based on the local subconfiguration around the chosen site). During a transition of systematic scan Glauber dynamics, the sites are updated in a (deterministic) systematic order, one after another. Again, the updates are from an appropriate probability distribution based on the local subconfiguration.
The state of the art for general spin systems is due to Dyer, Goldberg and Jerrum REF , who prove that any systematic scan Glauber dynamics (on any graph) has O(log n) mixing time provided any matrix norm of the dependency matrix of the spin system is bounded away from 1.
Matrix norms and rapid mixing for spin systems
Annals of Applied Probability 2009, Vol. 19, No. 1, 71-107
Computer Science Mathematics