Abstract: We consider Glauber dynamics (starting from an extremal configuration) in a monotone spin system, and show that interjecting extra updates cannot increase the expected Hamming distance or the total variation distance to the stationary distribution. We deduce that for monotone Markov random fields, when block dynamics contracts a Hamming metric, single-site dynamics mixes in O(n log n) steps on an n-vertex graph. In particular, our result completes work of Kenyon, Mossel and Peres concerning Glauber dynamics for the Ising model on trees. Our approach also shows that on bipartite graphs, alternating updates systematically between odd and even vertices cannot improve the mixing time by more than a factor of log n compared to updates at uniform random locations on an n-vertex graph. Our result is especially effective in comparing block and single-site dynamics; it has already been used in works of Martinelli, Sinclair, Mossel, Sly, Ding, Lubetzky, and Peres in various combinations.
Recommendations
- Some circumstances where extra updates can delay mixing
- A general lower bound for mixing of single-site dynamics on graphs
- Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
- Dobrushin Conditions for Systematic Scan with Block Dynamics
- Dobrushin Conditions and Systematic Scan
Cites work
- scientific article; zbMATH DE number 2042289 (Why is no real title available?)
- scientific article; zbMATH DE number 1418384 (Why is no real title available?)
- scientific article; zbMATH DE number 3892344 (Why is no real title available?)
- Approach to equilibrium of Glauber dynamics in the one phase region. I: The attractive case
- Dobrushin Conditions and Systematic Scan
- Exact thresholds for Ising-Gibbs samplers on general graphs
- Glauber dynamics on the cycle is monotone
- Glauber dynamics on trees and hyperbolic graphs
- Glauber dynamics on trees: Boundary conditions and mixing time
- Mixing in time and space for lattice spin systems: A combinatorial view
- Mixing time for the Ising model: a uniform lower bound for all graphs
- Mixing time for the solid-on-solid model
- Mixing time of critical Ising model on trees is polynomial in the height
- On the mixing time of the 2D stochastic Ising model with ``Plus boundary conditions at low temperature
- Random sampling for the monomer-dimer model on a lattice.
- Some circumstances where extra updates can delay mixing
- Systematic scan for sampling colorings
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
Cited in
(23)- Mixing time of the adjacent walk on the simplex
- Mixing time for the asymmetric simple exclusion process in a random environment
- Mixing time of critical Ising model on trees is polynomial in the height
- Cutoff for the cyclic adjacent transposition shuffle
- Dynamics of (2+1)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion
- Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement
- Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
- Mixing time for the Ising model: a uniform lower bound for all graphs
- A one-dimensional coagulation-fragmentation process with a dynamical phase transition
- Monotonicity for continuous-time random walks
- Mixing times for the simple exclusion process in ballistic random environment
- Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics
- scientific article; zbMATH DE number 7378644 (Why is no real title available?)
- Mixing times for the simple exclusion process with open boundaries
- Spectral gap and cutoff phenomenon for the Gibbs sampler of \(\nabla \varphi\) interfaces with convex potential
- The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions
- Random-cluster dynamics on random regular graphs in tree uniqueness
- The \(S_k\) shuffle block dynamics
- Some things we've learned (about Markov chain Monte Carlo)
- Cutoff for polymer pinning dynamics in the repulsive phase
- How quickly can we sample a uniform domino tiling of the \(2L\times 2L\) square via Glauber dynamics?
- Some circumstances where extra updates can delay mixing
- Spatial mixing and the random‐cluster dynamics on lattices
This page was built for publication: Can extra updates delay mixing?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q378052)
