Speeding up Markov chains with deterministic jumps

DOI10.1007/s00440-020-01006-4zbMath1468.60088arXiv2004.11491OpenAlexW3089300668MaRDI QIDQ2210752

Persi Diaconis, Sourav Chatterjee

Publication date: 8 November 2020

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

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

zbMATH Keywords

Markov chainspectral gapCheeger constantmixing time

Mathematics Subject Classification ID

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

Related Items (11)

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

Cites Work

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

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