Geometric Bounds on the Fastest Mixing Markov Chain

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 $\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 }_{\text{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 }_{\text{RW}}\lesssim {\Phi }^{-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$. 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 $\epsilon$-close to uniform in total variation. We show that it is always possible to construct such a chain with mixing time $\tau \lesssim {\epsilon }^{-1}(\mathrm{diam}G{)}^2\log |V|$. Finally, we discuss analogous questions for continuous-time and time-inhomogeneous chains.

arXiv comment31 pages

References in corpus (6)

• Fastest mixing Markov chain on graphs with symmetries
• Comparison inequalities and fastest-mixing Markov chains
• Geometric Bounds on the Fastest Mixing Markov Chain
• Counting weighted independent sets beyond the permanent
• Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain
• Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time

Cited by in corpus (1)

• Geometric Bounds on the Fastest Mixing Markov Chain