MATRIX NORMS AND RAPID MIXING FOR SPIN SYSTEMS

• 成果类型: Article
• 署名作者: Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
• 署名单位: University of Leeds; University of Liverpool; University of London
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/08-AAP532
• 发表日期: 2009
• 页码: 71-107
• 关键词: eigenvalues; uniqueness; colorings; models; scan

摘要

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 or 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 asymmetric 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.