×

zbMATH — the first resource for mathematics

The Markov chain Monte Carlo revolution. (English) Zbl 1168.60032
The use of simulations for high-dimensional intractable computations is considered. The principle tool is the Metropolis algorithm for properly designed time-homogeneous Markov chain. Some elegant examples (cryptography problem, Markov chains on permutations, hard disks in a box) leading to really fascinating mathematics are analyzed. The estimates of the rate of convergency are based on the analysis of the self-adjoint operators.

MSC:
60J22 Computational methods in Markov chains
Software:
BaM
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aldous, D. and Fill, J. (2002). Reversible Markov chains and random walks on graphs. Monograph.
[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. · Zbl 0731.60067
[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. · Zbl 1056.60006
[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. · Zbl 1146.60058
[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. · Zbl 1186.26011
[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. · Zbl 0744.60032
[8] Louis J. Billera and Persi Diaconis, A geometric interpretation of the Metropolis-Hastings algorithm, Statist. Sci. 16 (2001), no. 4, 335 – 339. · Zbl 1127.60310
[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. · Zbl 0822.60002
[10] Pierre Brémaud, Markov chains, Texts in Applied Mathematics, vol. 31, Springer-Verlag, New York, 1999. Gibbs fields, Monte Carlo simulation, and queues. · Zbl 0949.60009
[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. · Zbl 0957.60083
[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. · Zbl 1080.62065
[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. · Zbl 1149.43001
[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. · Zbl 0949.65005
[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. · Zbl 1117.62310
[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. · Zbl 0589.62041
[19] 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. · Zbl 0695.60012
[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. · Zbl 0375.62045
[21] Donald St. P. Richards , Hypergeometric functions on domains of positivity, Jack polynomials, and applications, Contemporary Mathematics, vol. 138, American Mathematical Society, Providence, RI, 1992. · Zbl 0771.00045
[22] Persi Diaconis and I. M. Isaacs, Supercharacters and superclasses for algebra groups, Trans. Amer. Math. Soc. 360 (2008), no. 5, 2359 – 2392. · Zbl 1137.20008
[23] Diaconis, P., Khare, K., and Saloff-Coste, L. (2008a). Gibbs sampling, exponential families and orthogonal polynomials, with discussion. Statist. Sci., to appear. · Zbl 1327.62058
[24] Diaconis, P. and Lebeau, G. (2008). Micro-local analysis for the Metropolis algorithm. Math. Z., to appear. · Zbl 1178.60053
[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. · Zbl 1227.60093
[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. · Zbl 1058.65010
[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. · Zbl 0998.60069
[29] Persi Diaconis and Laurent Saloff-Coste, Comparison theorems for reversible Markov chains, Ann. Appl. Probab. 3 (1993), no. 3, 696 – 730. · Zbl 0799.60058
[30] P. Diaconis and L. Saloff-Coste, Nash inequalities for finite Markov chains, J. Theoret. Probab. 9 (1996), no. 2, 459 – 510. · Zbl 0870.60064
[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). · Zbl 0920.68054
[32] Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159 – 179. · Zbl 0485.60006
[33] Persi Diaconis and Bernd Sturmfels, Algebraic algorithms for sampling from conditional distributions, Ann. Statist. 26 (1998), no. 1, 363 – 397. · Zbl 0952.62088
[34] Diaconis, P. and Thiem, N. (2008). Supercharacter formulas for pattern groups. Trans. Amer. Math. Soc., to appear. · Zbl 1205.20006
[35] Dobrushin, R. L. (1970). Prescribing a system of random variables by conditional distributions. Theor. Probab. Appl.- Engl. Tr., 15:453-486. · Zbl 0264.60037
[36] Doucet, A., de Freitas, N., and Gordon, N. (2001). Sequential Monte Carlo in Practice. Springer-Verlag, New York. · Zbl 0967.00022
[37] Christophe Dress and Werner Krauth, Cluster algorithm for hard spheres and related systems, J. Phys. A 28 (1995), no. 23, L597 – L601. · Zbl 0877.60094
[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. · Zbl 0592.60049
[39] William Feller, An introduction to probability theory and its applications. Vol. I, Third edition, John Wiley & Sons, Inc., New York-London-Sydney, 1968. · Zbl 0077.12201
[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. · Zbl 0726.60069
[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. · Zbl 0889.65132
[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. · Zbl 0838.31001
[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. · Zbl 1033.62024
[44] J. M. Hammersley and D. C. Handscomb, Monte Carlo methods, Methuen & Co., Ltd., London; Barnes & Noble, Inc., New York, 1965. · Zbl 0121.35503
[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. · Zbl 1035.60080
[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. · Zbl 1091.20001
[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. · Zbl 1141.81005
[49] Hosten, S. and Meek, C. (2006). Preface. 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. · Zbl 0997.60070
[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. · Zbl 1204.65044
[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. · Zbl 1127.60309
[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. · Zbl 1205.60137
[55] Wilfrid S. Kendall, Geometric ergodicity and perfect simulation, Electron. Comm. Probab. 9 (2004), 140 – 151. · Zbl 1061.60070
[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. · Zbl 1016.60066
[57] 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. · Zbl 1144.82002
[58] David P. Landau and Kurt Binder, A guide to Monte Carlo simulations in statistical physics, Cambridge University Press, Cambridge, 2000. · Zbl 0998.82504
[59] Lebeau, G. and Michel, L. (2008). Semiclassical analysis of a random walk on a manifold. Ann. Probab., to appear (arXiv:0802.0644). · Zbl 1187.58033
[60] Thomas M. Liggett, Interacting particle systems, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. · Zbl 0559.60078
[61] Torgny Lindvall, Lectures on the coupling method, Dover Publications, Inc., Mineola, NY, 2002. Corrected reprint of the 1992 original. · Zbl 1013.60001
[62] Jun S. Liu, Monte Carlo strategies in scientific computing, Springer Series in Statistics, Springer-Verlag, New York, 2001. · Zbl 0991.65001
[63] László Lovász and Santosh Vempala, Hit-and-run from a corner, SIAM J. Comput. 35 (2006), no. 4, 985 – 1005. · Zbl 1103.52002
[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.
[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. · Zbl 0899.05068
[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. · Zbl 1206.82058
[68] S. P. Meyn and R. L. Tweedie, Markov chains and stochastic stability, Communications and Control Engineering Series, Springer-Verlag London, Ltd., London, 1993. · Zbl 0925.60001
[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. · Zbl 1193.68138
[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. · Zbl 1101.68044
[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). · Zbl 1171.53011
[72] M. E. J. Newman and G. T. Barkema, Monte Carlo methods in statistical physics, The Clarendon Press, Oxford University Press, New York, 1999. · Zbl 1012.82019
[73] Ollivier, Y. (2008). Ricci curvature of Markov chains on metric spaces. Preprint, submitted, 2008. · Zbl 1181.53015
[74] Lior Pachter and Bernd Sturmfels , Algebraic statistics for computational biology, Cambridge University Press, New York, 2005. · Zbl 1108.62118
[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. · Zbl 0986.68172
[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. · Zbl 0960.62003
[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. , https://doi.org/10.1002/(SICI)1098-2418(199608/09)9:1/23.3.CO;2-R · Zbl 0859.60067
[78] Ross, S. M. (2002). A First Course in Probability, 7th Edition. Cambridge University Press, Cambridge. · Zbl 0327.60003
[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. · Zbl 0885.60061
[80] Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. · Zbl 1028.20002
[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. · Zbl 0780.68096
[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. · Zbl 0928.05001
[83] Howard M. Taylor and Samuel Karlin, An introduction to stochastic modeling, Academic Press, Inc., Orlando, FL, 1984. · Zbl 0796.60001
[84] Thiem, N. and Marberg, E. (2008). Superinduction for pattern groups. Technical report, Department of Mathematics, University of Colorado, Boulder. · Zbl 1190.20038
[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. · Zbl 1190.20039
[86] Hermann Thorisson, Coupling, stationarity, and regeneration, Probability and its Applications (New York), Springer-Verlag, New York, 2000. · Zbl 0949.60007
[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. · Zbl 0162.29302
[88] Tung Tsang, Statistical mechanics, Rinton Press, Incorporated, Princeton, NJ, 2002. · Zbl 1007.82002
[89] Horng-Tzer Yau, Logarithmic Sobolev inequality for generalized simple exclusion processes, Probab. Theory Related Fields 109 (1997), no. 4, 507 – 538. · Zbl 0903.60087
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.