Decomposition Methods and Sampling Circuits in the Cartesian Lattice

1. C. Borgs, J. T. Chayes, A. Frieze, J. H. Kim, P. Tetali, E. Vigoda, and V. H. Vu. Torpid mixing of some MCMC algorithms in statistical physics. Proc. 40th IEEE Symposium on Foundations of Computer Science, 218–229, 1999.

   Google Scholar 

2. R. Bubley and M. Dyer. Faster random generation of linear extensions. Discrete Mathematics, 201:81–88, 1999.

   Article  MATH  MathSciNet  Google Scholar 

3. R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. Proc. 38th Annual IEEE Symposium on Foundations of Computer Science 223–231, 1997.

   Google Scholar 

4. P. Diaconis and L. Saloff-Coste. Comparison theorems for reversible Markov chains. Annals of Applied Probability, 3:696–730, 1993.

   Article  MATH  MathSciNet  Google Scholar 

5. M. Dyer and C. Greenhill. On Markov chains for independent sets. Journal of Algorithms, 35: 17–49, 2000.

   Article  MATH  MathSciNet  Google Scholar 

6. M. Dyer and C. Greenhill. A more rapidly mixing Markov chain for graph colorings. Random Structures and Algorithms, 13:285–317, 1998.

   Article  MATH  MathSciNet  Google Scholar 

7. C. J. Geyer Markov Chain Monte Carlo Maximum Likelihood. Computing Science and Statistics: Proceedings of the 23rd Symposium on the Interface (E. M. Keramidas, ed.), 156–163. Interface Foundation, Fairfax Station, 1991.

   Google Scholar 

8. C. J. Geyer and E. A. Thompson. Annealing Markov Chain Monte Carlo with Applications to Ancestral Inference. J. Amer. Statist. Assoc. 90 909–920, 1995.

   Article  MATH  Google Scholar 

9. M. Luby and E. Vigoda. Fast Convergence of the Glauber dynamics for sampling independent sets. Random Structures and Algorithms 15: 229–241, 1999.

   Article  MATH  MathSciNet  Google Scholar 

10. N. Madras and M. Piccioni. Importance sampling for families of distributions. Ann. Appl. Probab. 9: 1202–1225, 1999.

    Article  MATH  MathSciNet  Google Scholar 

11. N. Madras and D. Randall. Factoring graphs to bound mixing rates. Proc. 37th Annual IEEE Symposium on Foundations of Computer Science, 194–203, 1996.

    Google Scholar 

12. N. Madras and D. Randall. Markov chain decomposition for convergence rate analysis. Annals of Applied Probability, (to appear), 2001.

    Google Scholar 

13. N. Madras and Z. Zheng. On the swapping algorithm. Preprint, 2001.

    Google Scholar 

14. E. Marinari and G. Parisi. Simulated tempering: a new Monte Carlo scheme. Europhys. Lett. 19 451–458, 1992.

    Article  Google Scholar 

15. R. A. Martin and D. Randall Sampling adsorbing staircase walks using a new Markov chain decomposition method. Proceedings of the 41st Symposium on the Foundations of Computer Science (FOCS 2000), 492–502, 2000.

    Google Scholar 

16. R. A. Martin and D. Randall Disjoint decomposition with applications to sampling circuits in some Cayley graphs. Preprint, 2001.

    Google Scholar 

17. D. Randall and P. Tetali. Analyzing Glauber dynamics by comparison of Markov chains. Journal of Mathematical Physics, 41:1598–1615, 2000.

    Article  MATH  MathSciNet  Google Scholar 

18. A. J. Sinclair. Algorithms for random generation & counting: a Markov chain approach. Birkhäuser, Boston, 1993.

    MATH  Google Scholar 

Download references