Elementary bounds on mixing times for decomposable Markov chains

Natesh S. Pillai and Aaron Smith

Stochastic Processes and their Applications, 2017, vol. 127, issue 9, 3068-3109

Abstract: Many finite-state reversible Markov chains can be naturally decomposed into “projection” and “restriction” chains. In this paper we provide bounds on the total variation mixing times of the original chain in terms of the mixing properties of these related chains. This paper is in the tradition of existing bounds on Poincaré and log-Sobolev constants of Markov chains in terms of similar decompositions (Jerrum et al., 2004; Madras and Randall, 2002; Martin and Randall, 2006; Madras and Yuen, 2009). Our proofs are simple, relying largely on recent results relating hitting and mixing times of reversible Markov chains (Peres and Sousi, 2013; Oliveira, 2012). We describe situations in which our results give substantially better bounds than those obtained by applying existing decomposition results and provide examples for illustration.

Keywords: Spectral gap; Mixing time; Markov chain; Decomposition of Markov chain (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S030441491730025X
Full text for ScienceDirect subscribers only

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:eee:spapps:v:127:y:2017:i:9:p:3068-3109

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2017.02.002

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().