Abstract
In the Fastest Mixing Markov Chain problem, we are given a graph $$G = (V, E)$$ G = ( V , E ) and desire the discrete-time Markov chain with smallest mixing time $$\tau $$ τ 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 $$\tau _\textsf {RW}$$ τ RW of the lazy random walk on G is characterised by the edge conductance $$\Phi $$ Φ of G via Cheeger’s inequality: $$\Phi ^{-1} \lesssim \tau _\textsf {RW} \lesssim \Phi ^{-2} \log |V|$$ Φ - 1 ≲ τ RW ≲ Φ - 2 log | V | . Analogously, we characterise the fastest mixing time $$\tau ^\star $$ τ ⋆ via a Cheeger-type inequality but for a different geometric quantity, namely the vertex conductance $$\Psi $$ Ψ of G: $$\Psi ^{-1} \lesssim \tau ^\star \lesssim \Psi ^{-2} (\log |V|)^2$$ Ψ - 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 $$\varepsilon $$ ε -close to uniform in total variation. We show that it is always possible to construct such a chain with mixing time $$\tau \lesssim \varepsilon ^{-1} ({\text {diam}} G)^2 \log |V|$$ τ ≲ ε - 1 ( diam G ) 2 log | V | . Finally, we discuss analogous questions for continuous-time and time-inhomogeneous chains.
Funding Information
  • Engineering and Physical Sciences Research Council (EP/N004566/1)

This publication has 43 references indexed in Scilit: