Matrix norms and rapid mixing for spin systems

DOI10.1214/08-AAP532zbMath1166.15015arXivmath/0702744OpenAlexW3102205987WikidataQ56323833 ScholiaQ56323833MaRDI QIDQ1009479

Leslie Ann Goldberg, Martin Dyer, Mark R. Jerrum

Publication date: 2 April 2009

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0702744

zbMATH Keywords

Markov chainsGlauber dynamicsmatrix normspin systemsrapid mixingcoloring sparse graphs

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Coloring of graphs and hypergraphs (05C15)

Related Items

Entropy decay in the Swendsen-Wang dynamics on \(\mathbb{Z}^d\), Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics, Comparison theorems for Gibbs measures, Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs, Robustness of Markov processes on large networks, Online Discrete Optimization in Social Networks in the Presence of Knightian Uncertainty, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, On mixing of Markov chains: coupling, spectral independence, and entropy factorization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extreme eigenvalues of nonregular graphs
• Markov chain comparison
• Non-negative matrices and Markov chains. 2nd ed
• A covariance estimate for Gibbs measures
• A partial k-arboretum of graphs with bounded treewidth
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Comparison theorems for reversible Markov chains
• The largest eigenvalue of nonregular graphs
• Bounding the largest eigenvalue of trees in terms of the largest vertex degree
• Convergence properties of the Gibbs sampler for perturbations of Gaussians
• Path coupling without contraction
• Systematic scan for sampling colorings
• Eigenvectors and eigenvalues of non-regular graphs
• Improved bounds for sampling colorings
• Analyzing Glauber dynamics by comparison of Markov chains
• Facilitated Spin Models: Recent and New Results
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Fast mixing for independent sets, colorings, and other models on trees
• Probability and Computing
• Prescribing a System of Random Variables by Conditional Distributions
• Combinatorial criteria for uniqueness of Gibbs measures
• Dobrushin Conditions and Systematic Scan
• Dobrushin Conditions and Systematic Scan
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques