Show simple item record

dc.contributor.authorBasu, Riddhipratim
dc.contributor.authorHermon, Jonathan
dc.contributor.authorPeres, Yuval
dc.date.accessioned2018-03-19T11:17:14Z
dc.date.available2018-03-19T11:17:14Z
dc.date.issued2017-05
dc.identifier.issn0091-1798
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/274077
dc.description.abstractA 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.publisherInstitute of Mathematical Statistics
dc.subjectCutoff
dc.subjectmixing-time
dc.subjectfinite reversible Markov chains
dc.subjecthitting times
dc.subjecttrees
dc.subjectmaximal inequality
dc.titleCHARACTERIZATION OF CUTOFF FOR REVERSIBLE MARKOV CHAINS
dc.typeArticle
prism.endingPage1487
prism.issueIdentifier3
prism.publicationDate2017
prism.publicationNameANNALS OF PROBABILITY
prism.startingPage1448
prism.volume45
dc.identifier.doi10.17863/CAM.21164
rioxxterms.versionofrecord10.1214/16-AOP1090
rioxxterms.versionAM
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserved
rioxxterms.licenseref.startdate2017-05
dc.contributor.orcidHermon, Jonathan [0000-0002-2935-3999]
dc.publisher.urlhttp://dx.doi.org/10.1214/16-AOP1090
rioxxterms.typeJournal Article/Review
rioxxterms.freetoread.startdate2018-05-15


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record