Can extra updates delay mixing?
From MaRDI portal
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)- scientific article; zbMATH DE number 7378644 (Why is no real title available?)
- Monotonicity for continuous-time random walks
- A one-dimensional coagulation-fragmentation process with a dynamical phase transition
- Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
- Cutoff for polymer pinning dynamics in the repulsive phase
- Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement
- Mixing times for the simple exclusion process with open boundaries
- Dynamics of \((2+1)\)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion
- Spectral gap and cutoff phenomenon for the Gibbs sampler of \(\nabla \varphi\) interfaces with convex potential
- Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics
- Some circumstances where extra updates can delay mixing
- Some things we've learned (about Markov chain Monte Carlo)
- Mixing time of the adjacent walk on the simplex
- Mixing times for the simple exclusion process in ballistic random environment
- Mixing time of critical Ising model on trees is polynomial in the height
- Mixing time for the asymmetric simple exclusion process in a random environment
- How quickly can we sample a uniform domino tiling of the \(2L\times 2L\) square via Glauber dynamics?
- The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions
- Mixing time for the Ising model: a uniform lower bound for all graphs
- The \(S_k\) shuffle block dynamics
- Spatial mixing and the random‐cluster dynamics on lattices
- Random-cluster dynamics on random regular graphs in tree uniqueness
- Cutoff for the cyclic adjacent transposition shuffle
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)
