Bounds on Lifting Continuous-State Markov Chains to Speed Up Mixing

Kavita Ramanan and Aaron Smith ()
Additional contact information
Kavita Ramanan: Brown University
Aaron Smith: University of Ottawa

Journal of Theoretical Probability, 2018, vol. 31, issue 3, 1647-1678

Abstract: Abstract It is often possible to speed up the mixing of a Markov chain $$\{ X_{t} \}_{t \in \mathbb {N}}$$ { X t } t ∈ N on a state space $$\Omega $$ Ω by lifting, that is, running a more efficient Markov chain $$\{ \widehat{X}_{t} \}_{t \in \mathbb {N}}$$ { X ^ t } t ∈ N on a larger state space $$\hat{\Omega } \supset \Omega $$ Ω ^ ⊃ Ω that projects to $$\{ X_{t} \}_{t \in \mathbb {N}}$$ { X t } t ∈ N in a certain sense. Chen et al. (Proceedings of the 31st annual ACM symposium on theory of computing. ACM, 1999) 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 of $$\{X_t\}_{t \in \mathbb {N}}$$ { X t } t ∈ N . Unfortunately, this extra factor makes the bound in Chen et al. (1999) 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 Chen et al. (1999). These bounds also allow us to improve on the bounds in Chen et al. (1999) for some chains on finite state spaces.

Keywords: Markov chain; Nonreversible; Lift; Mixing time; Conductance; 60J05 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-017-0745-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:31:y:2018:i:3:d:10.1007_s10959-017-0745-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-017-0745-5

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().