dc.contributor.author Basu, Riddhipratim dc.contributor.author Hermon, Jonathan dc.contributor.author Peres, Yuval dc.date.accessioned 2018-03-19T11:17:14Z dc.date.available 2018-03-19T11:17:14Z dc.date.issued 2017-05 dc.identifier.issn 0091-1798 dc.identifier.uri https://www.repository.cam.ac.uk/handle/1810/274077 dc.description.abstract A sequence of Markov chains is said to exhibit (total variation) cutoff if the convergence to stationarity in total variation distance is abrupt. We consider reversible lazy chains. We prove a necessary and sufficient condition for the occurrence of the cutoff phenomena in terms of concentration of hitting time of "worst" (in some sense) sets of stationary measure at least $\alpha$, for some $\alpha \in (0,1)$. We also give general bounds on the total variation distance of a reversible chain at time $t$ in terms of the probability that some "worst" set of stationary measure at least $\alpha$ was not hit by time $t$. As an application of our techniques we show that a sequence of lazy Markov chains on finite trees exhibits a cutoff iff the ratio of their relaxation-times and their (lazy) mixing-times tends to 0. dc.publisher Institute of Mathematical Statistics dc.subject Cutoff dc.subject mixing-time dc.subject finite reversible Markov chains dc.subject hitting times dc.subject trees dc.subject maximal inequality dc.title CHARACTERIZATION OF CUTOFF FOR REVERSIBLE MARKOV CHAINS dc.type Article prism.endingPage 1487 prism.issueIdentifier 3 prism.publicationDate 2017 prism.publicationName ANNALS OF PROBABILITY prism.startingPage 1448 prism.volume 45 dc.identifier.doi 10.17863/CAM.21164 rioxxterms.versionofrecord 10.1214/16-AOP1090 rioxxterms.version AM rioxxterms.licenseref.uri http://www.rioxx.net/licenses/all-rights-reserved rioxxterms.licenseref.startdate 2017-05 dc.contributor.orcid Hermon, Jonathan [0000-0002-2935-3999] dc.publisher.url http://dx.doi.org/10.1214/16-AOP1090 rioxxterms.type Journal Article/Review rioxxterms.freetoread.startdate 2018-05-15
﻿