 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
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
 |
2
|
|
| |
3
|
|
| |
4
|
|
| |
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
|
|
| |
13
|
|
| |
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
|
|
| |
18
|
|
| |
19
|
|
| |
20
|
|
| |
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
|
|
| |
24
|
|
| |
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
|
|
| |
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
|
|
| |
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
|
|
| |
34
|
Owen, A. B. 1997b. Scrambled net variance for integrals of smooth functions. Ann. Stat. 25, 1541--1562.
|
| |
35
|
|
| |
36
|
Owen, A. B. 2000. Monte Carlo, quasi-Monte Carlo, and randomized quasi-Monte Carlo. See Niederreiter and Spanier {2000}, 86--97.
|
| |
37
|
|
| |
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
|
|
| |
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.
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
823.gz
F.2