Slow mixing of Markov chains using fault lines and fat contours

DOI10.1007/s00453-008-9246-3zbMath1204.60065OpenAlexW2110278186MaRDI QIDQ603913

Sam Greenberg, Dana Randall

Publication date: 8 November 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.67.4911

zbMATH Keywords

Markov chaintriangular latticeGlauber dynamicsmixing timeindependent sets8-vertex modelslow mixing

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Related Items (4)

Sampling weighted perfect matchings on the square-octagon lattice ⋮ Sampling and Counting 3-Orientations of Planar Triangulations ⋮ Approximability of the eight-vertex model ⋮ Tunneling of the hard‐core model on finite triangular lattices

Cites Work

• Approximate counting, uniform generation and rapidly mixing Markov chains
• Bound on the mass gap for finite volume stochastic Ising models at low temperature
• Analyzing Glauber dynamics by comparison of Markov chains
• Markov Chain Algorithms for Planar Lattice Structures
• Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Slow mixing of glauber dynamics via topological obstructions
• Fast convergence of the Glauber dynamics for sampling independent sets
• On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$

This page was built for publication: Slow mixing of Markov chains using fault lines and fat contours