Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
From MaRDI portal
Publication:2428505
DOI10.1007/s00440-010-0329-0zbMath1250.60034arXiv1011.3058OpenAlexW2152708178MaRDI QIDQ2428505
Prasad Tetali, Jennifer T. Chayes, Christian Borgs
Publication date: 26 April 2012
Published in: Probability Theory and Related Fields (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1011.3058
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) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Random-cluster dynamics in \(\mathbb {Z}^2\), Entropy decay in the Swendsen-Wang dynamics on \(\mathbb{Z}^d\), Mixing of the Glauber dynamics for the ferromagnetic Potts model, The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions, Algorithmic Pirogov-Sinai theory, Exponentially slow mixing in the mean-field Swendsen-Wang dynamics, Random-cluster dynamics in \(\mathbb{Z}^2\): rapid mixing with general boundary conditions, Efficient sampling and counting algorithms for the Potts model on ℤd at all temperatures, Cutoff for the Swendsen-Wang dynamics on the lattice, Sampling from the low temperature Potts model through a Markov chain on flows, Spatial mixing and the random‐cluster dynamics on lattices, Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022, Low-temperature Ising dynamics with random initializations, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Unnamed Item, Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics, Unnamed Item, Large scale stochastic dynamics. Abstracts from the workshop held September 15--21, 2019, Swendsen‐Wang algorithm on the mean‐field Potts model, Glauber dynamics for the mean-field Potts model, Tunneling behavior of Ising and Potts models in the low-temperature regime, Comparison of Swendsen-Wang and heat-bath dynamics, Rapid mixing of Swendsen–Wang dynamics in two dimensions, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Interfaces in the Potts model. I: Pirogov-Sinai theory of the Fortuin- Kasteleyn representation
- Faster mixing and small bottlenecks
- Approximate counting, uniform generation and rapidly mixing Markov chains
- A unified approach to phase diagrams in field theory and statistical mechanics
- Edge-isoperimetric inequalities in the grid
- Relaxation to equilibrium for two dimensional disordered Ising systems in the Griffiths phase
- On the mixing time of a simple random walk on the super critical percolation cluster
- Glauber dynamics on trees and hyperbolic graphs
- Bound on the mass gap for finite volume stochastic Ising models at low temperature
- Discontinuity of the magnetization in one-dimensional \(1/| x-y| ^ 2\) Ising and Potts models.
- The Swendsen-Wang process does not always mix rapidly
- Mixing properties of the Swendsen–Wang process on the complete graph and narrow grids
- Lifting Markov chains to speed up mixing
- On Counting Independent Sets in Sparse Graphs
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
- Mathematical Aspects of Mixing Times in Markov Chains
