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. Anderson, W. J. (1991).
    Continuous-time Markov chains.
    An applications-oriented approach.
    Springer Series in Statistics: Probability and its Applications. Springer-Verlag, New York. MR 1118840 (92k:60170)
  • 4. Arias-Castro, E., Diaconis, P., and Stanley, R. (2004).
    A super-class walk on upper-triangular matrices.
    J. Algebra, 278(2):739-765. MR 2071663 (2005f:60101)
  • 5. Bakry, D., Cattiaux, P., and Guillin, A. (2008).
    Rate of convergence for ergodic continuous Markov processes: Lyapunov versus Poincaré.
    J. Funct. Anal., 254(3):727-759. MR 2381160
  • 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. Bhattacharya, R. N. and Waymire, E. C. (1990).
    Stochastic processes with applications.
    Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. John Wiley & Sons Inc., New York.
    A Wiley-Interscience Publication. MR 1054645 (91m:60001)
  • 8. Billera, L. J. and Diaconis, P. (2001).
    A geometric interpretation of the Metropolis-Hastings algorithm.
    Statist. Sci., 16(4):335-339. MR 1888448 (2002m:60133)
  • 9. Billingsley, P. (1995).
    Probability and measure.
    Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons Inc., New York, third edition.
    A Wiley-Interscience Publication. MR 1324786 (95k:60001)
  • 10. Brémaud, P. (1999).
    Markov chains, volume 31 of Texts in Applied Mathematics.
    Springer-Verlag, New York.
    Gibbs fields, Monte Carlo simulation, and queues. MR 1689633 (2000k:60137)
  • 11. Bubley, B. and Dyer, M. (1997).
    Path coupling: a technique for proving rapid mixing in Markov chains.
    FOCS, pages 223-231.
  • 12. Burdzy, K. and Kendall, W. S. (2000).
    Efficient Markovian couplings: examples and counterexamples.
    Ann. Appl. Probab., 10(2):362-409. MR 1768241 (2002b:60129)
  • 13. Cappé, O., Moulines, E., and Rydén, T. (2005).
    Inference in hidden Markov models.
    Springer Series in Statistics. Springer, New York.
    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 (2006e:60002)
  • 14. Ceccherini-Silberstein, T., Scarabotti, F., and Tolli, F. (2008).
    Harmonic analysis on finite groups, volume 108 of Cambridge Studies in Advanced Mathematics.
    Cambridge University Press, Cambridge.
    Representation theory, Gelfand pairs and Markov chains. MR 2389056
  • 15. Chen, M.-H., Shao, Q.-M., and Ibrahim, J. G. (2000).
    Monte Carlo methods in Bayesian computation.
    Springer Series in Statistics. Springer-Verlag, New York. MR 1742311 (2000k:65014)
  • 16. Chen, Y., Diaconis, P., Holmes, S. P., and Liu, J. S. (2005).
    Sequential Monte Carlo methods for statistical analysis of tables.
    J. Amer. Statist. Assoc., 100(469):109-120. MR 2156822 (2006f:62062)
  • 17. Conner, S. (2003).
    Simulation and solving substitution codes.
    Master's thesis, Department of Statistics, University of Warwick.
  • 18. Critchlow, D. E. (1985).
    Metric methods for analyzing partially ranked data, volume 34 of Lecture Notes in Statistics.
    Springer-Verlag, Berlin. MR 818986 (87c:62044)
  • 19. Diaconis, P. (1988).
    Group representations in probability and statistics.
    Institute of Mathematical Statistics Lecture Notes--Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA. MR 964069 (90a:60001)
  • 20. Diaconis, P. and Graham, R. L. (1977).
    Spearman's footrule as a measure of disarray.
    J. Roy. Statist. Soc. Ser. B, 39(2):262-268. MR 0652736 (58:31575)
  • 21. Diaconis, P. and Hanlon, P. (1992).
    Eigen-analysis for some examples of the Metropolis algorithm.
    In Hypergeometric functions on domains of positivity, Jack polynomials, and applications (Tampa, FL, 1991), volume 138 of Contemp. Math., pages 99-117. Amer. Math. Soc., Providence, RI. MR 1199117 (93h:33001)
  • 22. Diaconis, P. and Isaacs, I. M. (2008).
    Supercharacters and superclasses for algebra groups.
    Trans. Amer. Math. Soc., 360(5):2359-2392. MR 2373317
  • 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. Diaconis, P. and Neuberger, J. W. (2004).
    Numerical results for the Metropolis algorithm.
    Experiment. Math., 13(2):207-213. MR 2068894
  • 28. Diaconis, P. and Ram, A. (2000).
    Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques.
    Michigan Math. J., 48:157-190.
    Dedicated to William Fulton on the occasion of his 60th birthday. MR 1786485 (2001j:60132)
  • 29. Diaconis, P. and Saloff-Coste, L. (1993).
    Comparison theorems for reversible Markov chains.
    Ann. Appl. Probab., 3(3):696-730. MR 1233621 (94i:60074)
  • 30. Diaconis, P. and Saloff-Coste, L. (1996).
    Nash inequalities for finite Markov chains.
    J. Theoret. Probab., 9(2):459-510. MR 1385408 (97d:60114)
  • 31. Diaconis, P. and Saloff-Coste, L. (1998).
    What do we know about the Metropolis algorithm?
    J. Comput. System Sci., 57(1):20-36.
    27th Annual ACM Symposium on the Theory of Computing (STOC'95) (Las Vegas, NV). MR 1649805 (2000b:68094)
  • 32. Diaconis, P. and Shahshahani, M. (1981).
    Generating a random permutation with random transpositions.
    Z. Wahrsch. Verw. Gebiete, 57(2):159-179. MR 626813 (82h:60024)
  • 33. Diaconis, P. and Sturmfels, B. (1998).
    Algebraic algorithms for sampling from conditional distributions.
    Ann. Statist., 26(1):363-397. MR 1608156 (99j:62137)
  • 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. Dress, C. and Krauth, W. (1995).
    Cluster algorithm for hard spheres and related systems.
    J. Phys. A, 28(23):L597-L601. MR 1381129
  • 38. Ethier, S. N. and Kurtz, T. G. (1986).
    Markov processes.
    Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons Inc., New York.
    Characterization and convergence. MR 838085 (88a:60130)
  • 39. Feller, W. (1968).
    An introduction to probability theory and its applications. Vol. I.
    Third edition. John Wiley & Sons Inc., New York. MR 0228020 (37:3604)
  • 40. Fill, J. A. (1991).
    Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process.
    Ann. Appl. Probab., 1(1):62-87. MR 1097464 (92h:60104)
  • 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. Hammersley, J. M. and Handscomb, D. C. (1965).
    Monte Carlo methods.
    Methuen & Co. Ltd., London. MR 0223065 (36:6114)
  • 45. Hendrickson, A. O. F. (2008).
    Supercharacter theories of finite simple groups.
    PhD thesis, University of Wisconsin.
  • 46. Hobert, J. P., Jones, G. L., Presnell, B., and Rosenthal, J. S. (2002).
    On the applicability of regenerative simulation in Markov chain Monte Carlo.
    Biometrika, 89(4):731-743. MR 1946508 (2003m:60200)
  • 47. Holt, D. F., Eick, B., and O'Brien, E. A. (2005).
    Handbook of computational group theory.
    Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL. MR 2129747 (2006f:20001)
  • 48. Hora, A. and Obata, N. (2007).
    Quantum probability and spectral analysis of graphs.
    Theoretical and Mathematical Physics. Springer, Berlin.
    With a foreword by Luigi Accardi. MR 2316893
  • 49. Hosten, S. and Meek, C. (2006).
    J. Symb. Comput., 41(2):123-124.
  • 50. Jarner, S. F. and Hansen, E. (2000).
    Geometric ergodicity of Metropolis algorithms.
    Stochastic Process. Appl., 85(2):341-361. MR 1731030 (2001c:60108)
  • 51. Jaster, A. (2004).
    The hexatic phase of the two-dimensional hard disks system.
    Phys. Lett. A, 330(cond-mat/0305239):120-125.
  • 52. Jerrum, M., Sinclair, A., and Vigoda, E. (2004).
    A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
    J. ACM, 51(4):671-697 (electronic). MR 2147852 (2006b:15013)
  • 53. Jones, G. L. and Hobert, J. P. (2001).
    Honest exploration of intractable probability distributions via Markov chain Monte Carlo.
    Statist. Sci., 16(4):312-334. MR 1888447
  • 54. Kannan, R., Mahoney, M. W., and Montenegro, R. (2003).
    Rapid mixing of several Markov chains for a hard-core model.
    In Algorithms and computation, volume 2906 of Lecture Notes in Comput. Sci., pages 663-675. Springer, Berlin. MR 2088246 (2005d:68160)
  • 55. Kendall, W. S. (2004).
    Geometric ergodicity and perfect simulation.
    Electron. Comm. Probab., 9:140-151 (electronic). MR 2108860 (2006e:60098)
  • 56. Kontoyiannis, I. and Meyn, S. P. (2003).
    Spectral theory and limit theorems for geometrically ergodic Markov processes.
    Ann. Appl. Probab., 13(1):304-362. MR 1952001 (2003m:60187)
  • 57. Krauth, W. (2006).
    Statistical mechanics.
    Oxford Master Series in Physics. Oxford University Press, Oxford.
    Algorithms and computations, Oxford Master Series in Statistical Computational, and Theoretical Physics. MR 2370557
  • 58. Landau, D. P. and Binder, K. (2005).
    A Guide to Monte Carlo Simulations in Statistical Physics.
    Cambridge University Press, Cambridge. MR 1781083 (2001m:82051)
  • 59. Lebeau, G. and Michel, L. (2008).
    Semiclassical analysis of a random walk on a manifold.
    Ann. Probab., to appear (arXiv:0802.0644).
  • 60. Liggett, T. M. (1985).
    Interacting particle systems, volume 276 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].
    Springer-Verlag, New York. MR 776231 (86e:60089)
  • 61. Lindvall, T. (2002).
    Lectures on the coupling method.
    Dover Publications Inc., Mineola, NY.
    Corrected reprint of the 1992 original. MR 1924231
  • 62. Liu, J. S. (2001).
    Monte Carlo Strategies in Scientific Computing.
    Springer Series in Statistics. Springer-Verlag, New York. MR 1842342 (2002i:65006)
  • 63. Lovász, L. and Vempala, S. (2006).
    Hit-and-run from a corner.
    SIAM J. Comput., 35(4):985-1005 (electronic). MR 2203735 (2007h:60041)
  • 64. Löwen, H. (2000).
    Fun with hard spheres.
    In Statistical physics and spatial statistics (Wuppertal, 1999), volume 554 of Lecture Notes in Phys., pages 295-331. Springer, Berlin. MR 1870950
  • 65. Macdonald, I. G. (1995).
    Symmetric functions and Hall polynomials.
    Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, second edition.
    With contributions by A. Zelevinsky, Oxford Science Publications. MR 1354144 (96h:05207)
  • 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. Martinelli, F. (2004).
    Relaxation times of Markov chains in statistical mechanics and combinatorial structures.
    In Probability on discrete structures, volume 110 of Encyclopaedia Math. Sci., pages 175-262. Springer, Berlin. MR 2023653 (2005b:60260)
  • 68. Meyn, S. P. and Tweedie, R. L. (1993).
    Markov chains and stochastic stability.
    Communications and Control Engineering Series. Springer-Verlag London Ltd., London. MR 1287609 (95j:60103)
  • 69. Montenegro, R. and Tetali, P. (2006).
    Mathematical aspects of mixing times in Markov chains.
    Found. Trends Theor. Comput. Sci., 1(3):x+121. MR 2341319
  • 70. Morris, B. and Sinclair, A. (2004).
    Random walks on truncated cubes and sampling $ 0-1$ knapsack solutions.
    SIAM J. Comput., 34(1):195-226 (electronic). MR 2114310 (2005k:68095)
  • 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. Newman, M. E. J. and Barkema, G. T. (1999).
    Monte Carlo methods in statistical physics.
    The Clarendon Press Oxford University Press, New York. MR 1691513 (2000m:82030)
  • 73. Ollivier, Y. (2008).
    Ricci curvature of Markov chains on metric spaces.
    Preprint, submitted, 2008.
  • 74. Pachter, L. and Sturmfels, B., editors (2005).
    Algebraic statistics for computational biology.
    Cambridge University Press, New York. MR 2205865 (2006i:92002)
  • 75. Pak, I. (2001).
    What do we know about the product replacement algorithm?
    In Groups and computation, III (Columbus, OH, 1999), volume 8 of Ohio State Univ. Math. Res. Inst. Publ., pages 301-347. de Gruyter, Berlin. MR 1829489 (2002d:20107)
  • 76. Pistone, G., Riccomagno, E., and Wynn, H. P. (2001).
    Algebraic statistics, volume 89 of Monographs on Statistics and Applied Probability.
    Chapman & Hall/CRC, Boca Raton, FL.
    Computational commutative algebra in statistics. MR 2332740 (2008f:62098)
  • 77. Propp, J. G. and Wilson, D. B. (1996).
    Exact sampling with coupled Markov chains and applications to statistical mechanics.
    In Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), volume 9, pages 223-252. MR 1611693 (99k:60176)
  • 78. Ross, S. M. (2002).
    A First Course in Probability, 7th Edition.
    Cambridge University Press, Cambridge.
  • 79. Saloff-Coste, L. (1997).
    Lectures on finite Markov chains.
    In Lectures on probability theory and statistics (Saint-Flour, 1996), volume 1665 of Lecture Notes in Math., pages 301-413. Springer, Berlin. MR 1490046 (99b:60119)
  • 80. Seress, Á. (2003).
    Permutation group algorithms, volume 152 of Cambridge Tracts in Mathematics.
    Cambridge University Press, Cambridge. MR 1970241 (2004c:20008)
  • 81. Sinclair, A. (1993).
    Algorithms for random generation and counting.
    Progress in Theoretical Computer Science. Birkhäuser Boston Inc., Boston, MA.
    A Markov chain approach. MR 1201590 (93j:65011)
  • 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. Taylor, H. M. and Karlin, S. (1984).
    An introduction to stochastic modeling.
    Academic Press Inc., Orlando, FL. MR 778728 (86j:60003)
  • 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. Thorisson, H. (2000).
    Coupling, stationarity, and regeneration.
    Probability and its Applications (New York). Springer-Verlag, New York. MR 1741181 (2001b:60003)
  • 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. Widom, B. (2002).
    Statistical Mechanics: A Concise Introduction for Chemists.
    Cambridge University Press, Cambridge. MR 1921032 (2004a:82001)
  • 89. Yau, H.-T. (1997).
    Logarithmic Sobolev inequality for generalized simple exclusion processes.
    Probab. Theory Related Fields, 109(4):507-538. MR 1483598 (99f:60171)

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.

American Mathematical Society