A semidefinite sound for mixing sates of Markov chains
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(2)n, where n is the number of states. (C) 1997 John Wiley & Sons, Inc.
markov chains semidefinite programming eigenvalues poincare inequalities multicommodity flow