Geometric bounds on the fastest mixing Markov chain

• 成果类型: Article
• 署名作者: Olesker-Taylor, Sam; Zanetti, Luca
• 署名单位: University of Warwick; University of Bath
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-023-01257-x
• 发表日期: 2024
• 页码: 1017-1062
• 关键词: times

摘要

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(RW) of the lazy random walk on G is characterised by the edge conductance Phi of G via Cheeger's inequality: Phi(-1) less than or similar to tau(RW) less than or similar to 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) less than or similar to tau(star) less than or similar to 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 chainwith mixing time tau less than or similar to epsilon(-1) (diam G)(2) log |V|. Finally, we discuss analogous questions for continuous-time and time-inhomogeneous chains.