Mixing time bounds via bottleneck sequences

Louigi Addario-Berry; Matthew Roberts

doi:10.1007/s10955-017-1917-5

Mixing time bounds via bottleneck sequences

Louigi Addario-Berry, Matthew Roberts

McGill University

Research output: Contribution to journal › Article › peer-review

3 Citations (SciVal)

77 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 language	English
Pages (from-to)	845-871
Number of pages	27
Journal	Journal of Statistical Physics
Volume	173
Issue number	3-4
Early online date	11 Nov 2017
DOIs	https://doi.org/10.1007/s10955-017-1917-5
Publication status	Published - 1 Nov 2018

Keywords

Isoperimetric profile
Mixing times
Rough isometry

ASJC Scopus subject areas

Statistical and Nonlinear Physics
Mathematical Physics

Access to Document

10.1007/s10955-017-1917-5

1610.07874
This is a post-peer-review, pre-copyedit version of an article published in Journal of Statistical Physics. the final authenticated version is available online at: https://doi.org/10.1007/s10955-017-1917-5.
Accepted author manuscript, 346 KB

https://arxiv.org/abs/1610.07874

Cite this

@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 = nov,

day = "1",

doi = "10.1007/s10955-017-1917-5",

language = "English",

volume = "173",

pages = "845--871",

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

SN - 0022-4715

VL - 173

SP - 845

EP - 871

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

IS - 3-4

ER -

Mixing time bounds via bottleneck sequences

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

EPSRC Posdoctoral Fellowship in Applied Probability for Dr Matthew I Roberts

Matthew Roberts

Cite this

Mixing time bounds via bottleneck sequences

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Projects

EPSRC Posdoctoral Fellowship in Applied Probability for Dr Matthew I Roberts

Profiles

Matthew Roberts

Cite this