Speeding up Markov chains with deterministic jumps

DOI10.1007/S00440-020-01006-4zbMATH Open1468.60088OpenAlexW3089300668MaRDI QIDQ2210752FDOQ2210752

Authors Sourav Chatterjee, Persi Diaconis 

Publication date 8 November 2020

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

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

zbMATH Keywords

Markov chainCheeger constantmixing timespectral gap

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: We show that the convergence of finite state space Markov chains to stationarity can often be considerably speeded up by alternating every step of the chain with a deterministic move. Under fairly general conditions, we show that not only do such schemes exist, they are numerous.

Recommendations

• scientific article; zbMATH DE number 18982
• Some things we've learned (about Markov chain Monte Carlo)
• Characterizing limits and opportunities in speeding up Markov chain mixing
• Convergence Rates for Markov Chains
• Fastest Mixing Markov Chain on a Graph

Cites work

• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 194547 (Why is no real title available?)
• A Model for Random Random-Walks on Finite Groups
• A lower bound for the Chung-Diaconis-Graham random process
• A permuted random walk exits faster
• A survey of results on random random walks on finite groups
• Algebraic algorithms for sampling from conditional distributions
• An affine walk on the hypercube
• Analysis of a nonreversible Markov chain sampler.
• Binomial coefficient codes over GF(2)
• Cutoff on all Ramanujan graphs
• Cutoff phenomena for random walks on random regular graphs
• Diffusion and mixing in fluid flow
• Exceptional polynomials of affine type
• Hit and run as a unifying device
• Improved mixing rates of directed cycles by added connection
• Irreducibility of random polynomials of large degree
• Mixing times of random walks on dynamic configuration models
• Moderate growth and random walk on finite groups
• On sensitivity of mixing times and cutoff
• On sensitivity of uniform mixing times
• On the spectral analysis of second-order Markov chains
• Permuted random walk exits typically in linear time
• Probabilizing Fibonacci numbers
• Qualitative properties of certain piecewise deterministic Markov processes
• Random random walks on \(\mathbb{Z}_2^d\)
• Random walks arising in random number generation
• Sensitivity of mixing times
• Some simple but challenging Markov processes
• Some things we've learned (about Markov chain Monte Carlo)
• Time to Reach Stationarity in the Bernoulli–Laplace Diffusion Model

Cited in

(14)

• Random motion on finite rings. I: commutative rings
• Mixing time of fractional random walk on finite fields
• On the fastest finite Markov processes
• scientific article; zbMATH DE number 426338 (Why is no real title available?)
• Cutoff for permuted Markov chains
• The-square-and-add Markov chain
• Markov chains on finite fields with deterministic jumps
• Universality of cutoff for graphs with an added random matching
• Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022
• Fast mixing of a randomized shift-register Markov chain
• Linking the mixing times of random walks on static and dynamic random graphs
• On the multiplicative Chung-Diaconis-Graham process
• Using Bernoulli maps to accelerate mixing of a random walk on the torus
• Double Flip Move for Ising Models with Mixed Boundary Conditions

This page was built for publication: Speeding up Markov chains with deterministic jumps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2210752)