Abstract
In the Fastest Mixing Markov Chain problem, we are given a graph G = (V, E) and desire the discretetime Markov chain with smallest mixing time τ subject to having equilibrium distribution uniform on V and nonzero transition probabilities only across edges of the graph [Boyd et al., 2004].
It is wellknown 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} logV. Edge conductance, however, fails to characterise the fastest mixing time τ^⋆ of G. Take, for example, a graph consisting of two nvertex 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 Cheegertype inequality but for a different geometric quantity, namely the vertex conductance Ψ of G: Ψ^{1} ≲ τ^* ≲ Ψ^{2}(logV)^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 continuoustime and timeinhomogeneous chains.
BibTeX  Entry
@InProceedings{oleskertaylor_et_al:LIPIcs.ITCS.2022.109,
author = {OleskerTaylor, Sam and Zanetti, Luca},
title = {{Geometric Bounds on the Fastest Mixing Markov Chain}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {109:1109:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15705},
URN = {urn:nbn:de:0030drops157051},
doi = {10.4230/LIPIcs.ITCS.2022.109},
annote = {Keywords: mixing time, random walks, conductance, fastest mixing Markov chain}
}
Keywords: 

mixing time, random walks, conductance, fastest mixing Markov chain 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 