Quasi-monte carlo methods in practice: quasi-monte carlo methods for simulation

ABSTRACT

Quasi-Monte Carlo (QMC) methods are numerical techniques for estimating large-dimensional integrals, usually over the unit hypercube. They can be applied, at least in principle, to any simulation whose aim is to estimate a mathematical expectation. This covers a very wide range of applications.

In this paper, we review some of the key ideas of quasi-Monte Carlo methods from a broad perspective, with emphasis on some recent results. We visit lattice rules in different types of spaces and make the connections between these rules and digital nets, thus covering the two most widely used QMC methods.

REFERENCES

• 1: Bakhvalov, N. S. 1962. On the rate of convergence ofindeterministic integration processes within the functional classes Wp. Theory of Probability and its Applications 7:227.
• 2: Paul Bratley , Bennett L. Fox, ALGORITHM 659: implementing Sobol's quasirandom sequence generator, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.88-100, March 1988 [doi>10.1145/42288.214372]
• 3: Caflisch, R. E., W. Morokoff, and A. Owen. 1997. Valuation of mortgage-backed securities using Brownian bridges to reduce effective dimension. The Journal of Computational Finance 1 (1): 27--46.
• 4: Raymond Couture , Pierre L'ecuyer, Lattice computations for random numbers, Mathematics of Computation, v.69 n.230, p.757-765, April 2000 [doi>10.1090/S0025-5718-99-01112-6]
• 5: Cranley, R., and T. N. L. Patterson. 1976. Randomization of number theoretic methods for multiple integration. SIAM Journal on Numerical Analysis 13 (6): 904--914.
• 6: Faure, H. 1982. Discrépance des suites associées à un systéme de numération. Acta Arithmetica 61:337--351.
• 7: Fox, B. L. 1999. Strategies for quasi-Monte Carlo. Boston, MA: Kluwer Academic.
• 8: Heinrich, S., and E. Nowak. 2002. Optimal summation and integration by deterministic, randomized, and quantum algorithms. In Monte Carlo and Quasi-Monte Carlo Methods 2000, ed. K. -T. Fang, F. J. Hickernell, and H. Niederreiter, 50--62. Berlin: Springer-Verlag.
• 9: Hellekalek, P. 1998. On the assessment of random and quasi-random point sets. In Random and Quasi-Random Point Sets, ed. P. Hellekalek and G. Larcher, Volume 138 of Lecture Notes in Statistics, 49--108. New York: Springer.
• 10: Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Mathematics of Computation, v.67 n.221, p.299-322, Jan. 1998 [doi>10.1090/S0025-5718-98-00894-1]
• 11: Hickernell, F. J. 1998b. Lattice rules: How well do they measure up? In Random and Quasi-Random Point Sets, ed. P. Hellekalek and G. Larcher, Volume 138 of Lecture Notes in Statistics, 109--166. New York: Springer.
• 12: Fred J. Hickernell , Hee Sun Hong , Pierre LÉcuyer , Christiane Lemieux, Extensible Lattice Sequences for Quasi-Monte Carlo Quadrature, SIAM Journal on Scientific Computing, v.22 n.3, p.1117-1138, 2000 [doi>10.1137/S1064827599356638]
• 13: Hoeffding, W. 1948. A class of statistics with asymptotically normal distributions. Annals of Mathematical Statistics 19:293--325.
• 14: Stephen Joe , Ian H. Sloan, Imbedded lattice rules for multidimensional integration, SIAM Journal on Numerical Analysis, v.29 n.4, p.1119-1135, Aug. 1992 [doi>10.1137/0729068]
• 15: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 16: Korobov, N. M. 1959. The approximate computation of multiple integrals. Dokl. Akad. Nauk SSSR 124:1207--1210. in Russian.
• 17: L'Ecuyer, P. 2003. Polynomial lattice rules. In Monte Carlo and Quasi-Monte Carlo Methods 2002, ed. H. Niederreiter. Berlin: Springer-Verlag. to appear.
• 18: Pierre L'Ecuyer , Christiane Lemieux, Variance Reduction via Lattice Rules, Management Science, v.46 n.9, p.1214-1235, September 2000 [doi>10.1287/mnsc.46.9.1214.12231]
• 19: L'Ecuyer, P., and C. Lemieux. 2002. Recent advances in randomized quasi-Monte Carlo methods. In Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications, ed. M. Dror, P. L'Ecuyer, and F. Szidarovszki, 419--474. Boston: Kluwer Academic Publishers.
• 20: L'Ecuyer, P., and F. Panneton. 2002. Construction of equidistributed generators based on linear recurrences modulo 2. In Monte Carlo and Quasi-Monte Carlo Methods 2000, ed. K. -T. Fang, F. J. Hickernell, and H. Niederreiter, 318--330. Berlin: Springer-Verlag.
• 21: Christiane Lemieux , Pierre L'Ecuyer, On selection criteria for lattice rules and other quasi-Monte Carlo point sets, Mathematics and Computers in Simulation, v.55 n.1-3, p.139-148, Feb. 15, 2001 [doi>10.1016/S0378-4754(00)00254-8]
• 22: Christiane Lemieux , Pierre L'Ecuyer, Randomized Polynomial Lattice Rules for Multivariate Integration and Simulation, SIAM Journal on Scientific Computing, v.24 n.5, p.1768-1789, 2002 [doi>10.1137/S1064827501393782]
• 23: Liu, R., and A. B. Owen. 2003. Estimating mean dimensionality. manuscript.
• 24: William J. Morokoff, Generating Quasi-Random Paths for Stochastic Processes, SIAM Review, v.40 n.4, p.765-788, Dec. 1998 [doi>10.1137/S0036144597317959]
• 25: Niederreiter, H. 1987. Point sets and sequences with small discrepancy. Monatshefte fur Mathematik 104:273--337.
• 26: Niederreiter, H. 1988. Low-discrepancy and low-dispersion sequences. Journal of Number Theory 30:51--70.
• 27: Niederreiter, H. 1992a. Low-discrepancy point sets obtained by digital constructions over finite fields. Czechoslovak Math. Journal 42:143--166.
• 28: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 29: Niederreiter, H., and G. Pirsic. 2001. Duality for digital nets and its applications. Acta Arithmetica 97:173--182.
• 30: Niederreiter, H., and C. Xing. 1997. The algebraic-geometry approach to low-discrepancy sequences. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, ed. P. Hellekalek, G. Larcher, H. Niederreiter, and P. Zinterhof, Volume 127 of Lecture Notes in Statistics, 139--160. New York: Springer-Verlag.
• 31: 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, ed. H. Niederreiter and P. J. -S. Shiue, Number 106 in Lecture Notes in Statistics, 299--317. Springer-Verlag.
• 32: Owen, A. B. 1997. Scrambled net variance for integrals of smooth functions. Annals of Statistics 25 (4): 1541--1562.
• 33: Art B. Owen, Latin supercube sampling for very high-dimensional simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.71-102, Jan. 1998 [doi>10.1145/272991.273010]
• 34: Art B. Owen, Variance with alternative scramblings of digital nets, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.4, p.363-378, October 2003 [doi>10.1145/945511.945518]
• 35: Pirsic, G., and W. C. Schmid. 2001. Calculation of the quality parameter of digital nets and application to their construction. Journal of Complexity 17 (4): 827--839.
• 36: Sloan, I. H., and S. Joe. 1994. Lattice methods for multiple integration. Oxford: Clarendon Press.
• 37: Sobol', I. M. 1967. The distribution of points in a cube and the approximate evaluation of integrals. U.S.S.R. Comput. Math. and Math. Phys. 7:86--112.
• 38: Sobol', I. M., and Y. L. Levitan. 1976. The production of points uniformly distributed in a multidimensional. Technical Report Preprint 40, Institute of Applied Mathematics, USSR Academy of Sciences. In Russian.
• 39: Jerome Spanier , Earl H. Maize, Quasi-random methods for estimating integrals using relatively small samples, SIAM Review, v.36 n.1, p.18-44, March 1994 [doi>10.1137/1036002]
• 40: Tezuka, S. 1990, Jan., A new family of low-discrepancy point sets. Technical Report RT-0031, IBM Research, Tokyo Research Laboratory.
• 41: Tezuka, S. 1995. Uniform random numbers: Theory and practice. Norwell, Mass.: Kluwer Academic Publishers.
• 42: B. Tuffin, Variance reduction order using good lattice points in Monte Carlo methods, Computing, v.61 n.4, p.371-378, 1998 [doi>10.1007/BF02684386]