Mixing time bounds via bottleneck sequences

Louigi Addario-Berry, Matthew Roberts

Research output: Contribution to journalArticle

31 Downloads (Pure)

Abstract

We provide new upper bounds for mixing times of general finite Markov chains. We use these bounds to show that the total variation mixing time is robust under rough isometry for bounded degree graphs that are roughly isometric to trees.
Original languageEnglish
Pages (from-to)845-871
Number of pages27
JournalJournal of Statistical Physics
Volume173
Issue number3-4
Early online date11 Nov 2017
DOIs
Publication statusPublished - 1 Nov 2018

Keywords

  • Isoperimetric profile
  • Mixing times
  • Rough isometry

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics

Fingerprint Dive into the research topics of 'Mixing time bounds via bottleneck sequences'. Together they form a unique fingerprint.

Cite this