Geometric bounds on the fastest mixing Markov chain

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|) ² . 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) ²log | V| . Finally, we discuss analogous questions for continuous-time and time-inhomogeneous chains.