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.) |