CHARACTERIZATION OF CUTOFF FOR REVERSIBLE MARKOV CHAINS
| cam.issuedOnline | 2017-05-01 | |
| dc.contributor.author | Basu, Riddhipratim | |
| dc.contributor.author | Hermon, Jonathan | |
| dc.contributor.author | Peres, Yuval | |
| dc.contributor.orcid | Hermon, Jonathan [0000-0002-2935-3999] | |
| dc.date.accessioned | 2018-03-19T11:17:14Z | |
| dc.date.available | 2018-03-19T11:17:14Z | |
| dc.date.issued | 2017 | |
| 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.identifier.doi | 10.17863/CAM.21164 | |
| dc.identifier.issn | 0091-1798 | |
| dc.identifier.uri | https://www.repository.cam.ac.uk/handle/1810/274077 | |
| dc.language.iso | eng | |
| dc.publisher | Institute of Mathematical Statistics | |
| dc.publisher.url | http://dx.doi.org/10.1214/16-AOP1090 | |
| 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 | |
| rioxxterms.licenseref.startdate | 2017-05 | |
| rioxxterms.licenseref.uri | http://www.rioxx.net/licenses/all-rights-reserved | |
| rioxxterms.type | Journal Article/Review | |
| rioxxterms.version | AM | |
| rioxxterms.versionofrecord | 10.1214/16-AOP1090 |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- cutoffAOPrevision10Jan2016.pdf
- Size:
- 517.59 KB
- Format:
- Adobe Portable Document Format
- Description:
- Accepted version
- Licence
- http://www.rioxx.net/licenses/all-rights-reserved
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- DepositLicenceAgreement.pdf
- Size:
- 417.78 KB
- Format:
- Adobe Portable Document Format