Geometric Bounds on the Fastest Mixing Markov Chain

Sam Olesker-Taylor, Luca Zanetti

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

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 [Boyd et al., 2004].
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|. Edge conductance, however, fails to characterise the fastest mixing time τ^⋆ of G. Take, for example, a graph consisting of two n-vertex cliques connected by a perfect matching: its edge conductance is Θ(1/n), while τ^⋆ can be shown to be O(log n). We show, instead, that is possible to 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. We prove this result by first relating vertex conductance to a new expansion measure, which we call matching conductance. We then relate matching conductance to a variational characterisation of τ^⋆ (or, more precisely, of the fastest relaxation time) due to Roch [Roch, 2005]. This is done by interpreting Roch’s characterisation as a particular instance of fractional vertex cover, which is dual to fractional matching. We believe matching conductance to be of independent interest and might have further applications in studying connectivity properties of graphs.
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 call such chains almost mixing. We show that it is always possible to construct an almost mixing chain with mixing time τ ≲ ε^{-1} (diam G)² log |V|. Our proof is based on carefully constructing a reweighted spanning tree of G with good expansion properties and superimposing it over a simple "base" chain.
In summary, our work together with known results shows that three fundamental geometric quantities characterise the mixing time on a graph according to three different notions of mixing: edge conductance characterises the mixing time of the lazy random walk, vertex conductance the fastest mixing time, while the diameter characterises the almost mixing time.
Finally, we also discuss analogous questions for continuous-time and time-inhomogeneous chains.
Original languageEnglish
Title of host publication13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
EditorsMark Braverman
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages109:1 - 109:1
Number of pages1
Volume215 (2022)
ISBN (Electronic)978-3-95977-217-4
DOIs
Publication statusPublished - 25 Jan 2022

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl - Leibniz Zentrum fur Informatik
Volume215
ISSN (Electronic)1868-8969

Fingerprint

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

Cite this