Analyzing Glauber dynamics by comparison of Markov chains

1. Aldous, D. Random walks on finite groups and rapidly mixing Markov chains. Séminaire de Probabilités XVII, 1981/82, Springer Lecture Notes in Mathematics 986, pp. 243–297.

   Article  MathSciNet  Google Scholar 

2. Baxter, R.J. Exactly solved models in statistical mechanics. Academic Press, London, 1982.

   MATH  Google Scholar 

3. van den Berg, J. and Steif, J.E. Percolation and the hard-core lattice gas model. Stochastic Processes and their Applications 49, 1994, pp. 179–197.

   Article  MathSciNet  MATH  Google Scholar 

4. Diaconis, P. and Stroock, D. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probability 1, 1991, pp. 36–61.

   MathSciNet  MATH  Google Scholar 

5. Diaconis, P. and Saloff-Coste, L. Comparison theorems for reversible Markov chains. Ann. Appl. Probability 3, 1993, pp. 696–730.

   MathSciNet  MATH  Google Scholar 

6. Diaconis, P. and Saloff-Coste, L. Logarithmic Sobolev Inequalities for Finite Markov Chains. Ann. of Appl. Probab. 6 (1996), pp. 695–750.

   Article  MathSciNet  MATH  Google Scholar 

7. Jerrum, M. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures and Algorithms 7, 1995, pp. 157–165.

   MATH  MathSciNet  Google Scholar 

8. Jerrum, M.R. and Sinclair, A.J. Approximating the permanent. SIAM Journal on Computing 18 (1989), pp. 1149–1178.

   Article  MathSciNet  MATH  Google Scholar 

9. Jerrum, M., Valiant, L. and Vazirani, V. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science 43 (1986), pp. 169–188.

   Article  MathSciNet  MATH  Google Scholar 

10. Kannan, R., Tetali, and P., Vempala, S. Simple Markov chain algorithms for generating bipartite graphs and tournaments. Proc. of the 8th ACM-SIAM Symp. on Discrete Algorithms January 1997.

    Google Scholar 

11. Lieb, E.H. Residual entropy of square ice. Physical Review 162, 1967, pp. 162–172.

    Article  Google Scholar 

12. Lubin, M. and Sokal A.D. Comment on “Antiferromagnetic Potts Model. Phys. Rev. Lett. 71, 1993, pp. 17–78.

    Article  Google Scholar 

13. Luby, M., Randall, D. and Sinclair, A. Markov Chain Algorithms for Planar Lattice Structures. Proc. 36th IEEE Symposium on Foundations of Computing (1995), pp. 150–159.

    Google Scholar 

14. Luby, M., Vigoda, E. Approximately counting up to four. Proc. 29th ACM Symposium on Theory of Computing (1997), pp. 150–159.

    Google Scholar 

15. Madras, N. and Randall, D. Factoring Graphs to Bound Mixing Time. Proc. 37th IEEE Symposium on Foundations of Computing (1996).

    Google Scholar 

16. Sinclair, A.J. and Jerrum, M.R. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation 82 (1989), pp. 93–133.

    Article  MathSciNet  MATH  Google Scholar 

17. Sinclair, A.J. Algorithms for random generation & counting: a Markov chain approach. Birkhäuser, Boston, 1993, pp. 47–48.

    MATH  Google Scholar 

18. Sinclair, A.J. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability, & Computing. 1 (1992), pp. 351–370.

    MATH  MathSciNet  Google Scholar 

19. Thurston, W. Conway's tiling groups. American Mathematical Monthly 97, 1990, pp. 757–773.

    Article  MATH  MathSciNet  Google Scholar 

20. Vigoda, E. personal communication.

    Google Scholar 

21. Welsh, D.J.A. The computational complexity of some classical problems from statistical physics. In Disorder in Physical Systems, (G. Grimmett and D. Welsh eds.). Claredon Press, Oxford, 1990, pp. 323–335.

    Google Scholar 

22. Welsh, D.J.A. Approximate counting. In Surveys in Combinatorics, (R.A. Bailey, ed.). Cambridge University Press, London Math Society Lecture Notes 241, 1997, pp. 287–317.

    Google Scholar 

23. Wilson, D.B. Mixing times of lozenge tiling and card shuffling Markov chains, draft of manuscript.

    Google Scholar 

Download references