×

Local antithetic sampling with scrambled nets. (English) Zbl 1157.65006

Many problems in science and engineering require multidimensional quadratures. The Monte Carlo integration can be improved by the use of variance reduction methods.
The author extends the classical variance reduction method of antithetic sampling and combine it with randomized quasi-Monte Carlo methods. Several ways of combining and randomized digital nets are considered. The main result is that for any \(\epsilon > 0\) such method reduces the rate of the root mean square error (RMSE) of the integration of smooth integrands to \({\mathcal O}\left( n^{-{3 \over 2} - {1 \over d} + \epsilon}\right),\) where \(d\) is the dimension.
In section 2 the information on scrambled nets is reminded. The concepts of \((q,m,d)\)-nets, \((\lambda,q,m,d)\)-nets and \((q,d)\)-sequences in base \(b \geq 2\) are discussed. Techniques of random scrambles as a random linear scrambling, an affine matrix scramble with a different structure of the matrices are presented. The ANOVA decomposition of functions is reminded.
In Section 3 \(d\)-dimensional folding operations are used to introduce local antithetic properties into digital nets. Three specific methods – reflection nets, box folded nets and monomial nets – are introduced for inducing local antithetic properties in some \((q,m,2)\)-nets.
In Section 4 these three methods are illustrated to concrete two-dimensional integrand.
In Section 5 the variance for scrambled digital nets quadrature of smooth functions is considered. Theorem 2 shows some upper bounds of the gain coefficients for a \((0,m,d)\)-net, a \((\lambda,0,m,d)\)-net and a \((\lambda,q,m,d)\)-net in base \(b.\) Theorem 3 gives an order \({\mathcal O}\left( n^{-{3 \over 2}} (\log n)^{d-1 \over 2}\right)\) of the RMSE of the integration of smooth functions using a randomized relaxed \((\lambda,q,m,d)\)-net in base \(b.\)
In Section 6 the effect of the reflection scheme on a scrambled net is investigated. The concept of the box fold scheme is introduced. Theorem 4 states that for doubly smooth functions under the box folding on a randomized relaxed \((\lambda,0,m,d)\)-net in base \(b\) the RMSE of the integration has an order \({\mathcal O}\left( n^{-{3 \over 2} - {1 \over d}} (\log n)^{d-1 \over 2}\right).\)
In Section 7 the box folding scheme is presented as a hybrid of a monomial cubature rule with scrambled net sampling.

MSC:

65C05 Monte Carlo methods
11K45 Pseudo-random numbers; Monte Carlo methods
41A55 Approximate quadratures
41A63 Multidimensional problems

Software:

MinT
PDFBibTeX XMLCite
Full Text: DOI arXiv

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.) 1-18. Springer, Berlin. · Zbl 0888.90010
[2] Caflisch, R., Morokoff, E. W. and Owen, A. B. (1997). Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension. J. Computational Finance 1 27-46.
[3] Chelson, P. (1976). Quasi-random techniques for Monte Carlo methods. Ph.D. thesis, The Claremont Graduate School.
[4] Cools, R. (1999). Monomial cubature rules since Stroud: A compilation-part 2. J. Comput. Appl. Math. 112 21-27. · Zbl 0954.65021
[5] Cools, R. and Rabinowitz, P. (1993). Monomial cubature rules since Stroud: A compilation. J. Comput. Appl. Math. 48 309-326. · Zbl 0799.65027
[6] Efron, B. and Stein, C. (1981). The jackknife estimate of variance. Ann. Statist. 9 586-596. · Zbl 0481.62035
[7] Faure, H. (1982). Discrépance de suites associées à un système de numération (en dimension s ). Acta Arith. 41 337-351. · Zbl 0442.10035
[8] Fishman, G. S. (2006). A First Course in Monte Carlo . Duxbury, Belmont, CA.
[9] Fox, B. L. (1999). Strategies for Quasi-Monte Carlo . Kluwer Academic, Boston.
[10] Glasserman, P. (2004). Monte Carlo Methods in Financial Engineering . Springer, New York. · Zbl 1038.91045
[11] Haber, S. (1970). Numerical evaluation of multiple integrals. SIAM Rev. 12 481-526. JSTOR: · Zbl 0206.46905
[12] Hickernell, F. J., Lemieux, C. and Owen, A. B. (2005). Control variates for quasi-Monte Carlo (with discussion). Statist. Sci. 20 1-31. · Zbl 1100.65006
[13] Hlawka, E. (1961). Funktionen von beschränkter Variation in der Theorie der Gleichverteilung. Ann. Mat. Pura Appl. 54 325-333. · Zbl 0103.27604
[14] Hoeffding, W. (1948). A class of statistics with asymptotically normal distribution. Ann. Math. Statist. 19 293-325. · Zbl 0032.04101
[15] L’Ecuyer, P. and Lemieux, C. (2002). A survey of randomized quasi-Monte Carlo methods. In Modeling Uncertainty : An Examination of Stochastic Theory , Methods , and Applications (M. Dror, P. L’Ecuyer and F. Szidarovszki, eds.) 419-474. Kluwer Academic, New York.
[16] Matoušek, J. (1998). Geometric Discrepancy : An Illustrated Guide . Springer, Heidelberg. · Zbl 1197.11092
[17] Niederreiter, H. (1992). Random Number Generation and Quasi-Monte Carlo Methods . SIAM, Philadelphia. · Zbl 0761.65002
[18] Niederreiter, H. and Pirsic, G. (2001). The microstructure of ( t , m , s )-nets. J. Complexity 17 683-696. · Zbl 0997.11059
[19] 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.) 299-317. Springer, New York. · Zbl 0831.65024
[20] Owen, A. B. (1997). Monte Carlo variance of scrambled equidistribution quadrature. SIAM J. Numer. Anal. 34 1884-1910. JSTOR: · Zbl 0890.65023
[21] Owen, A. B. (1997). Scrambled net variance for integrals of smooth functions. Ann. Statist. 25 1541-1562. · Zbl 0886.65018
[22] Owen, A. B. (1998). Scrambling Sobol’ and Niederreiter-Xing points. J. Complexity 14 466-489. · Zbl 0916.65017
[23] Owen, A. B. (2003). Variance with alternative scramblings of digital nets. ACM Trans. Modeling and Computer Simulation 13 363-378. · Zbl 1390.65037
[24] Schürer, R. and Schmid, W. C. (2006). MinT: A database for optimal net parameters. In Monte Carlo and Quasi-Monte Carlo Methods 2004 (H. Niederreiter and D. Talay, eds.) 457-469. Springer, Berlin. · Zbl 1130.65302
[25] Sloan, I. H. and Joe, S. (1994). Lattice Methods for Multiple Integration . Oxford Science Publications. · Zbl 0855.65013
[26] Sobol’, I. M. (1967). The use of Haar series in estimating the error in the computation of infinite-dimensional integrals. Dokl. Akad. Nauk SSSR 8 810-813. · Zbl 0189.49402
[27] Spanier, J. and Maize, E. H. (1994). Quasi-random methods for estimating integrals using relatively small samples. SIAM Rev. 36 18-44. JSTOR: · Zbl 0824.65009
[28] Stroud, A. H. (1971). Approximate Calculation of Multiple Integrals . Prentice-Hall, Englewood Cliffs, NJ. · Zbl 0379.65013
[29] Takemura, A. (1983). Tensor analysis of ANOVA decomposition. J. Amer. Statist. Assoc. 78 894-900. JSTOR: · Zbl 0535.62061
[30] Tezuka, S. and Faure, H. (2003). I-binomial scrambling of digital nets and sequences. J. Complexity 19 744-757. · Zbl 1073.68033
[31] Yue, R. X. and Hickernell, F. J. (2002). The discrepancy and gain coefficients of scrambled digital nets. J. Complexity 18 135-151. · Zbl 1114.11306
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.