Bounding Fastest Mixing

Sébastien Roch (University of California at Berkeley, USA)

Abstract


In a recent work, Boyd, Diaconis and Xiao 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.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 282-296

Publication Date: December 29, 2005

DOI: 10.1214/ECP.v10-1169

References

  1. Aldous, D. and Fill, J., Reversible Markov Chains and Random Walks on Graphs, monograph in preparation, 2004. Math. Review number not available.
  2. N. Berger et al., Glauber dynamics on trees and hyperbolic graphs, Probab. Theory Related Fields 131 (2005), no. 3, 311-340. Math. Review MR2123248 (2005k:82066)
  3. Boyd, S., Diaconis, P., Parrilo, P., and Xiao, L., Symmetry analysis of reversible Markov chains, Internet Mathematics, 2 (2005), no. 1, 31-71. Math. Review number not available.
  4. Boyd, S., Diaconis, P., Sun, J., and Xiao, L., Fastest mixing Markov chain on a path. To appear in The American Mathematical Monthly, 2005. Math. Review number not available.
  5. S. Boyd et al., Fastest mixing Markov chain on a graph, SIAM Rev. 46 (2004), no. 4, 667-689 (electronic). Math. Review MR2124681 (2005j:90058)
  6. Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D., Mixing Times for Random Walks on Geometric Random Graphs. To appear in SIAM ANALCO 2005. Math. Review number not available.
  7. S. Boyd and L. Vandenberghe, Convex optimization, Cambridge Univ. Press, Cambridge, 2004. Math. Review MR2061575 (2005d:90002)
  8. P. Diaconis and D. Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), no. 1, 36-61. Math. Review MR1097463 (92h:60103)
  9. W. Evans et al., Broadcasting on trees and the Ising model, Ann. Appl. Probab. 10 (2000), no. 2, 410-433. Math. Review MR1768240 (2001g:60243)
  10. R. A. Horn, C. R. Johnson, Matrix analysis, Cambridge Univ. Press, Cambridge, 1985. Math. Review MR0832183 (87e:15001)
  11. M. Jerrum, Counting, sampling and integrating: algorithms and complexity, Birkhauser, Basel, 2003. Math. Review MR1960003 (2004a:68044)
  12. M. Jerrum and A. Sinclair, Approximating the permanent, SIAM J. Comput. 18 (1989), no. 6, 1149-1178. Math. Review MR1025467 (91a:05075)
  13. A. Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow, Combin. Probab. Comput. 1 (1992), no. 4, 351-370. Math. Review MR1211324 (94f:60087)
  14. Sun, J., Boyd, S., Xiao, L., and Diaconis, P., The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem. To appear in SIAM Review, 2005. Math. Review number not available.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.