The Dobrushin condition states that every row sum of the influence matrix is less than 1 - ε, where &epsilon > 0. This criterion implies rapid convergence (O(n log n) mixing time) of the single-site (Glauber) dynamics for a spin system, as well as uniqueness of the Gibbs measure. The dual condition that every column sum of the influence matrix is less than 1 - ε has also been shown to imply the same conclusions.
We examine a common generalization of these conditions, namely that the maximum eigenvalue of the influence matrix is less than 1 - ε. Our main result is that this condition implies O(n log n) mixing time for the Glauber dynamics.
As applications, we consider the Ising model, hard-core lattice gas model, and graph colorings, relating the mixing time of the Glauber dynamics to the maximum eigenvalue for the adjacency matrix of the graph. For the special case of planar graphs, this leads to improved bounds on mixing time with quite simple proofs.
|FOCS proceedings version, last modified Aug 15, 2006.||(Please email me if you have trouble viewing.)|