Bounding fastest mixing. (English) Zbl 1111.60056

Summary: In a recent work, S. Boyd, P. Diaconis, J. Sun and L. Xiao [SIAM Rev. 46, No. 4, 667–689 (2004; Zbl 1063.60102)] introduced a semidefinite programming approach for computing the fastest mixing Markov chain on a graph of allowed transitions, given a target stationary distribution. In this paper, we show that standard mixing time analysis techniques – variational characterizations, conductance, canonical paths – can be used to give simple, nontrivial lower and upper bounds on the fastest mixing time. To test the applicability of this idea, we consider several detailed examples including the Glauber dynamics of the Ising model.


60J10 Markov chains (discrete-time Markov processes on discrete state spaces)


Zbl 1063.60102
Full Text: DOI arXiv EuDML