Book contents
- Frontmatter
- Contents
- Preface to the Second Edition
- Preface to the First Edition
- 1 Algorithms and Computers
- 2 Computer Arithmetic
- 3 Matrices and Linear Equations
- 4 More Methods for Solving Linear Equations
- 5 Regression Computations
- 6 Eigenproblems
- 7 Functions: Interpolation, Smoothing, and Approximation
- 8 Introduction to Optimization and Nonlinear Equations
- 9 Maximum Likelihood and Nonlinear Regression
- 10 Numerical Integration and Monte Carlo Methods
- 11 Generating Random Variables from Other Distributions
- 12 Statistical Methods for Integration and Monte Carlo
- 13 Markov Chain Monte Carlo Methods
- 14 Sorting and Fast Algorithms
- Author Index
- Subject Index
- References
10 - Numerical Integration and Monte Carlo Methods
Published online by Cambridge University Press: 01 June 2011
Book contents
- Frontmatter
- Contents
- Preface to the Second Edition
- Preface to the First Edition
- 1 Algorithms and Computers
- 2 Computer Arithmetic
- 3 Matrices and Linear Equations
- 4 More Methods for Solving Linear Equations
- 5 Regression Computations
- 6 Eigenproblems
- 7 Functions: Interpolation, Smoothing, and Approximation
- 8 Introduction to Optimization and Nonlinear Equations
- 9 Maximum Likelihood and Nonlinear Regression
- 10 Numerical Integration and Monte Carlo Methods
- 11 Generating Random Variables from Other Distributions
- 12 Statistical Methods for Integration and Monte Carlo
- 13 Markov Chain Monte Carlo Methods
- 14 Sorting and Fast Algorithms
- Author Index
- Subject Index
- References
Summary
Introduction
The juxtaposition of these two topics may appear strange to many readers. Upon further reflection, the common thread of spreading points in space may become apparent. My point in combining these topics is to emphasize that this thread is not weak. Monte Carlo should be viewed as just another way to compute an integral; numerical integration should be viewed as just another way to sample points in space. Great gains can be made by exploiting the strengths of one approach when the other is floundering. Only with the willingness to adjust one's viewpoint and use these tools in combination can the full array of techniques be brought to bear on a difficult problem.
Tools such as Riemann sums and Simpson's rule characterize the set of tools known as fixed quadrature or simply quadrature. A viewpoint of these methods as a discretization of the continuous problem of integration is indeed naive. The points are spread in a fixed way in space, with the number of points set in advance. Most of these methods employ a weighting scheme, so that the points (abscissas) where a function is to be evaluated have varying importance. For estimating an integral by evaluating a function at N points in one dimension, the error converges to zero at a rate of O(N-2) or better, depending on the smoothness of the function. In higher dimensions, however, this rate slows considerably.
- Type
- Chapter
- Information
- Numerical Methods of Statistics , pp. 257 - 302Publisher: Cambridge University PressPrint publication year: 2011
References
, , , , , and (1972), Robust Estimates of Location. Princeton, NJ: Princeton University Press.Google Scholar
and (1976), “Improving a Poor Random Number Generator,” ACM Transactions on Mathematical Software 2: 59–64.CrossRefGoogle Scholar
and (1979), “Quasi-Random Number Sequences from a Long-Period TLP Generator with Remarks on Application to Cryptography,” Computing Surveys 11: 357–70.CrossRefGoogle Scholar
(1994), “Analysis of Random Number Generators Using Monte Carlo Simulation,” International Journal of Modern Physics C 5: 547–60.CrossRefGoogle Scholar
and (1976), “Randomization of Number Theoretic Methods for Multiple Integration,” SIAM Journal of Numerical Analysis 13: 904–14.CrossRefGoogle Scholar
, , and (1992), “Monte Carlo Simulations: Hidden Errors from ‘Good’ Random Number Generators,” Physical Review Letters 69: 3382–4.CrossRefGoogle ScholarPubMed
and (1982), “A Statistical Evaluation of Multiplicative Congruential Generators with Modulus 231 – 1,” Journal of the American Statistical Association 77: 129–36.Google Scholar
and (1986), “An Exhaustive Analysis of Multiplicative Congruential Random Number Generators with Modulus 231 – 1,” SIAM Journal of Scientific and Statistical Computing 7: 24–45.CrossRefGoogle Scholar
and (Eds.) (1991), Statistical Multiple Integration (Contemporary Mathematics Series, vol. 115). Providence, RI: American Mathematical Society.CrossRefGoogle Scholar
and (1983), “The k-Distribution of Generalized Feedback Shift Register Pseudorandom Numbers,” Communications of the ACM 26: 516–23.CrossRefGoogle Scholar
(1989), “Bayesian Inference in Econometric Models Using Monte Carlo Integration,” Econometrica 57: 1317–39.CrossRefGoogle Scholar
(1976), “The Spectral Test for the Evaluation of Congruential Pseudo-random Generators,” Applied Statistics 25: 173–80. [Corrections in Volume 25, p. 324 (Golder) and Volume 27, pp. 375–6 (Hoaglin and King).]CrossRefGoogle Scholar
and (1969), “Calculation of Gauss Quadrature Rules,” Mathematics of Computation 23: 221–30.CrossRefGoogle Scholar
(1973), “A Monte Carlo Swindle for Estimators of Location,” Applied Statistics 22: 347–53.CrossRefGoogle Scholar
and (1964), “Algorithm 247: Radical-Inverse Quasi-Random Point Sequence,” Communications of the ACM 7: 701–2.CrossRefGoogle Scholar
and (1993), “A Portable Random Number Generator Well Suited for the Rejection Method,” ACM Transactions on Mathematical Software 19: 489–95.CrossRefGoogle Scholar
and (1981), Applications of Number Theory to Numerical Analysis. New York: Springer-Verlag.CrossRefGoogle Scholar
and (1974), “A Table of Good Lattice Points in Three Dimensions,” Numerische Mathematik 23: 175–80.CrossRefGoogle Scholar
(1997), The Art of Computer Programming (vol. 2: Seminumerical Algorithms), 3rd ed. Reading, MA: Addison-Wesley.Google Scholar
(1988), “Efficient and Portable Random Number Generators,” Communications of the ACM 31: 742–9, 774.CrossRefGoogle Scholar
, , and (1969), “A Pseudo-random Number Generator for the System/360,” IBM Systems Journal 2: 136–46.CrossRefGoogle Scholar
and (1973), “Generalized Feedback Shift Register Pseudorandom Number Algorithm,” Journal of the Association for Computing Machinery 30: 456–68.CrossRefGoogle Scholar
(1972), “Recherche et Utilisation des ‘Bons Treillis.’ Programmation et Resultats Numeriques,” in (Ed.), Applications of Number Theory to Numerical Analysis, pp. 121–201. New York: Academic Press.CrossRefGoogle Scholar
(1968), “Random Numbers Fall Mainly in the Planes,” Proceedings of the National Academy of Sciences 61: 25–8.CrossRefGoogle ScholarPubMed
(1972), “The Structure of Linear Congruential Sequences,” in (Ed.), Applications of Number Theory to Numerical Analysis, pp. 249–85. New York: Academic Press.CrossRefGoogle Scholar
(1985), “A Current View of Random Number Generators,” in (Ed.), Computer Science and Statistics: Proceedings of the Sixteenth Symposium on the Interface, pp. 3–10. Amsterdam: North-Holland.Google Scholar
and (1998), “Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator,” ACM Transactions on Modeling and Computer Simulation, 8: 3–30.CrossRefGoogle Scholar
(1980), “The Approximation of Multiple Integrals by using Interpolatory Cubature Formulae,” in and (Eds.), Quantitative Approximation, pp. 217–43. New York: Academic Press.CrossRefGoogle Scholar
(1978), “Quasi–Monte Carlo Methods and Pseudo-Random Numbers,” Bulletin of the American Mathematical Society 84: 957–1041.CrossRefGoogle Scholar
(1987), “Statistical Analysis of Generalized Feedback Shift Register Pseudorandom Generators,” SIAM Journal of Scientific and Statistical Computing 8: 1035–51.CrossRefGoogle Scholar
(1992), Random Number Generation and Quasi–Monte Carlo Methods. Philadelphia: SIAM.CrossRefGoogle Scholar
, , and (2006), “Improved Long-Period Generators Based on Linear Recurrences Modulo 2,” ACM Transactions on Mathematical Software 32: 1–16.CrossRefGoogle Scholar
and (1988), “Random Number Generators: Good Ones Are Hard to Find,” Communications of the ACM 31: 1192–1201.CrossRefGoogle Scholar
(1988), “Discrepancy and Integration of Continuous Functions,” Journal of Approximation Theory 52: 121–31.CrossRefGoogle Scholar
(1970), “Variance Reduction Techniques for Monte Carlo Sampling from Student Distributions,” Technometrics 12: 499–515.CrossRefGoogle Scholar
(1983), “Computer Generation of Random Variables: A Tutorial,” International Statistical Review 51: 301–19.CrossRefGoogle Scholar
(1987), Stochastic Simulation. New York: Wiley.
(1979), “A More Portable Fortran Random Number Generator,” ACM Transactions on Mathematical Software 5: 132–8.CrossRefGoogle Scholar
(1976), “Computer Simulation Swindles, with Applications to Estimates of Location and Dispersion,” Applied Statistics 25: 266–74.CrossRefGoogle Scholar
(1971), Approximate Calculation of Multiple Integrals. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
and (1984), “Monte Carlo Comparison of ANOVA, MIVQUE, REML, and ML Estimators of Variance Components,” Technometrics 26: 47–57.CrossRefGoogle Scholar
(1965), “Random Numbers Generated by Linear Recurrence Modulo Two,” Mathematics of Computation 19: 201–9.CrossRefGoogle Scholar
and (1982), “Algorithm AS 183: An Efficient and Portable Pseudorandom Number Generator,” Applied Statistics 31: 188–90; 33: 123.CrossRefGoogle Scholar