Bounds on lifting continuous-state Markov chains to speed up mixing

DOI10.1007/S10959-017-0745-5zbMATH Open1404.60101arXiv1606.03161OpenAlexW2963723050MaRDI QIDQ1800950FDOQ1800950

Authors: Yanyan Li 

Publication date: 26 October 2018

Published in: Journal of Theoretical Probability (Search for Journal in Brave)

Abstract: It is often possible to speed up the mixing of a Markov chain ${X_t}_{tinmathbbN}$ on a state space $Omega$ by extit{lifting}, that is, running a more efficient Markov chain ${hat{X}_t}_{tinmathbbN}$ on a larger state space $hatOmegasupsetOmega$ that projects to ${X_t}_{tinmathbbN}$ in a certain sense. In [CLP99], Chen, Lov{'a}sz and Pak prove that for Markov chains on finite state spaces, the mixing time of any lift of a Markov chain is at least the square root of the mixing time of the original chain, up to a factor that depends on the stationary measure. Unfortunately, this extra factor makes the bound in [CLP99] very loose for Markov chains on large state spaces and useless for Markov chains on continuous state spaces. In this paper, we develop an extension of the evolving set method that allows us to refine this extra factor and find bounds for Markov chains on continuous state spaces that are analogous to the bounds in [CLP99]. These bounds also allow us to improve on the bounds in [CLP99] for some chains on finite state spaces.

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

Recommendations

• Lifting Markov chains to speed up mixing
• Liftings of tree-structured Markov chains (extended abstract)
• Characterizing limits and opportunities in speeding up Markov chain mixing
• Mixing and hitting times for finite Markov chains
• Evolving sets, mixing and heat kernel bounds

zbMATH Keywords

Markov chainliftmixing timeconductancenonreversible

Mathematics Subject Classification ID

Discrete-time Markov processes on general state spaces (60J05)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• Analysis of a nonreversible Markov chain sampler.
• On Choosing and Bounding Probability Metrics
• The Markov chain Monte Carlo revolution
• On the spectral analysis of second-order Markov chains
• Lifting Markov chains to speed up mixing
• Evolving sets, mixing and heat kernel bounds
• Mixing times are hitting times of large sets
• Random rotations: Characters and random walks on \(SO(N)\)

Cited In (4)

• Lifting Markov chains to speed up mixing
• Liftings of tree-structured Markov chains (extended abstract)
• Characterizing limits and opportunities in speeding up Markov chain mixing
• On the convergence time of some non-reversible Markov chain Monte Carlo methods

This page was built for publication: Bounds on lifting continuous-state Markov chains to speed up mixing

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