×

General hit-and-run Monte Carlo sampling for evaluating multidimensional integrals. (English) Zbl 0912.65011

Oper. Res. Lett. 19, No. 4, 161-169 (1996); erratum ibid. 21, 209 (1997).
Summary: We elaborate on the hit-and-run sampler, a Monte Carlo approach that estimates the value of a high-dimensional integral with integrand \(h(\underline x)f(\underline x)\) by sampling from a time-reversible Markov chain over the support of the density \(f\). The Markov chain transitions are defined by choosing a random direction and then moving to a new point \(\underline x\) whose likelihood depends on \(f\) in that direction. The serially dependent observations of \(h(\underline x_i)\) are averaged to estimate the integral. The sampler applies directly to \(f\) being a nonnegative function with finite integral.
We generalize the convergence results of C. J. P. Bélisle, H. E. Romeijn and R. L. Smith [Math. Oper. Res. 18, No. 2, 255-266 (1993; Zbl 0771.60052)] to unbounded regions and to unbounded integrands. Here convergence is of the point estimator to the value of the integral; this convergence is based on convergence in distribution of realizations to their limiting distribution \(f\).
An important application is determining properties of Bayesian posterior distributions. Here \(f\) is proportional to the posterior density and \(h\) is chosen to indicate the property being estimated. Typical properties include means, variances, correlations, probabilities of regions, and predictive densities.

MSC:

65D32 Numerical quadrature and cubature formulas
65C05 Monte Carlo methods

Citations:

Zbl 0771.60052
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Applegate, D.; Kannan, R.; Polson, N., Random polynomial time algorithms for sampling from joint distributions, (Technical Report 500 (1990), Department of Statistics, Carnegie Mellon University)
[2] Barker, A. A., Monte Carlo calculations of the radial distribution functions for a protonelectron plasma, Austral. J. Phys., 18, 119-133 (1965)
[3] Belisle, C. J.P.; Romeijn, H. E.; Smith, R. L., Hit-and-Run algorithms for generating multivariate distributions, Math. Oper. Res., 18, 255-266 (1993) · Zbl 0771.60052
[4] Berger, J. O.; Chen, M.-H., Predicting retirement patterns: Prediction for a multinomial distribution with constrained parameter space, Statistician, 42, 427-443 (1993)
[5] Chen, M.-H., Monte Carlo Markov chain sampling for Bayesian computation, with applications to constrained parameter spaces (1993), Department of Statistics, Purdue University, unpublished Ph.D. Dissertation
[6] Chen, M.-H.; Deely, J. J., Application of a new Gibbs Hit-and-Run sampler to a constrained linear multiple regression problem, (Technical Report 92-21 (1992), Department of Statistics, Purdue University)
[7] Devroye, L., Non-Uniform Random Variate Generation (1986), Springer: Springer New York · Zbl 0593.65005
[8] Diebolt, J.; Robert, C., Bayesian estimation of finite mixture distributions, (Technical Report (1990), Laboratoire de Statistique Théorique et Appliquée, Universite Paris VI) · Zbl 0796.62028
[9] Gelfand, A. E.; Smith, A. F.M., Sampling based approaches to calculating marginal densities, J. Amer. Statist. Assoc., 85, 398-409 (1990) · Zbl 0702.62020
[10] Geweke, J., Bayesian inference in econometric models using Monte Carlo integration, Econometrika, 57, 1317-1339 (1989) · Zbl 0683.62068
[11] Hastings, W. K., Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57, 97-109 (1970) · Zbl 0219.65008
[12] D.E. Kaufman and R.L. Smith, “Optimal direction choice for Hit-and-Run sampling”, Oper. Res.; D.E. Kaufman and R.L. Smith, “Optimal direction choice for Hit-and-Run sampling”, Oper. Res. · Zbl 1009.62597
[13] Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E., Equations of state calculations by fast computing machines, J. Chem. Phys., 21, 1087-1092 (1953) · Zbl 1431.65006
[14] Müller, P., A genetic approach to posterior integration and Gibbs sampling, (Technical Report 91-09 (1991), Department of Statistics, Purdue University)
[15] Naylor, J. C.; Smith, A. F.M., Econometric illustrations of novel numerical integration strategies for Bayesian inference, J. Econom., 38, 103-125 (1988)
[16] Naylor, J. C.; Smith, A. F.M., Applications of a method for the efficient computation of posterior distributions, Appl. Statist., 31, 214-225 (1982) · Zbl 0521.65017
[17] Nummelin, E., General Irreducible Markov Chains and Non-Negative Operators (1984), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0551.60066
[18] Peskun, P. H., Optimum Monte-Carlo sampling using Markov chains, Biometrika, 60, 607-612 (1973) · Zbl 0271.62041
[19] Revuz, D., Markov Chains (1975), North-Holland: North-Holland Amsterdam · Zbl 0332.60045
[20] Romeijn, H. E.; Smith, R. L., Sampling through random walks, (Technical Report 90-2 (1990), Department of Industrial and Operations Engineering, The University of Michigan)
[21] Schmeiser, B. W.; Chen, M.-H., On Hit-and-Run Monte Carlo sampling for evaluating multidimensional integrals, (Technical Report 91-39 (1991), Department of Statistics, Purdue University), revision of · Zbl 0912.65011
[22] Tanner, M. A.; Wong, W. H., The calculation of posterior distributions by data augmentation, J. Amer. Statist. Assoc., 82, 528-550 (1987) · Zbl 0619.62029
[23] Tierney, L., Markov chains for exploring posterior distributions, Ann. Statist., 22, 1701-1762 (1994), (with discussion) · Zbl 0829.62080
[24] Tierney, L.; Kadane, J., Accurate approximation for posterior moments and marginal densities, J. Amer. Statist. Assoc., 81, 82-86 (1986) · Zbl 0587.62067
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.