Latin supercube sampling for very high-dimensional simulations

ABSTRACT

This article introduces Latin supercube sampling (LSS) for very high-dimensional simulations such as arise in particle transport, finance, and queueing. LSS is developed as a combination of two widely used methods: Latin hypercube sampling (LHS) and quasi-Monte Carlo (QMC). In LSS, the input variables are grouped into subsets, and a lower-dimensional QMC method is used within each subset. The QMC points are presented in random order within subsets. QMC methods have been observed to lose effectiveness in high-dimensional problems. This article shows that LSS can extend the benefits of QMC to much higher dimensions, when one can make a good grouping of input variables. Some suggestions for grouping variables are given for the motivating examples. Even a poor grouping can still be expected to do as well as LHS. The article also extends LHS and LSS to infinite-dimensional problems. The paper includes a survey of QMC methods, randomized versions of them (RQMC), and previous methods for extending QMC to higher dimensions. Furthermore it shows that LSS applied with RQMC is more reliable than LSS with QMC.

REFERENCES

• 1: ACWORTH, P., BROADIE, M., AND GLASSERMAN, P. 1997. A comparison of some Monte Carlo techniques for option pricing. In Monte Carlo and Quasi-Monte Carlo Methods '96, H. Niederreiter, P. Hellekalek, G. Larcher, and P. Zinterhof, Eds., Springer-Verlag, New York (in press).
• 2: BOYLE, P., BROADIE, M., AND GLASSERMAN, P. 1996. Monte Carlo methods for security pricing. J. Econ. Dynamics Control (in press).
• 3: Paul Bratley , Bennett L. Fox , Harald Niederreiter, Implementation and tests of low-discrepancy sequences, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.2 n.3, p.195-213, July 1992 [doi>10.1145/146382.146385]
• 4: CAFLISCH, R. E., MOROKOFF, W., AND OWEN, A. B. 1997. Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension. Tech. Rep., Department of Mathematics, UCLA.
• 5: CRANLEY, R. AND PATTERSON, T. 1976. Randomization of number theoretic methods for multiple integration. SIAM J. Numer. Anal. 13, 904-914.
• 6: DAVIS, P. J. AND RABINOWITZ, P. 1984. Methods of Numerical Integration, (2nd ed.). Academic Press, San Diego.
• 7: DEVROYE, L. 1986. Non-Uniform Random Variate Generation. Springer-Verlag, New York.
• 8: EFRON, B. AND STEIN, C. 1981. The jackknife estimate of variance. Ann. Stat. 9, 586-596.
• 9: FANG, K.-T. AND WANG, Y. 1994. Number Theoretic Methods in Statistics. Chapman and Hall, London.
• 10: FAURE, H. 1982. Discr~pance de suites associ~es ~ un syst~me de numeration (en dimension s). Acta Arith. 41, 337-351.
• 11: Henri Faure, Multidimensional quasi-Monte-Carlo methods, Theoretical Computer Science, v.123 n.1, p.131-137, Jan. 17, 1994 [doi>10.1016/0304-3975(94)90073-6]
• 12: Fox, B. 1996. Generating Poisson processes by quasi-Monte Carlo. Tech. Rep., SIMOPT Consulting, 872 Timber Lane, Boulder, CO 80304.
• 13: GLYNN, P. 1995. Some new results on the initial transient problem. Tech. Rep., Stanford University, EESOR Department.
• 14: HABER, S. 1970. Numerical evaluation of multiple integrals. SIAM Rev. 12, 481-526.
• 15: Fred J. Hickernell, The mean square discrepancy of randomized nets, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.6 n.4, p.274-296, Oct. 1996 [doi>10.1145/240896.240909]
• 16: 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]
• 17: HUA, L. AND WANG, Y. 1981. Applications of Number Theory to Numerical Analysis. Springer-Verlag, Berlin.
• 18: S. Joe, Randomization of lattice rules for numerical multiple integration, Journal of Computational and Applied Mathematics, v.31 n.2, p.299-304, Aug. 1990 [doi>10.1016/0377-0427(90)90172-V]
• 19: Corwin Joy , Phelim P. Boyle , Ken Seng Tan, Quasi-Monte Carlo methods in numerical finance, Management Science, v.42 n.6, p.926-938, June 1996 [doi>10.1287/mnsc.42.6.926]
• 20: KAKUTANI, S. 1944. Two-dimensional Brownian motion harmonic functions. Proc. Imp. Acad. (Tokyo) 20, 706-714.
• 21: KELLER, A. 1995. A quasi-Monte Carlo algorithm for the global illumination problem in a radiosity setting. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, H. Niederreiter and P. J.-S. Shiue, Eds., Springer-Verlag, New York, 239-251.
• 22: KERSCH, A. AND MOROKOFF, W. 1995. Transport Simulation in Microelectronics. Birkh~iuser, Basel.
• 23: KOEHLER, J. AND OWEN, A. 1996. Computer experiments. In Handbook of Statistics, 13: Design and Analysis of Experiments, S. Ghosh and C. Rao, Eds., North-Holland, Amsterdam, 261-308.
• 24: McKAY, M. D., BECKMAN, R. J., AND CONOVER, W.J. 1979. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21, 2, 239-45.
• 25: William J. Morokoff , Russel E. Caflisch, A quasi-Monte Carlo approach to particle simulation of the heat equation, SIAM Journal on Numerical Analysis, v.30 n.6, p.1558-1573, Dec. 1993 [doi>10.1137/0730081]
• 26: William J. Morokoff , Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM Journal on Scientific Computing, v.15 n.6, p.1251-1279, Nov. 1994 [doi>10.1137/0915077]
• 27: William J. Morokoff , Russel E. Caflisch, Quasi-Monte Carlo integration, Journal of Computational Physics, v.122 n.2, p.218-230, Dec. 1995 [doi>10.1006/jcph.1995.1209]
• 28: NIEDERREITER, H. 1987. Point sets and sequences with small discrepancy. Monatshefte fur mathematik 104, 273-337.
• 29: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 30: NIEDERREITER, H. AND XING, C. 1996. Low-discrepancy sequences and global function fields with many rational places. Finite Fields Appl. 2, 241-273.
• 31: OKTEN, G. 1996. A probabilistic result on the discrepancy of a hybrid-Monte Carlo sequence and applications. Tech. Rep., Mathematics Department, Claremont Graduate School.
• 32: OWEN, A.B. 1992. Orthogonal arrays for computer experiments, integration and visualization. Stat. Sinica 2, 439-452.
• 33: OWEN, A.B. 1994. Lattice sampling revisited: Monte Carlo variance of means over randomized orthogonal arrays. Ann. Stat. 22, 930-945.
• 34: 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, H. Niederreiter and P. J.-S. Shiue, Eds., Springer-Verlag, New York, 299-317.
• 35: Art B. Owen, Monte Carlo Variance of Scrambled Net Quadrature, SIAM Journal on Numerical Analysis, v.34 n.5, p.1884-1910, Oct. 1997 [doi>10.1137/S0036142994277468]
• 36: OWEN, A.B. 1997b. Scrambled net variance for integrals of smooth functions. Ann. Stat. 25, 4, 1541-1562.
• 37: PASKOV, S. 1996. New methodologies for valuing derivatives. In Mathematics of Derivative Securities, S. Pliska and M. Dempster, Eds., Isaac Newton Institute, Cambridge University Press, New York.
• 38: PASKOV, S. AND TRAUB, J. 1995. Faster valuation of financial derivatives. J. Portfolio Manage., 113-120.
• 39: PATTERSON, H.D. 1954. The errors of lattice sampling. J.R.S.S.-B 16, 140-149.
• 40: SADIKU, M. N.O. 1992. Numerical Techniques in Electromagnetics. CRC Press, Boca Raton, FL.
• 41: P. K. Sarkar , M. A. Prasad, A comparative study of Pseudo and Quasi random sequences for the solution intergral equations, Journal of Computational Physics, v.68 n.1, p.66-88, January 2, 1987 [doi>10.1016/0021-9991(87)90045-3]
• 42: SEARLE, S. R., CASELLA, G., AND MCCULLOCH, C.E. 1992. Variance Components. John Wiley, New York.
• 43: SLOAN, I. H. AND JOE, S. 1994. Lattice Methods for Multiple Integration. Oxford Science Publications, Oxford.
• 44: SLOAN, I. H. AND WOZNIAKOWSKI, H. 1995. An intractability result for multiple integration. Tech. Rep., University of New South Wales, School of Mathematics.
• 45: SPANIER, J. 1995. Quasi-Monte Carlo methods for particle transport problems. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, H. Niederreiter and P. J.-S. Shiue Eds., Springer-Verlag, New York, 121-148.
• 46: Michael Stein, Large sample properties of simulations using latin hypercube sampling, Technometrics, v.29 n.2, p.143-151, May 1, 1987 [doi>10.2307/1269769]
• 47: TAKEMURA, A. 1983. Tensor analysis of ANOVA decomposition. J. Am. Stat. Assoc. 78, 894-900.
• 48: TEZUKA, S.1995. Uniform Random Numbers: Theory and Practice. Kluwer Academic, Boston.
• 49: TUFFIN, B. 1996. On the use of low discrepancy sequences in Monte Carlo methods. Tech. Rep. 1060, IRISA, Rennes, France.
• 50: VAN RENSBURG, E. g. g. AND TORRIE, G.M. 1993. Estimation of multidimensional integrals: Is Monte Carlo the best method? J. Phys. A: Math. Gen. 26, 943-953.
• 51: VEACH, E. AND GUIBAS, L. 1994. Bidirectional estimators for light transport. In Fifth Annual Eurographics Workshop on Rendering (Darmstadt, Germany, June 13-15), 147-162.
• 52: WAHBA, G. 1990. Spline Models for Observational Data. CBMS-NSF, SIAM, Philadelphia.
• 53: WASILKOWSKI, g. AND WOZNIAKOWSKI, a. 1996. The exponent of discrepancy is at most 1.4778 .... Tech. Rep., Columbia University, Department of Computer Science.
• 54: WILLIAMS, D. 1991. Probability with Martingales. Cambridge University Press, Cambridge.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Multidimensional (multiple) quadrature

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Error analysis
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Experimentation, Theory

Keywords:
(t, m, s)-nets, Latin hypercube, integration, lattice methodss, low discrepancy sequences, orthogonal array sampling, quasi-Monte Carlo