Geometric bounds on the fastest mixing Markov chain
Open Access
- 30 January 2024
- journal article
- research article
- Published by Springer Nature in Probability Theory and Related Fields
- Vol. 188 (3-4) , 1017-1062
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 _\textsf {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|$$ . 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 $$\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|$$ . Finally, we discuss analogous questions for continuous-time and time-inhomogeneous chains.
Keywords
All Related Versions
Funding Information
- Engineering and Physical Sciences Research Council (EP/N004566/1)
This publication has 43 references indexed in Scilit:
- Comparison inequalities and fastest-mixing Markov chainsThe Annals of Applied Probability, 2013
- Fastest mixing Markov chain problem for the union of two cliquesLinear and Multilinear Algebra, 2011
- Fastest Mixing Markov Chain on a PathThe American Mathematical Monthly, 2006
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entriesJournal of the ACM, 2004
- $\lambda_{\infty}$ , Vertex Isoperimetry and ConcentrationCombinatorica, 2000
- Relations entre isopérimétrie et trou spectral pour les chaînes de Markov finiesProbability Theory and Related Fields, 1999
- The electrical resistance of a graph captures its commute and cover timescomputational complexity, 1996
- Trailing the Dovetail Shuffle to its LairThe Annals of Applied Probability, 1992
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's InequalityTransactions of the American Mathematical Society, 1988
- Extensions of Lipschitz mappings into a Hilbert space1984