×

A semidefinite bound for mixing rates of Markov chains. (English) Zbl 0889.90154

Summary: We study general geometric techniques for bounding the spectral gap of a reversible Markov chain. We show that the best bound obtainable using these techniques can be computed in polynomial time via semidefinite programming, and is off by at most a factor of order \(\log^2n\), where \(n\) is the number of states.

MSC:

90C40 Markov and semi-Markov decision processes
90B10 Deterministic network models in operations research
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI