Geometric Bounds on the Fastest Mixing Markov Chain

Sam Olesker-Taylor, Luca Zanetti

Research output: Working paper / PreprintPreprint

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 . Φ −2 log |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 (diam G) 2 log |V |. Finally, we discuss analogous questions for continuous-time and time-inhomogeneous chains. Keywords: mixing time, random walks, conductance, fastest mixing Markov chain
Original languageEnglish
PublisherarXiv
Pages1-31
Number of pages31
Publication statusSubmitted - 10 Nov 2021

Publication series

NameProbability Theory and Related Fields
PublisherSpringer New York
ISSN (Print)0178-8051

Bibliographical note

Funding information:
SOT was supported by EPSRC grant EP/N004566/1.

Fingerprint

Dive into the research topics of 'Geometric Bounds on the Fastest Mixing Markov Chain'. Together they form a unique fingerprint.

Cite this