## CHARACTERIZATION OF CUTOFF FOR REVERSIBLE MARKOV CHAINS

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 |