Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



The Markov chain Monte Carlo revolution

Author: Persi Diaconis
Journal: Bull. Amer. Math. Soc. 46 (2009), 179-205
MSC (2000): Primary 60J20
Published electronically: November 20, 2008
MathSciNet review: 2476411
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The use of simulation for high-dimensional intractable computations has revolutionized applied mathematics. Designing, improving and understanding the new tools leads to (and leans on) fascinating mathematics, from representation theory through micro-local analysis.

References [Enhancements On Off] (What's this?)

  • 1. Aldous, D. and Fill, J. (2002).
    Reversible Markov chains and random walks on graphs.
  • 2. Allen, M. P. and Tildesely, D. J. (1987).
    Computer simulation of liquids.
    Oxford University Press, Oxford.
  • 3. William J. Anderson, Continuous-time Markov chains, Springer Series in Statistics: Probability and its Applications, Springer-Verlag, New York, 1991. An applications-oriented approach. MR 1118840
  • 4. Ery Arias-Castro, Persi Diaconis, and Richard Stanley, A super-class walk on upper-triangular matrices, J. Algebra 278 (2004), no. 2, 739–765. MR 2071663, 10.1016/j.jalgebra.2004.04.005
  • 5. Dominique Bakry, Patrick Cattiaux, and Arnaud Guillin, Rate of convergence for ergodic continuous Markov processes: Lyapunov versus Poincaré, J. Funct. Anal. 254 (2008), no. 3, 727–759. MR 2381160, 10.1016/j.jfa.2007.11.002
  • 6. Barthe, F., Bakry, P., Cattiaux, P., and Guillin, A. (2008).
    Poincaré inequalities for log-concave probability measures: a Lyapounov function approach.
    Electron Comm. Probab., 13:60-66.
  • 7. Rabi N. Bhattacharya and Edward C. Waymire, Stochastic processes with applications, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Inc., New York, 1990. A Wiley-Interscience Publication. MR 1054645
  • 8. Louis J. Billera and Persi Diaconis, A geometric interpretation of the Metropolis-Hastings algorithm, Statist. Sci. 16 (2001), no. 4, 335–339. MR 1888448, 10.1214/ss/1015346318
  • 9. Patrick Billingsley, Probability and measure, 3rd ed., Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. MR 1324786
  • 10. Pierre Brémaud, Markov chains, Texts in Applied Mathematics, vol. 31, Springer-Verlag, New York, 1999. Gibbs fields, Monte Carlo simulation, and queues. MR 1689633
  • 11. Bubley, B. and Dyer, M. (1997).
    Path coupling: a technique for proving rapid mixing in Markov chains.
    FOCS, pages 223-231.
  • 12. Krzysztof Burdzy and Wilfrid S. Kendall, Efficient Markovian couplings: examples and counterexamples, Ann. Appl. Probab. 10 (2000), no. 2, 362–409. MR 1768241, 10.1214/aoap/1019487348
  • 13. Olivier Cappé, Eric Moulines, and Tobias Rydén, Inference in hidden Markov models, Springer Series in Statistics, Springer, New York, 2005. With Randal Douc’s contributions to Chapter 9 and Christian P. Robert’s to Chapters 6, 7 and 13; With Chapter 14 by Gersende Fort, Philippe Soulier and Moulines, and Chapter 15 by Stéphane Boucheron and Elisabeth Gassiat. MR 2159833
  • 14. Tullio Ceccherini-Silberstein, Fabio Scarabotti, and Filippo Tolli, Harmonic analysis on finite groups, Cambridge Studies in Advanced Mathematics, vol. 108, Cambridge University Press, Cambridge, 2008. Representation theory, Gelfand pairs and Markov chains. MR 2389056
  • 15. Ming-Hui Chen, Qi-Man Shao, and Joseph G. Ibrahim, Monte Carlo methods in Bayesian computation, Springer Series in Statistics, Springer-Verlag, New York, 2000. MR 1742311
  • 16. Yuguo Chen, Persi Diaconis, Susan P. Holmes, and Jun S. Liu, Sequential Monte Carlo methods for statistical analysis of tables, J. Amer. Statist. Assoc. 100 (2005), no. 469, 109–120. MR 2156822, 10.1198/016214504000001303
  • 17. Conner, S. (2003).
    Simulation and solving substitution codes.
    Master's thesis, Department of Statistics, University of Warwick.
  • 18. Douglas E. Critchlow, Metric methods for analyzing partially ranked data, Lecture Notes in Statistics, vol. 34, Springer-Verlag, Berlin, 1985. MR 818986
  • 19. Persi Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069
  • 20. Persi Diaconis and R. L. Graham, Spearman’s footrule as a measure of disarray, J. Roy. Statist. Soc. Ser. B 39 (1977), no. 2, 262–268. MR 0652736
  • 21. Donald St. P. Richards (ed.), Hypergeometric functions on domains of positivity, Jack polynomials, and applications, Contemporary Mathematics, vol. 138, American Mathematical Society, Providence, RI, 1992. MR 1199117
  • 22. Persi Diaconis and I. M. Isaacs, Supercharacters and superclasses for algebra groups, Trans. Amer. Math. Soc. 360 (2008), no. 5, 2359–2392. MR 2373317, 10.1090/S0002-9947-07-04365-6
  • 23. Diaconis, P., Khare, K., and Saloff-Coste, L. (2008a).
    Gibbs sampling, exponential families and orthogonal polynomials, with discussion.
    Statist. Sci., to appear.
  • 24. Diaconis, P. and Lebeau, G. (2008).
    Micro-local analysis for the Metropolis algorithm.
    Math. Z., to appear.
  • 25. Diaconis, P., Lebeau, G., and Michel, L. (2008b).
    Geometric analysis for the Metropolis algorithm on Lipshitz domains.
    Technical report, Department of Statistics, Stanford University, preprint.
  • 26. Diaconis, P. and Limic, V. (2008).
    Spectral gap of the hard-core model on the unit interval.
    Technical report, Department of Statistics, Stanford University, preprint.
  • 27. Persi Diaconis and J. W. Neuberger, Numerical results for the Metropolis algorithm, Experiment. Math. 13 (2004), no. 2, 207–213. MR 2068894
  • 28. Persi Diaconis and Arun Ram, Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques, Michigan Math. J. 48 (2000), 157–190. Dedicated to William Fulton on the occasion of his 60th birthday. MR 1786485, 10.1307/mmj/1030132713
  • 29. Persi Diaconis and Laurent Saloff-Coste, Comparison theorems for reversible Markov chains, Ann. Appl. Probab. 3 (1993), no. 3, 696–730. MR 1233621
  • 30. P. Diaconis and L. Saloff-Coste, Nash inequalities for finite Markov chains, J. Theoret. Probab. 9 (1996), no. 2, 459–510. MR 1385408, 10.1007/BF02214660
  • 31. P. Diaconis and L. Saloff-Coste, What do we know about the Metropolis algorithm?, J. Comput. System Sci. 57 (1998), no. 1, 20–36. 27th Annual ACM Symposium on the Theory of Computing (STOC’95) (Las Vegas, NV). MR 1649805, 10.1006/jcss.1998.1576
  • 32. Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159–179. MR 626813, 10.1007/BF00535487
  • 33. Persi Diaconis and Bernd Sturmfels, Algebraic algorithms for sampling from conditional distributions, Ann. Statist. 26 (1998), no. 1, 363–397. MR 1608156, 10.1214/aos/1030563990
  • 34. Diaconis, P. and Thiem, N. (2008).
    Supercharacter formulas for pattern groups.
    Trans. Amer. Math. Soc., to appear.
  • 35. Dobrushin, R. L. (1970).
    Prescribing a system of random variables by conditional distributions.
    Theor. Probab. Appl.- Engl. Tr., 15:453-486.
  • 36. Doucet, A., de Freitas, N., and Gordon, N. (2001).
    Sequential Monte Carlo in Practice.
    Springer-Verlag, New York.
  • 37. Christophe Dress and Werner Krauth, Cluster algorithm for hard spheres and related systems, J. Phys. A 28 (1995), no. 23, L597–L601. MR 1381129
  • 38. Stewart N. Ethier and Thomas G. Kurtz, Markov processes, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1986. Characterization and convergence. MR 838085
  • 39. William Feller, An introduction to probability theory and its applications. Vol. I, Third edition, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020
  • 40. James Allen Fill, Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process, Ann. Appl. Probab. 1 (1991), no. 1, 62–87. MR 1097464
  • 41. Frenkel, D. and Smit, B. (2002).
    Understanding molecular simulation: From algorithms to applications, 2nd edition.
    Computational Science Series, Vol 1. Academic Press, San Diego.
  • 42. Fukushima, M., Ōshima, Y., and Takeda, M. (1994).
    Dirichlet forms and symmetric Markov processes, volume 19 of de Gruyter Studies in Mathematics.
    Walter de Gruyter & Co., Berlin.
  • 43. Gill, J. (2007).
    Bayesian methods: a social and behavioral sciences approach, 2nd ed.
    Statistics in the Social and Behavioral Sciences. Chapman & Hall/CRC.
    Second edition.
  • 44. J. M. Hammersley and D. C. Handscomb, Monte Carlo methods, Methuen & Co., Ltd., London; Barnes & Noble, Inc., New York, 1965. MR 0223065
  • 45. Hendrickson, A. O. F. (2008).
    Supercharacter theories of finite simple groups.
    PhD thesis, University of Wisconsin.
  • 46. James P. Hobert, Galin L. Jones, Brett Presnell, and Jeffrey S. Rosenthal, On the applicability of regenerative simulation in Markov chain Monte Carlo, Biometrika 89 (2002), no. 4, 731–743. MR 1946508, 10.1093/biomet/89.4.731
  • 47. Derek F. Holt, Bettina Eick, and Eamonn A. O’Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2005. MR 2129747
  • 48. Akihito Hora and Nobuaki Obata, Quantum probability and spectral analysis of graphs, Theoretical and Mathematical Physics, Springer, Berlin, 2007. With a foreword by Luigi Accardi. MR 2316893
  • 49. Hosten, S. and Meek, C. (2006).
    J. Symb. Comput., 41(2):123-124.
  • 50. Søren Fiig Jarner and Ernst Hansen, Geometric ergodicity of Metropolis algorithms, Stochastic Process. Appl. 85 (2000), no. 2, 341–361. MR 1731030, 10.1016/S0304-4149(99)00082-4
  • 51. Jaster, A. (2004).
    The hexatic phase of the two-dimensional hard disks system.
    Phys. Lett. A, 330(cond-mat/0305239):120-125.
  • 52. Mark Jerrum, Alistair Sinclair, and Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM 51 (2004), no. 4, 671–697 (electronic). MR 2147852, 10.1145/1008731.1008738
  • 53. Galin L. Jones and James P. Hobert, Honest exploration of intractable probability distributions via Markov chain Monte Carlo, Statist. Sci. 16 (2001), no. 4, 312–334. MR 1888447, 10.1214/ss/1015346317
  • 54. Ravi Kannan, Michael W. Mahoney, and Ravi Montenegro, Rapid mixing of several Markov chains for a hard-core model, Algorithms and computation, Lecture Notes in Comput. Sci., vol. 2906, Springer, Berlin, 2003, pp. 663–675. MR 2088246, 10.1007/978-3-540-24587-2_68
  • 55. Wilfrid S. Kendall, Geometric ergodicity and perfect simulation, Electron. Comm. Probab. 9 (2004), 140–151 (electronic). MR 2108860, 10.1214/ECP.v9-1117
  • 56. I. Kontoyiannis and S. P. Meyn, Spectral theory and limit theorems for geometrically ergodic Markov processes, Ann. Appl. Probab. 13 (2003), no. 1, 304–362. MR 1952001, 10.1214/aoap/1042765670
  • 57. Werner Krauth, Statistical mechanics, Oxford Master Series in Physics, Oxford University Press, Oxford, 2006. Algorithms and computations; Oxford Master Series in Statistical Computational, and Theoretical Physics. MR 2370557
  • 58. David P. Landau and Kurt Binder, A guide to Monte Carlo simulations in statistical physics, Cambridge University Press, Cambridge, 2000. MR 1781083
  • 59. Lebeau, G. and Michel, L. (2008).
    Semiclassical analysis of a random walk on a manifold.
    Ann. Probab., to appear (arXiv:0802.0644).
  • 60. Thomas M. Liggett, Interacting particle systems, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. MR 776231
  • 61. Torgny Lindvall, Lectures on the coupling method, Dover Publications, Inc., Mineola, NY, 2002. Corrected reprint of the 1992 original. MR 1924231
  • 62. Jun S. Liu, Monte Carlo strategies in scientific computing, Springer Series in Statistics, Springer-Verlag, New York, 2001. MR 1842342
  • 63. László Lovász and Santosh Vempala, Hit-and-run from a corner, SIAM J. Comput. 35 (2006), no. 4, 985–1005 (electronic). MR 2203735, 10.1137/S009753970544727X
  • 64. Hartmut Löwen, Fun with hard spheres, Statistical physics and spatial statistics (Wuppertal, 1999) Lecture Notes in Phys., vol. 554, Springer, Berlin, 2000, pp. 295–331. MR 1870950, 10.1007/3-540-45043-2_11
  • 65. I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR 1354144
  • 66. Mackenzie, P. (2005).
    The fundamental constants of nature from lattice gauge theory simulations.
    J. Phys. Conf. Ser., 16(doi:10.1088/1742-6596/16/1/018):140-149.
  • 67. Fabio Martinelli, Relaxation times of Markov chains in statistical mechanics and combinatorial structures, Probability on discrete structures, Encyclopaedia Math. Sci., vol. 110, Springer, Berlin, 2004, pp. 175–262. MR 2023653, 10.1007/978-3-662-09444-0_4
  • 68. S. P. Meyn and R. L. Tweedie, Markov chains and stochastic stability, Communications and Control Engineering Series, Springer-Verlag London, Ltd., London, 1993. MR 1287609
  • 69. Ravi Montenegro and Prasad Tetali, Mathematical aspects of mixing times in Markov chains, Found. Trends Theor. Comput. Sci. 1 (2006), no. 3, x+121. MR 2341319
  • 70. Ben Morris and Alistair Sinclair, Random walks on truncated cubes and sampling 0-1 knapsack solutions, SIAM J. Comput. 34 (2004), no. 1, 195–226. MR 2114310, 10.1137/S0097539702411915
  • 71. Neel, R. W. (2008).
    A martingale approach to minimal surfaces.
    J. Funct. Anal., (doi:10.1016/j.jfa.2008.06.033).
    arXiv:0805.0556v2 [math.DG] (in press).
  • 72. M. E. J. Newman and G. T. Barkema, Monte Carlo methods in statistical physics, The Clarendon Press, Oxford University Press, New York, 1999. MR 1691513
  • 73. Ollivier, Y. (2008).
    Ricci curvature of Markov chains on metric spaces.
    Preprint, submitted, 2008.
  • 74. Lior Pachter and Bernd Sturmfels (eds.), Algebraic statistics for computational biology, Cambridge University Press, New York, 2005. MR 2205865
  • 75. Igor Pak, What do we know about the product replacement algorithm?, Groups and computation, III (Columbus, OH, 1999) Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 301–347. MR 1829489
  • 76. Giovanni Pistone, Eva Riccomagno, and Henry P. Wynn, Algebraic statistics, Monographs on Statistics and Applied Probability, vol. 89, Chapman & Hall/CRC, Boca Raton, FL, 2001. Computational commutative algebra in statistics. MR 2332740
  • 77. James Gary Propp and David Bruce Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), 1996, pp. 223–252. MR 1611693, 10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.3.CO;2-R
  • 78. Ross, S. M. (2002).
    A First Course in Probability, 7th Edition.
    Cambridge University Press, Cambridge.
  • 79. Laurent Saloff-Coste, Lectures on finite Markov chains, Lectures on probability theory and statistics (Saint-Flour, 1996) Lecture Notes in Math., vol. 1665, Springer, Berlin, 1997, pp. 301–413. MR 1490046, 10.1007/BFb0092621
  • 80. Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241
  • 81. Alistair Sinclair, Algorithms for random generation and counting, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1993. A Markov chain approach. MR 1201590
  • 82. Stanley, R. P. (1999).
    Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics.
    Cambridge University Press, Cambridge.
    With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.
  • 83. Howard M. Taylor and Samuel Karlin, An introduction to stochastic modeling, Academic Press, Inc., Orlando, FL, 1984. MR 778728
  • 84. Thiem, N. and Marberg, E. (2008).
    Superinduction for pattern groups.
    Technical report, Department of Mathematics, University of Colorado, Boulder.
  • 85. Thiem, N. and Venkateswaran, V. (2008).
    Restricting supercharacters of the finite group of unipotent uppertriangular matrices.
    Technical report, Department of Mathematics, University of Colorado, Boulder.
  • 86. Hermann Thorisson, Coupling, stationarity, and regeneration, Probability and its Applications (New York), Springer-Verlag, New York, 2000. MR 1741181
  • 87. Uhlenbeck, G. E. (1968).
    An outline of statistical mechanics.
    In Cohen, E. G. D., editor, Fundamental Problems in Statistical Mechanics, volume 2, pages 1-19. North-Holland Publishing Co., Amsterdam.
  • 88. Tung Tsang, Statistical mechanics, Rinton Press, Incorporated, Princeton, NJ, 2002. MR 1921032
  • 89. Horng-Tzer Yau, Logarithmic Sobolev inequality for generalized simple exclusion processes, Probab. Theory Related Fields 109 (1997), no. 4, 507–538. MR 1483598, 10.1007/s004400050140

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 60J20

Retrieve articles in all journals with MSC (2000): 60J20

Additional Information

Persi Diaconis
Affiliation: Department of Mathematics and Statistics, Stanford University, Stanford, California

Received by editor(s): August 5, 2008
Published electronically: November 20, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.