The Library
Geometric bounds on the fastest mixing Markov chain
Tools
Olesker-Taylor, Sam and Zanetti, Luca (2024) Geometric bounds on the fastest mixing Markov chain. Probability Theory and Related Fields . doi:10.1007/s00440-023-01257-x ISSN 0178-8051. (In Press)
|
PDF
s00440-023-01257-x.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (667Kb) | Preview |
|
PDF
WRAP-Geometric-bounds-fastest-mixing-Markov-chain-23.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (650Kb) |
Official URL: https://doi.org/10.1007/s00440-023-01257-x
Abstract
In the Fastest Mixing Markov Chain problem, we are given a graph G=(V,E) and desire the discrete-time Markov chain with smallest mixing time τ subject to having equilibrium distribution uniform on V and non-zero transition probabilities only across edges of the graph.
It is well-known that the mixing time τRW of the lazy random walk on G is characterised by the edge conductance Φ of G via Cheeger’s inequality: Φ^-1<~τRW<~Φ^-2log|V|. Analogously, we characterise the fastest mixing time τ* via a Cheeger-type inequality but for a different geometric quantity, namely the vertex conductance Ψ of G: Ψ^-1<~τ*<~Ψ^-2(log|V|)^2.
This characterisation forbids fast mixing for graphs with small vertex conductance. To bypass this fundamental barrier, we consider Markov chains on G with equilibrium distribution which need not be uniform, but rather only ε-close to uniform in total variation. We show that it is always possible to construct such a chain with mixing time τ<~ε^-1(diamG)^2log|V|.
Finally, we discuss analogous questions for continuous-time and time-inhomogeneous chains.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Statistics | ||||||
Library of Congress Subject Headings (LCSH): | Random walks (Mathematics), Markov processes | ||||||
Journal or Publication Title: | Probability Theory and Related Fields | ||||||
Publisher: | Springer | ||||||
ISSN: | 0178-8051 | ||||||
Official Date: | 30 January 2024 | ||||||
Dates: |
|
||||||
DOI: | 10.1007/s00440-023-01257-x | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | In Press | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 13 December 2023 | ||||||
Date of first compliant Open Access: | 31 January 2024 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year