Speeding up Markov chains with deterministic jumps

DOI10.1007/S00440-020-01006-4zbMATH Open1468.60088arXiv2004.11491OpenAlexW3089300668MaRDI 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)

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.

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

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

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)

Cites Work

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

Cited In (12)

• Fast mixing of a randomized shift-register Markov chain
• Cutoff for permuted Markov chains
• The-square-and-add Markov chain
• Double Flip Move for Ising Models with Mixed Boundary Conditions
• On the multiplicative Chung-Diaconis-Graham process
• Using Bernoulli maps to accelerate mixing of a random walk on the torus
• Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022
• Title not available (Why is that?)
• Mixing time of fractional random walk on finite fields
• Markov chains on finite fields with deterministic jumps
• Universality of cutoff for graphs with an added random matching
• Linking the mixing times of random walks on static and dynamic random graphs

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)