Glauber dynamics on trees and hyperbolic graphs

• 成果类型: Article
• 署名作者: Berger, N; Kenyon, C; Mossel, E; Peres, Y
• 署名单位: University of California System; University of California Berkeley; Centre National de la Recherche Scientifique (CNRS); Universite Paris Saclay
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-004-0369-4
• 发表日期: 2005
• 页码: 311-340
• 关键词: markov-chains; ising-model; reconstruction; number; state

摘要

We study continuous time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap \lambda(1) - lambda(2)\) for the dynamics on trees and on planar hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that for general graphs, if the relaxation time tau(2) satisfies tau(2) = O(1), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.