A general lower bound for mixing of single-site dynamics on graphs

DOI10.1214/105051607000000104zbMath1125.60075arXivmath/0507517OpenAlexW3098791681MaRDI QIDQ2456048

Thomas P. Hayes, Alistair Sinclair

Publication date: 17 October 2007

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

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

zbMATH Keywords

Glauber dynamicsmixing timespin systemsMarkov random fields

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Random-cluster dynamics in \(\mathbb {Z}^2\), Entropy decay in the Swendsen-Wang dynamics on \(\mathbb{Z}^d\), Randomly coloring planar graphs with fewer colors than the maximum degree, Rigorous inequalities between length and time scales in glassy systems, Phase transition for the mixing time of the Glauber dynamics for coloring regular trees, Exact thresholds for Ising-Gibbs samplers on general graphs, Mixing time for the Ising model: a uniform lower bound for all graphs, Unnamed Item, On the dynamics of the glass transition on Bethe lattices, Mixing time and simulated annealing for the stochastic cellular automata, Cutoff for General Spin Systems with Arbitrary Boundary Conditions, Randomly coloring constant degree graphs, Dynamic Sampling from Graphical Models, On mixing of Markov chains: coupling, spectral independence, and entropy factorization

Cites Work

• Unnamed Item
• Unnamed Item
• Approach to equilibrium of Glauber dynamics in the one phase region. I: The attractive case
• A note on the Glauber dynamics for sampling independent sets
• Systematic scan for sampling colorings
• Logarithmic Sobolev inequalities for finite Markov chains
• An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings
• Improved bounds for sampling colorings
• On Counting Independent Sets in Sparse Graphs
• Generating a random permutation with random transpositions
• Mixing in time and space for lattice spin systems: A combinatorial view
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
• LATIN 2004: Theoretical Informatics