Honest exploration of intractable probability distributions via Markov chain Monte Carlo. (English) Zbl 1127.60309
Summary: Two important questions that must be answered whenever a Markov chain Monte Carlo (MCMC) algorithm is used are (Q1) What is an appropriate burn-in? and (Q2) How long should the sampling continue after burn-in? Developing rigorous answers to these questions presently requires a detailed study of the convergence properties of the underlying Markov chain. Consequently, in most practical applications of MCMC, exact answers to (Q1) and (Q2) are not sought. The goal of this paper is to demystify the analysis that leads to honest answers to (Q1) and (Q2). The authors hope that this article will serve as a bridge between those developing Markov chain theory and practitioners using MCMC to solve practical problems.
MSC:
| 60J05 | Discrete-time Markov processes on general state spaces |
| 65C05 | Monte Carlo methods |
| 65C40 | Numerical analysis or methods applied to Markov chains |
Software:
WinBUGSReferences:
| [1] | Athrey a, K. B. and Ney, P. (1978). A new approach to the limit theory of recurrent Markov chains. Trans. Amer. Math. Soc. 245 493-501. · Zbl 0397.60053 · doi:10.2307/1998882 |
| [2] | Besag, J., Green, P., Higdon, D. and Mengersen, K. (1995). Bayesian computation and stochastic sy stems (with discussion). Statist. Sci. 10 3-66. · Zbl 0955.62552 · doi:10.1214/ss/1177010123 |
| [3] | Billera, L. J. and Diaconis, P. (2001). A geometric interpretation of the Metropolis algorithm. Statist. Sci. 16 335-339. · Zbl 1127.60310 · doi:10.1214/ss/1015346318 |
| [4] | Bratley, P., Fox, B. L. and Schrage, L. E. (1987). A Guide to Simulation. Springer, New York. · Zbl 0515.68070 |
| [5] | Caffo, B. S., Booth, J. G. and Davison, A. C. (2001). Empirical sup rejection sampling, Technical report, Univ. Florida. · Zbl 1036.62004 |
| [6] | Chan, K. S. and Gey er, C. J. (1994). Comment on ”Markov chains for exploring posterior distributions.” Ann. Statist. 22 1747-1758. · Zbl 0829.62080 · doi:10.1214/aos/1176325750 |
| [7] | Chib, S. and Greenberg, E. (1995). Understanding the Metropolis-Hastings algorithm. Amer. Statist. 49 327-335. |
| [8] | Cowles, M. K. and Rosenthal, J. S. (1998). A simulation approach to convergence rates for Markov chain Monte Carlo algorithms. Statist. Comput. 8 115-124. |
| [9] | Crane, M. A. and Iglehart, D. L. (1975). Simulating stable stochastic sy stems III: Regenerative processes and discreteevent simulations. Oper. Res. 23 33-45. JSTOR: · Zbl 0346.60060 · doi:10.1287/opre.23.1.33 |
| [10] | Diaconis, P. and Stroock, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1 36-61. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980 |
| [11] | Diaconis, P. and Sturmfels, B. (1998). Algebraic algorithms for sampling from conditional distributions. Ann. Statist. 26 363-397. · Zbl 0952.62088 · doi:10.1214/aos/1030563990 |
| [12] | Frigessi, A., di Stefano, P., Hwang, C.-R. and Sheu, S.-J. (1993). Convergence rates of the Gibbs sampler, the Metropolis algorithm and other single-site updating dy namics. J. Roy. Statist. Soc. Ser. B 55 205-219. Gelfand, A. E., Hills, S. E., Racine-Poon, A. and Smith, A. JSTOR: · Zbl 0781.60039 |
| [13] | F. M. (1990). Illustration of Bayesian inference in normal data models using Gibbs sampling. J. Amer. Statist. Assoc. 85 972-985. |
| [14] | Gelfand, A. E. and Smith, A. F. M. (1990). Sampling-based approaches to calculating marginal densities. J. Amer. Statist. Assoc. 85 398-409. JSTOR: · Zbl 0702.62020 · doi:10.2307/2289776 |
| [15] | Gey er, C. J. (1992). Practical Markov chain Monte Carlo (with discussion). Statist. Sci. 7 473-511. |
| [16] | Gey er, C. J. and Thompson, E. A. (1995). Annealing Markov chain Monte Carlo with applications to ancestral inference. J. Amer. Statist. Assoc. 90 909-920. · Zbl 0850.62834 · doi:10.2307/2291325 |
| [17] | Gilks, W. R., Richardson, S. and Spiegelhalter, D. J. E. (1996). Markov Chain Monte Carlo in Practice. Chapman and Hall, London. · Zbl 0832.00018 |
| [18] | Gilks, W. R., Roberts, G. O. and Sahu, S. K. (1998). Adaptive Markov chain Monte Carlo through regeneration. J. Amer. Statist. Assoc. 93 1045-1054. JSTOR: · Zbl 1064.65503 · doi:10.2307/2669848 |
| [19] | Gly nn, P. W. (1985). Regenerative structure of Markov chains simulated via common random numbers. Oper. Res. Lett. 4 49-53. · Zbl 0576.60082 · doi:10.1016/0167-6377(85)90031-8 |
| [20] | Gly nn, P. W. and Iglehart, D. L. (1987). A joint central limit theorem for the sample mean and regenerative variance estimator. Ann. Oper. Res. 8 41-55. |
| [21] | Gly nn, P. W. and Iglehart, D. L. (1990). Simulation output analysis using standardized time series. Math. Oper. Res. 15 1-16. JSTOR: · Zbl 0704.65110 · doi:10.1287/moor.15.1.1 |
| [22] | Guihenneuc-Jouy aux, C. and Robert, C. P. (1998). Discretization of continuous Markov chains and Markov chain Monte Carlo convergence assessment. J. Amer. Statist. Assoc. 93 1055-1067. JSTOR: · Zbl 1013.60055 · doi:10.2307/2669849 |
| [23] | Hobert, J. P. (2001). Discussion of ”The art of data augmentation.” J. Comput. Graph. Statist. 10 59-68. JSTOR: · doi:10.1198/10618600152418584 |
| [24] | Hobert, J. P. and Gey er, C. J. (1998). Geometric ergodicity of Gibbs and blockGibbs samplers for a hierarchical random effects model. J. Multivariate Anal. 67 414-430. Hobert, J. P., Jones, G. L., Presnell, B. and Rosenthal, J. S. · Zbl 0922.60069 · doi:10.1006/jmva.1998.1778 |
| [25] | . On the applicability of regenerative simulation in Markov chain Monte Carlo. Technical report, Univ. Florida. · Zbl 1035.60080 |
| [26] | Ingrassia, S. (1994). On the rate of convergence of the Metropolis algorithm and Gibbs sampler by geometric bounds. Ann. Appl. Probab. 4 347-389. · Zbl 0802.60061 · doi:10.1214/aoap/1177005064 |
| [27] | Jarner, S. F. and Hansen, E. (2000). Geometric ergodicity of Metropolis algorithms. Stochastic Process. Appl. 85 341-361. · Zbl 0997.60070 · doi:10.1016/S0304-4149(99)00082-4 |
| [28] | Jarner, S. F. and Roberts, G. O. (2001). Poly nomial convergence rates of Markov chains. Ann. Appl. Probab. · Zbl 1012.60062 · doi:10.1214/aoap/1015961162 |
| [29] | Jones, G. L. and Hobert, J. P. (2001). Upper bounds on the distance to stationarity for the blockGibbs sampler for a hierarchical random effects model. Technical report, Univ. Florida. |
| [30] | Levine, R. A. and Casella, G. (2001). Implementations of the Monte Carlo EM algorithm. J. Comput. Graph. Statist. 10 422-439. JSTOR: · doi:10.1198/106186001317115045 |
| [31] | Lindvall, T. (1992). Lectures on the Coupling Method. Wiley Interscience, New York. · Zbl 0850.60019 |
| [32] | Liu, J. S., Wong, W. H. and Kong, A. (1994). Covariance structure of the Gibbs sampler with applications to the comparisons of estimators and augmentation schemes. Biometrika 81 27-40. JSTOR: · Zbl 0811.62080 · doi:10.1093/biomet/81.1.27 |
| [33] | Lund, R. B. and Tweedie, R. L. (1996). Geometric convergence rates for stochastically ordered Markov chains. Math. Oper. Res. 20 182-194. JSTOR: · Zbl 0847.60053 · doi:10.1287/moor.21.1.182 |
| [34] | Ly les, R. H., Kupper, L. L. and Rappaport, S. M. (1997). Assessing regulatory compliance of occupational exposures via the balanced one-way random effects ANOVA model. J. Agricultural Biol. Environ. Statist. 2 64-86. JSTOR: · doi:10.2307/1400641 |
| [35] | McCulloch, C. E. (1997). Maximum likelihood algorithms for generalized linear mixed models. J. Amer. Statist. Assoc. 92 162-170. JSTOR: · Zbl 0889.62061 · doi:10.2307/2291460 |
| [36] | Mengersen, K. and Tweedie, R. L. (1996). Rates of convergence of the Hastings and Metropolis algorithms. Ann. Statist. 24 101-121. · Zbl 0854.60065 · doi:10.1214/aos/1033066201 |
| [37] | Mey n, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability. Springer, London. · Zbl 0925.60001 |
| [38] | Mey n, S. P. and Tweedie, R. L. (1994). Computable bounds for geometric convergence rates of Markov chains. Ann. Appl. Probab. 4 981-1011. · Zbl 0812.60059 · doi:10.1214/aoap/1177004900 |
| [39] | Mira, A. and Tierney, L. (2001). On the use of auxiliary variables in Markov chain Monte Carlo sampling. Scand. J. Statist. |
| [40] | My kland, P., Tierney, L. and Yu, B. (1995). Regeneration in Markov chain samplers. J. Amer. Statist. Assoc. 90 233-241. JSTOR: · Zbl 0819.62082 · doi:10.2307/2291148 |
| [41] | Natarajan, R. and McCulloch, C. E. (1998). Gibbs sampling with diffuse proper priors: A valid approach to data-driven inference? J. Comput. Graph. Statist. 7 267-277. |
| [42] | Nummelin, E. (1978). A splitting technique for Harris recurrent Markov chains. Z. Wahrsch. Verw. Gebiete 43 309-318. · Zbl 0364.60104 · doi:10.1007/BF00534764 |
| [43] | Nummelin, E. (1984). General Irreducible Markov Chains and Non-negative Operators. Cambridge Univ. Press. · Zbl 0551.60066 |
| [44] | Ripley, B. D. (1987). Stochastic Simulation. Wiley, New York. · Zbl 0613.65006 |
| [45] | Robert, C. P. (1995). Convergence control methods for Markov chain Monte Carlo algorithms. Statist. Sci. 10 231-253. · Zbl 0955.60526 · doi:10.1214/ss/1177009937 |
| [46] | Robert, C. P. and Casella, G. (1999). Monte Carlo Statistical Methods. Springer, New York. · Zbl 0935.62005 |
| [47] | Roberts, G. O. (1999). A note on acceptance rate criteria for CLTs for Metropolis-Hastings algorithms. J. Appl. Probab. 36 1210-1217. Roberts, G. O. and Rosenthal, J. S. (1998a). Markov chain Monte Carlo: Some practical implications of theoretical results (with discussion). Canad. J. Statist. 26 5-31. Roberts, G. O. and Rosenthal, J. S. (1998b). On convergence rates of Gibbs samplers for uniform distributions. Ann. Appl. Probab. 8 1291-1302. · Zbl 0935.60054 · doi:10.1214/aoap/1028903381 |
| [48] | Roberts, G. O. and Rosenthal, J. S. (1999). Convergence of slice sampler Markov chains. J. Roy. Statist. Soc. Ser. B 61 643-660. JSTOR: · Zbl 0929.62098 · doi:10.1111/1467-9868.00198 |
| [49] | Roberts, G. O. and Sahu, S. K. (1997). Updating schemes, correlation structure, blocking and parameterization for the Gibbs sampler. J. Roy. Statist. Soc. Ser. B 59 291-317. JSTOR: · Zbl 0886.62083 · doi:10.1111/1467-9868.00070 |
| [50] | Roberts, G. O. and Tweedie, R. L. (1996). Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms. Biometrika 83 95-110. JSTOR: · Zbl 0888.60064 · doi:10.1093/biomet/83.1.95 |
| [51] | Roberts, G. O. and Tweedie, R. L. (1999). Bounds on regeneration times and convergence rates for Markov chains. Stochastic Process. Appl. 80 211-229. · Zbl 0961.60066 · doi:10.1016/S0304-4149(98)00085-4 |
| [52] | Roberts, G. O. and Tweedie, R. L. (2001). Bounds on regeneration times and convergence rates for Markov chains. (Corrigendum). Stochastic Process. Appl. 91 337-338. · Zbl 1047.60072 · doi:10.1016/S0304-4149(00)00074-0 |
| [53] | Rosenthal, J. S. (1995). Minorization conditions and convergence rates for Markov chain Monte Carlo. J. Amer. Statist. Assoc. 90 558-566. JSTOR: · Zbl 0824.60077 · doi:10.2307/2291067 |
| [54] | Rosenthal, J. S. (1996). Analy sis of the Gibbs sampler for a model related to James-Stein estimators. Statist. Comput. 6 269-275. |
| [55] | Rosenthal, J. S. (2001). A review of asy mptotic convergence for general state space Markov chains. Far East J. Theoret. Statist. 5 37-50. · Zbl 1010.60067 |
| [56] | Schmeiser, B. (1982). Batch size effects in the analysis of simulation output. Oper. Res. 30 556-568. JSTOR: · Zbl 0484.65087 · doi:10.1287/opre.30.3.556 |
| [57] | Searle, S. R., Casella, G. and McCulloch, C. E. (1992). Variance Componenets. Wiley, New York. |
| [58] | Spiegelhalter, D. J., Thomas, A. and Best, N. G. (1999). WinBUGS Version 1.2, MRC Biostatistics Unit, Cambridge, UK. |
| [59] | Tanner, M. A. and Wong, W. H. (1987). The calculation of posterior distributions by data augmentation (with discussion). J. Amer. Statist. Assoc. 82 528-550. JSTOR: · Zbl 0619.62029 · doi:10.2307/2289457 |
| [60] | Tierney, L. (1994). Markov chains for exploring posterior distributions (with discussion). Ann. Statist. 22 1701-1762. · Zbl 0829.62080 · doi:10.1214/aos/1176325750 |
| [61] | Tierney, L. (1998). A note on Metropolis-Hastings kernels for general state spaces. Ann. Appl. Probab. 8 1-9. · Zbl 0935.60053 · doi:10.1214/aoap/1027961031 |
| [62] | van Dy k, D. A. and Meng, X.-L. (2001). The art of data augmentation (with discussion). J. Comput. Graph. Statist. 10 1-111. JSTOR: · doi:10.1198/10618600152418584 |
| [63] | Yuen, W. K. (2000). Applications of geometric bounds to the convergence rate of Markov chains on n. Stochastic Process. Appl. 87 1-23. · Zbl 1045.60073 · doi:10.1016/S0304-4149(99)00101-5 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
