The Markov chain Monte Carlo revolution

Diaconis, Persi

doi:10.1090/S0273-0979-08-01238-X

The Markov chain Monte Carlo revolution
HTML articles powered by AMS MathViewer

by Persi Diaconis PDF

Bull. Amer. Math. Soc. 46 (2009), 179-205 Request permission

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

Computer simulation of liquids

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, DOI 10.1007/978-1-4612-3038-0
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, DOI 10.1016/j.jalgebra.2004.04.005
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, DOI 10.1016/j.jfa.2007.11.002

Electron Comm. Probab.

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
Louis J. Billera and Persi Diaconis, A geometric interpretation of the Metropolis-Hastings algorithm, Statist. Sci. 16 (2001), no. 4, 335–339. MR 1888448, DOI 10.1214/ss/1015346318
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
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, DOI 10.1007/978-1-4757-3124-8

FOCS

Krzysztof Burdzy and Wilfrid S. Kendall, Efficient Markovian couplings: examples and counterexamples, Ann. Appl. Probab. 10 (2000), no. 2, 362–409. MR 1768241, DOI 10.1214/aoap/1019487348
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
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, DOI 10.1017/CBO9780511619823
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, DOI 10.1007/978-1-4612-1276-8
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, DOI 10.1198/016214504000001303
Douglas E. Critchlow, Metric methods for analyzing partially ranked data, Lecture Notes in Statistics, vol. 34, Springer-Verlag, Berlin, 1985. MR 818986, DOI 10.1007/978-1-4612-1106-8
Persi Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069
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 652736
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, DOI 10.1090/conm/138
Persi Diaconis and I. M. Isaacs, Supercharacters and superclasses for algebra groups, Trans. Amer. Math. Soc. 360 (2008), no. 5, 2359–2392. MR 2373317, DOI 10.1090/S0002-9947-07-04365-6

Statist. Sci.

Math. Z.

Persi Diaconis and J. W. Neuberger, Numerical results for the Metropolis algorithm, Experiment. Math. 13 (2004), no. 2, 207–213. MR 2068894
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, DOI 10.1307/mmj/1030132713
Persi Diaconis and Laurent Saloff-Coste, Comparison theorems for reversible Markov chains, Ann. Appl. Probab. 3 (1993), no. 3, 696–730. MR 1233621
P. Diaconis and L. Saloff-Coste, Nash inequalities for finite Markov chains, J. Theoret. Probab. 9 (1996), no. 2, 459–510. MR 1385408, DOI 10.1007/BF02214660
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, DOI 10.1006/jcss.1998.1576
Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159–179. MR 626813, DOI 10.1007/BF00535487
Persi Diaconis and Bernd Sturmfels, Algebraic algorithms for sampling from conditional distributions, Ann. Statist. 26 (1998), no. 1, 363–397. MR 1608156, DOI 10.1214/aos/1030563990

Trans. Amer. Math. Soc.

Theor. Probab. Appl.– Engl. Tr.

Sequential Monte Carlo in Practice

Christophe Dress and Werner Krauth, Cluster algorithm for hard spheres and related systems, J. Phys. A 28 (1995), no. 23, L597–L601. MR 1381129
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, DOI 10.1002/9780470316658
William Feller, An introduction to probability theory and its applications. Vol. I, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020
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

Understanding molecular simulation: From algorithms to applications, 2nd edition

Dirichlet forms and symmetric Markov processes

de Gruyter Studies in Mathematics

Bayesian methods: a social and behavioral sciences approach, 2nd ed.

J. M. Hammersley and D. C. Handscomb, Monte Carlo methods, Methuen & Co., Ltd., London; Barnes & Noble, Inc., New York, 1965. MR 0223065

Supercharacter theories of finite simple groups

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, DOI 10.1093/biomet/89.4.731
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, DOI 10.1201/9781420035216
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

J. Symb. Comput.

Søren Fiig Jarner and Ernst Hansen, Geometric ergodicity of Metropolis algorithms, Stochastic Process. Appl. 85 (2000), no. 2, 341–361. MR 1731030, DOI 10.1016/S0304-4149(99)00082-4

Phys. Lett. A

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. MR 2147852, DOI 10.1145/1008731.1008738
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, DOI 10.1214/ss/1015346317
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, DOI 10.1007/978-3-540-24587-2_{6}8
Wilfrid S. Kendall, Geometric ergodicity and perfect simulation, Electron. Comm. Probab. 9 (2004), 140–151. MR 2108860, DOI 10.1214/ECP.v9-1117
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, DOI 10.1214/aoap/1042765670
Werner Krauth, Statistical mechanics, Oxford Master Series in Physics, vol. 13, Oxford University Press, Oxford, 2006. Algorithms and computations; Oxford Master Series in Statistical Computational, and Theoretical Physics. MR 2370557
David P. Landau and Kurt Binder, A guide to Monte Carlo simulations in statistical physics, Cambridge University Press, Cambridge, 2000. MR 1781083

Ann. Probab.

Thomas M. Liggett, Interacting particle systems, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. MR 776231, DOI 10.1007/978-1-4613-8542-4
Torgny Lindvall, Lectures on the coupling method, Dover Publications, Inc., Mineola, NY, 2002. Corrected reprint of the 1992 original. MR 1924231
Jun S. Liu, Monte Carlo strategies in scientific computing, Springer Series in Statistics, Springer-Verlag, New York, 2001. MR 1842342
László Lovász and Santosh Vempala, Hit-and-run from a corner, SIAM J. Comput. 35 (2006), no. 4, 985–1005. MR 2203735, DOI 10.1137/S009753970544727X
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, DOI 10.1007/3-540-45043-2_{1}1
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

J. Phys. Conf. Ser.

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, DOI 10.1007/978-3-662-09444-0_{4}
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, DOI 10.1007/978-1-4471-3267-7
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, DOI 10.1561/0400000003
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, DOI 10.1137/S0097539702411915

J. Funct. Anal.

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
Lior Pachter and Bernd Sturmfels (eds.), Algebraic statistics for computational biology, Cambridge University Press, New York, 2005. MR 2205865, DOI 10.1017/CBO9780511610684
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
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
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, DOI 10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.3.CO;2-R

A First Course in Probability, 7th Edition

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, DOI 10.1007/BFb0092621
Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241, DOI 10.1017/CBO9780511546549
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, DOI 10.1007/978-1-4612-0323-0

Enumerative combinatorics. Vol. 2

Cambridge Studies in Advanced Mathematics

Howard M. Taylor and Samuel Karlin, An introduction to stochastic modeling, Academic Press, Inc., Orlando, FL, 1984. MR 778728
Hermann Thorisson, Coupling, stationarity, and regeneration, Probability and its Applications (New York), Springer-Verlag, New York, 2000. MR 1741181, DOI 10.1007/978-1-4612-1236-2

Fundamental Problems in Statistical Mechanics

Tung Tsang, Statistical mechanics, Rinton Press, Incorporated, Princeton, NJ, 2002. MR 1921032
Horng-Tzer Yau, Logarithmic Sobolev inequality for generalized simple exclusion processes, Probab. Theory Related Fields 109 (1997), no. 4, 507–538. MR 1483598, DOI 10.1007/s004400050140