Algorithm 823: Implementing scrambled digital sequences

ABSTRACT

Random scrambling of deterministic (t, m, s)-nets and (t, s)-sequences eliminates their inherent bias while retaining their low-discrepancy properties. This article describes an implementation of two types of random scrambling, one proposed by Owen and another proposed by Faure and Tezuka. The four different constructions of digital sequences implemented are those proposed by Sobol', Faure, Niederreiter, and Niederreiter and Xing. Because the random scrambling involves manipulating all digits of each point, the code must be written carefully to minimize the execution time. Computed root mean square discrepancies of the scrambled sequences are compared to known theoretical results. Furthermore, the performances of these sequences on various test problems are discussed.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 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: 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: Kaitai T. Fang , H. Niederreiter , F. J. Hickernell, Monte Carlo and Quasi-Monte Carlo Methods 2000, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 5: Faure, H. 1982. Discrépance de suites associées à un système de numération (en dimension s). Acta Arith. 41, 337--351.
• 6: Faure, H. and Tezuka, S. 2002. Another random scrambling of digital (t, s)-sequences. See Fang et al. {2002}, 242--256.
• 7: Fox, B. L. 1999. Strategies for Quasi-Monte Carlo. Kluwer Academic Publishers, Boston, MA.
• 8: Genz, A. 1982. A Lagrange extrpolation algorithm for sequences of approximations to multiple integrals. SIAM J. Sci. Stat. Comput. 3, 160--172.
• 9: Genz, A. 1992. Numerical computation of multivariate normal probabilities. J. Comput. Graph. Statist. 1, 141--150.
• 10: Genz, A. 1993. Comparison of methods for the computation of multivariate normal probabilities. Comput. Sci. and Statist. 25, 400--405.
• 11: Hellekalek, P. and Larcher, G., Eds. 1998. Random and Quasi-Random Point Sets. Lecture Notes in Statistics, vol. 138. Springer-Verlag, New York, NY.
• 12: 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]
• 13: 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 ]
• 14: Hickernell, F. J. 1999. Goodness-of-fit statistics, discrepancies and robust designs. Statist. Probab. Lett. 44, 73--78.
• 15: Hickernell, F. J. 2000. What affects the accuracy of quasi-Monte Carlo quadrature? See Niederreiter and Spanier {2000}, 16--55.
• 16: Hickernell, F. J. and Hong, H. S. 1997. Computing multivariate normal probabilities using rank-1 lattice sequences. In Proceedings of the Workshop on Scientific Computing, G. H. Golub, S. H. Lui, F. T. Luk, and R. J. Plemmons, Eds. Springer-Verlag, Singapore, Hong Kong, 209--215.
• 17: Fred J. Hickernell , Hee Sun Hong, The asymptotic efficiency of randomized nets for quadrature, Mathematics of Computation, v.68 n.226, p.767-791, April 1999 [doi>10.1090/S0025-5718-99-01019-4 ]
• 18: 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]
• 19: Fred J. Hickernell , Rong-Xian Yue, The Mean Square Discrepancy of Scrambled (t,s)-Sequences, SIAM Journal on Numerical Analysis, v.38 n.4, p.1089-1112, 2000 [doi>10.1137/S0036142999358019]
• 20: Bradley D. Keister, Multidimensional quadrature algorithms, Computers in Physics, v.10 n.2, p.119-122, March/April 1996 [doi>10.1063/1.168565 ]
• 21: Larcher, G. 1998a. Digital point sets: Analysis and applications. See Hellekalek and Larcher {1998}, 167--222.
• 22: Larcher, G. 1998b. On the distribution of digital sequences. In Monte Carlo and quasi-Monte Carlo methods 1996, H. Niederreiter, P. Hellekalek, G. Larcher, and P. Zinterhof, Eds. Lecture Notes in Statistics, vol. 127. Springer-Verlag, New York, NY, 109--123.
• 23: Jonathan Lichtner, Iterating an $\alpha$-ary Gray code, SIAM Journal on Discrete Mathematics, v.11 n.3, p.381-386, Aug. 1998 [doi>10.1137/S0895480196308736]
• 24: Jiří Matoušek, On the L2-discrepancy for anchored boxes, Journal of Complexity, v.14 n.4, p.527-556, Dec. 1998 [doi>10.1006/jcom.1998.0489 ]
• 25: Matoušek, J. 1999. Geometric Discrepancy: An Illustrated Guide. Number 18 in Algorithms and Combinatorics. Springer-Verlag, Berlin, Germany.
• 26: McNamee, J. and Stenger, F. 1967. Construction of fully symmetric numerical integration formulas. Numer. Math. 10, 327--344.
• 27: Niederreiter, H. 1988. low-discrepancy and low dispersion sequences. J. Numb. Theor. 30, 51--70.
• 28: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 29: Jerome Spanier , Harald Niederreiter, Monte Carlo and Quasi-Monte Carlo Methods, 1998: Proceedings of a Conference Held at the Claremont Graduate University, Claremont, California, USA, JU, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 30: Harald Niederreiter , Chaoping Xing, Quasirandom points and global function fields, Proceedings of the third international conference on Finite fields and applications, p.269-296, February 1996, Glasgow, Scotland, United Kingdom
• 31: Niederreiter, H. and Xing, C. 1998. Nets, (t, s)-sequences and algebraic geometry. See Hellekalek and Larcher {1998}, 267--302.
• 32: 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. Lecture Notes in Statistics, vol. 106. Springer-Verlag, New York, NY, 299--317.
• 33: 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]
• 34: Owen, A. B. 1997b. Scrambled net variance for integrals of smooth functions. Ann. Stat. 25, 1541--1562.
• 35: Art B. Owen, Scrambling sobol' and niederreiter-xing points, Journal of Complexity, v.14 n.4, p.466-489, Dec. 1998 [doi>10.1006/jcom.1998.0487 ]
• 36: Owen, A. B. 2000. Monte Carlo, quasi-Monte Carlo, and randomized quasi-Monte Carlo. See Niederreiter and Spanier {2000}, 86--97.
• 37: A. Papageorgiou , J. F. Traub, Faster evaluation of multidimensional integrals, Computers in Physics, v.11 n.6, p.574-578, Nov./Dec. 1997 [doi>10.1063/1.168616 ]
• 38: Patterson, T. N. L. 1968. The optimum addition of points to quadrature formulae. Math. Comp. 22, 847--856.
• 39: Pirsic, G. 2002. A software implementation of niederreiter-xing sequences. See Fang et al. {2002}, 434--445.
• 40: Schmid, W. C. 1999. The exact quality parameter of nets derived from Sobol' and Niederreiter sequences. In Recent Advances in Numerical Methods and Applications, O. P. Iliev et al., Eds. World Scientific, Sigapore, 287--295.
• 41: Sobol', I. M. 1967. The distribution of points in a cube and the approximate evaluation of integrals. U.S.S.R. Comput. Math. Math. Phys. 7, 86--112.
• 42: Tezuka, S. 1995. Uniform Random Numbers: Theory and Practice. Kluwer Academic Publishers, Boston, MA.
• 43: Yue, R. X. 1999. Variance of quadrature over scrambled unions of nets. Statist. Sinica 9, 451--473.
• 44: Rong-Xian Yue , Fred J. Hickernell, The discrepancy and gain coefficients of scrambled digital nets, Journal of Complexity, v.18 n.1, p.135-151, March 2002 [doi>10.1006/jcom.2001.0630]
• 45: Yue, R. X. and Mao, S. S. 1999. On the variance of quadrature over scrambled nets and sequences. Statist. Probab. Lett. 44, 267--280.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms

Keywords:
Scrambling, digital net