Geometric Bounds on the Fastest Mixing Markov Chain
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917864236122112 |
|---|---|
| author | Olesker-Taylor, Sam Zanetti, Luca |
| author_facet | Olesker-Taylor, Sam Zanetti, Luca |
| contents | 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 $τ_\textsf{RW}$ of the lazy random walk on $G$ is characterised by the edge conductance $Φ$ of $G$ via Cheeger's inequality: $Φ^{-1} \lesssim τ_\textsf{RW} \lesssim Φ^{-2} \log |V|$. Analogously, we characterise the fastest mixing time $τ^\star$ via a Cheeger-type inequality but for a different geometric quantity, namely the vertex conductance $Ψ$ of $G$: $Ψ^{-1} \lesssim τ^\star \lesssim Ψ^{-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 $τ\lesssim \varepsilon^{-1} (\operatorname{diam} G)^2 \log |V|$.
Finally, we discuss analogous questions for continuous-time and time-inhomogeneous chains. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_05816 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Geometric Bounds on the Fastest Mixing Markov Chain Olesker-Taylor, Sam Zanetti, Luca Probability Discrete Mathematics Combinatorics 05C81, 60J10, 60J20, 60J27 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 $τ_\textsf{RW}$ of the lazy random walk on $G$ is characterised by the edge conductance $Φ$ of $G$ via Cheeger's inequality: $Φ^{-1} \lesssim τ_\textsf{RW} \lesssim Φ^{-2} \log |V|$. Analogously, we characterise the fastest mixing time $τ^\star$ via a Cheeger-type inequality but for a different geometric quantity, namely the vertex conductance $Ψ$ of $G$: $Ψ^{-1} \lesssim τ^\star \lesssim Ψ^{-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 $τ\lesssim \varepsilon^{-1} (\operatorname{diam} G)^2 \log |V|$. Finally, we discuss analogous questions for continuous-time and time-inhomogeneous chains. |
| title | Geometric Bounds on the Fastest Mixing Markov Chain |
| topic | Probability Discrete Mathematics Combinatorics 05C81, 60J10, 60J20, 60J27 |
| url | https://arxiv.org/abs/2111.05816 |