Mixing time bounds via bottleneck sequences

Louigi Addario-Berry, Matthew Roberts

Research output: Contribution to journalArticle

12 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)1-27
Number of pages27
JournalJournal of Statistical Physics
Volume173
Issue number3-4
Early online date11 Nov 2017
DOIs
Publication statusPublished - 1 Nov 2018

Fingerprint

Mixing Time
Markov chains
Total Variation
Isometric
Isometry
Rough
Markov chain
Upper bound
Graph in graph theory

Keywords

  • Isoperimetric profile
  • Mixing times
  • Rough isometry

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics

Cite this

Mixing time bounds via bottleneck sequences. / Addario-Berry, Louigi; Roberts, Matthew.

In: Journal of Statistical Physics, Vol. 173, No. 3-4, 01.11.2018, p. 1-27.

Research output: Contribution to journalArticle

Addario-Berry, Louigi ; Roberts, Matthew. / Mixing time bounds via bottleneck sequences. In: Journal of Statistical Physics. 2018 ; Vol. 173, No. 3-4. pp. 1-27.
@article{0b949d8b9d714f4fb730e426bb9d6a16,
title = "Mixing time bounds via bottleneck sequences",
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.",
keywords = "Isoperimetric profile, Mixing times, Rough isometry",
author = "Louigi Addario-Berry and Matthew Roberts",
year = "2018",
month = "11",
day = "1",
doi = "10.1007/s10955-017-1917-5",
language = "English",
volume = "173",
pages = "1--27",
journal = "Journal of Statistical Physics",
issn = "0022-4715",
publisher = "Springer New York",
number = "3-4",

}

TY - JOUR

T1 - Mixing time bounds via bottleneck sequences

AU - Addario-Berry, Louigi

AU - Roberts, Matthew

PY - 2018/11/1

Y1 - 2018/11/1

N2 - 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.

AB - 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.

KW - Isoperimetric profile

KW - Mixing times

KW - Rough isometry

UR - http://www.scopus.com/inward/record.url?scp=85033441213&partnerID=8YFLogxK

U2 - 10.1007/s10955-017-1917-5

DO - 10.1007/s10955-017-1917-5

M3 - Article

VL - 173

SP - 1

EP - 27

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

SN - 0022-4715

IS - 3-4

ER -