Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-24T03:20:21.218Z Has data issue: false hasContentIssue false
  • English
  • Français

Monte Carlo and quasi-Monte Carlo methods

Published online by Cambridge University Press:  07 November 2008

Russel E. Caflisch
Russel E. Caflisch
Affiliation:
Mathematics Department, UCLA, Los Angeles, CA 90095-1555, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Monte Carlo is one of the most versatile and widely used numerical methods. Its convergence rate, O(N−1/2), is independent of dimension, which shows Monte Carlo to be very robust but also slow. This article presents an introduction to Monte Carlo methods for integration problems, including convergence theory, sampling methods and variance reduction techniques. Accelerated convergence for Monte Carlo quadrature is attained using quasi-random (also called low-discrepancy) sequences, which are a deterministic alternative to random or pseudo-random sequences. The points in a quasi-random sequence are correlated to provide greater uniformity. The resulting quadrature method, called quasi-Monte Carlo, has a convergence rate of approximately O((logN)kN−1). For quasi-Monte Carlo, both theoretical error estimates and practical limitations are presented. Although the emphasis in this article is on integration, Monte Carlo simulation of rarefied gas dynamics is also discussed. In the limit of small mean free path (that is, the fluid dynamic limit), Monte Carlo loses its effectiveness because the collisional distance is much less than the fluid dynamic length scale. Computational examples are presented throughout the text to illustrate the theory. A number of open problems are described.

Type
Research Article
Information
Acta Numerica , Volume 7 , January 1998 , pp. 1 - 49
Copyright
Copyright © Cambridge University Press 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Acworth, P., Broadie, M. and Glasserman, P. (1997), A comparison of some Monte Carlo and quasi Monte Carlo techniques for option pricing, in Monte Carlo and Quasi-Monte Carlo Methods 1996 (Larcher, G., Niederreiter, H., Hellekalek, P. and Zinterhof, P., eds), Springer.Google Scholar
Babovsky, H., Gropengiesser, F., Neunzert, H., Struckmeier, J. and Wiesen, J. (1990), ‘Application of well-distributed sequences to the numerical simulation of the Boltzmann equation’, J. Comput. Appl. Math. 31, 15–22.CrossRefGoogle Scholar
Bardos, C., Golse, F. and Levermore, C. D. (1991), ‘Fluid dynamic limits of kinetic equations: I. Formal derivations’, J. Statist. Phys. 63, 323–344.CrossRefGoogle Scholar
Bardos, C., Golse, F. and Levermore, C. D. (1993), ‘Fluid dynamic limits of kinetic equations: II. Convergence proofs for the Boltzmann equation’, Comm. Pure Appl. Math. 46, 667–753.CrossRefGoogle Scholar
Bird, G. A. (1976), Molecular Gas Dynamics, Oxford University Press.Google Scholar
Bird, G. A. (1978), ‘Monte Carlo simulation of gas flows’, Ann. Rev. Fluid Mech. 10, 11–31.CrossRefGoogle Scholar
Borgers, C., Larsen, E. W. and Adams, M. L. (1992), ‘The asymptotic diffusion limit of a linear discontinuous discretization of a two-dimensional linear transport equation’ J. Comput. Phys. 98, 285–300.CrossRefGoogle Scholar
Bratley, P., Fox, B. L. and Niederreiter, H. (1994), ‘Algorithm 738 – Programs to generate Niederreiter's discrepancy sequences’, ACM Trans. Math. Software 20, 494–495.CrossRefGoogle Scholar
Caflisch, R. E. (1983), Fluid dynamics and the Boltzmann equation, in Nonequilibrium Phenomena I: The Boltzmann equation (Montroll, E. W. and Lebowitz, J. L., eds), Vol. 10 of Studies in Statistical Mechanics, North Holland, pp. 193–223.Google Scholar
Caflisch, R. E., Jin, S. and Russo, G. (1997a), ‘Uniformly accurate schemes for hyperbolic systems with relaxation’, SIAM J. Numer. Anal. 34, 246–281.CrossRefGoogle Scholar
Caflisch, R. E., Morokoff, W. and Owen, A. B. (1997b), ‘Valuation of mortgage-backed securities using Brownian bridges to reduce effective dimension’, J. Comput. Finance 1, 27–46.CrossRefGoogle Scholar
Cercignani, C. (1988), The Boltzmann Equation and its Applications, Springer.CrossRefGoogle Scholar
Chapman, S. and Cowling, T. G. (1970), The Mathematical Theory of Non-Uniform Gases, Cambridge University Press.Google Scholar
De Masi, A., Esposito, R. and Lebowitz, J. L. (1989), ‘Incompressible Navier–Stokes and Euler limits of the Boltzmann equation’, Comm. Pure Appl. Math. 42, 1189–1214.CrossRefGoogle Scholar
Faure, H. (1982), ‘Discrépance de suites associées à un système de numération (en dimension s)’, Acta Arithmetica 41, 337–351.CrossRefGoogle Scholar
Feller, W. (1971), An Introduction to Probability Theory and its Applications: Vol. I, Wiley.Google Scholar
Gabetta, E., Pareschi, L. and Toscani, G. (1997), ‘Relaxation schemes for nonlinear kinetic equations’, SIAM J. Numer. Anal. 34, 2168–2194.CrossRefGoogle Scholar
Goldstein, D., Sturtevant, B. and Broadwell, J. E. (1988), Investigations of the motion of discrete-velocity gases, in Rarefied Gas Dynamics: Theoretical and Computational Techniques (Muntz, E. P., Weaver, D. P. and Campbell, D. H., eds), Vol. 118 of Progress in Aeronautics and Astronautics, Proceedings of the 16th International Symposium on Rarefied Gas Dynamics, pp. 100–117.Google Scholar
Halton, J. H. (1960), ‘On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals’, Numer. Math. 2, 84–90.CrossRefGoogle Scholar
Hammersley, J. M. and Handscomb, D. C. (1965), Monte Carlo Methods, Wiley, New York.Google Scholar
Haselgrove, C. (1961), ‘A method for numerical integration’, Math. Comput. 15, 323–337.CrossRefGoogle Scholar
Hickernell, F. J. (1996), ‘The mean square discrepancy of randomized nets’, ACM Trans. Model. Comput. Simul. 6, 274–296.CrossRefGoogle Scholar
Hickernell, F. J. (1998), ‘A generalized discrepancy and quadrature error bound’, Math. Comput. 67, 299–322.CrossRefGoogle Scholar
Hogg, R. V. and Craig, A. T. (1995), Introduction to Mathematical Statistics, Prentice Hall.Google Scholar
Hua, L. K. and Wang, Y. (1981), Applications of Number Theory to Numerical Analysis, Springer, Berlin/New York.Google Scholar
Jin, S. and Levermore, C. D. (1993), ‘Fully-discrete numerical transfer in diffusive regimes’, Transp. Theory Statist. Phys., 22, 739–791.CrossRefGoogle Scholar
Jin, S., Pareschi, L. and Toscani, G. (1998), ‘Diffusive relaxation schemes for discrete-velocity kinetic equations’. Preprint.CrossRefGoogle Scholar
Kalos, M. H. and Whitlock, P. A. (1986), Monte Carlo Methods, Vol. I: Basics, Wiley, New York.CrossRefGoogle Scholar
Karatzas, I. and Shreve, S. E. (1991), Brownian Motion and Stochastic Calculus, Springer, New York.Google Scholar
Kennedy, W. J. and Gentle, J. E. (1980), Statistical Computing, Dekker, New York.Google Scholar
Koura, K. (1986), ‘Null-collision technique in the direct-simulation Monte Carlo method’, Phys. Fluids 29, 3509–3511.CrossRefGoogle Scholar
Kuipers, L. and Niederreiter, H. (1974), Uniform Distribution of Sequences, Wiley, New York.Google Scholar
Larsen, E. W. (1984), ‘Diffusion-synthetic acceleration methods for discrete-ordinates problems’, Transp. Theory Statist. Phys. 13, 107–126.CrossRefGoogle Scholar
Larsen, E. W., Morel, J. E. and Miller, W. F. (1987), ‘Asymptotic solutions of numerical transport problems in optically thick, diffusive regimes’, J. Comput. Phys. 69, 283–324.CrossRefGoogle Scholar
Lepage, G. (1978), ‘A new algorithm for adaptive multidimensional integration’, J. Comput. Phys. 27, 192–203.CrossRefGoogle Scholar
Marsaglia, G. (1991), ‘Normal (Gaussian) random variables for supercomputers’, J. Supercomputing 5, 49–55.CrossRefGoogle Scholar
Morokoff, W. and Caflisch, R. E. (1993), ‘A quasi-Monte Carlo approach to particle simulation of the heat equation’, SIAM J. Numer. Anal. 30, 1558–1573.CrossRefGoogle Scholar
Morokoff, W. and Caflisch, R. E. (1994), ‘Quasi-random sequences and their discrepancies’, SIAM J. Sci. Statist. Comput. 15, 1251–1279.CrossRefGoogle Scholar
Morokoff, W. and Caflisch, R. E. (1995), ‘Quasi-Monte Carlo integration’, J. Comput. Phys. 122, 218–230.CrossRefGoogle Scholar
Moskowitz, B. and Caflisch, R. E. (1996), ‘Smoothness and dimension reduction in quasi-Monte Carlo methods’, J. Math. Comput. Modeling 23, 37–54.CrossRefGoogle Scholar
Nanbu, K. (1986), Theoretical basis of the direct simulation Monte Carlo method, in Proceedings of the 15th International Symposium on Rarefied Gas Dynamics (Boffi, V. and Cercignani, C., eds), Vol. I, pp. 369–383.Google Scholar
Niederreiter, H. (1992), Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, PA.CrossRefGoogle Scholar
Owen, A. B. (1995), Randomly permuted (t, m, s)-nets and (t, s)-sequences, in Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (Niederreiter, H. and Shiue, P. J.-S., eds), Springer, New York, pp. 299–317.CrossRefGoogle Scholar
Owen, A. B. (1997), ‘Monte Carlo variance of scrambled net quadrature’, SIAM J. Numer. Anal. 34, 1884–1910.CrossRefGoogle Scholar
Owen, A. B. (1998), ‘Scrambled net variance for integrals of smooth functions’, Ann. Statist. In press.Google Scholar
Press, W. H. and Teukolsky, S. A. (1992), ‘Portable random number generators’, Comput. Phys. 6, 522–524.CrossRefGoogle Scholar
Press, W. H., Teukolsky, S. A., Vettering, W. T. and Flannery, B. P. (1992), Numerical Recipes in C: The Art of Scientific Computing, 2nd edn, Cambridge University Press.Google Scholar
Pullin, D. I. (1979), ‘Generation of normal variates with given sample and mean variance’, J. Statist. Comput. Simul. 9, 303–309.CrossRefGoogle Scholar
Sobol, I. M.' (1967), ‘The distribution of points in a cube and the accurate evaluation of integrals’, Zh. Vychisl. Mat. Mat. Fiz. 7, 784–802. In Russian.Google Scholar
Sobol, I. M.' (1976), ‘Uniformly distributed sequences with additional uniformity property’, USSR Comput. Math. Math. Phys. 16, 1332–1337.CrossRefGoogle Scholar
Spanier, J. and Maize, E. H. (1994), ‘Quasi-random methods for estimating integrals using relatively small samples’, SIAM Rev. 36, 18–44.CrossRefGoogle Scholar
Wagner, W. (1992), ‘A convergence proof for Bird's Direct Simulation Monte Carlo method for the Boltzmann equation’, J. Statist. Phys. 66, 1011–1044.CrossRefGoogle Scholar
Woźniakowski, H. (1991), ‘Average case complexity of multivariate integration’, Bull. Amer. Math. Soc. 24, 185–194.CrossRefGoogle Scholar
Xing, C. P. and Niederreiter, H. (1995), ‘A construction of low-discrepancy sequences using global function fields’, Acta Arithmetica 73, 87–102.CrossRefGoogle Scholar
Zaremba, S. K. (1968), ‘The mathematical basis of Monte Carlo and quasi-Monte Carlo methods’, SIAM Rev. 10, 303–314.CrossRefGoogle Scholar