×

zbMATH — the first resource for mathematics

Control variates for quasi-Monte Carlo (with comments and rejoinder). (English) Zbl 1100.65006
Summary: Quasi-Monte Carlo (QMC) methods have begun to displace ordinary Monte Carlo (MC) methods in many practical problems. It is natural and obvious to combine QMC methods with traditional variance reduction techniques used in MC sampling, such as control variates. There can, however, be some surprises. The optimal control variate coefficient for QMC methods is not in general the same as for MC. Using the MC formula for the control variate coefficient can worsen the performance of QMC methods. A good control variate in QMC is not necessarily one that correlates with the target integrand. Instead, certain high frequency parts or derivatives of the control variate should correlate with the corresponding quantities of the target. We present strategies for applying control variate coefficients with QMC and illustrate the method on a 16-dimensional integral from computational finance. We also include a survey of QMC aimed at a statistical readership.

MSC:
65C05 Monte Carlo methods
62J10 Analysis of variance and covariance (ANOVA)
Software:
Algorithm 823; SDaA
PDF BibTeX Cite
Full Text: DOI
References:
[1] Avramidis, A. and Wilson, J. R. (1993). A splitting scheme for control variates. Oper. Res. Lett. 14 187–198. · Zbl 0811.62027
[2] Beck, J. and Chen, W. W. L. (1987). Irregularities of Distribution . Cambridge Univ. Press. · Zbl 0631.10034
[3] Ben Ameur, H., L’Ecuyer, P. and Lemieux, C. (1999). Variance reduction of Monte Carlo and randomized quasi-Monte Carlo estimators for stochastic volatility models in finance. In Proc. 1999 Winter Simulation Conference 1 336–343. IEEE Press, New York.
[4] Bratley, P., Fox, B. L. and Schrage, L. E. (1987). A Guide to Simulation , 2nd ed. Springer, New York. · Zbl 0515.68070
[5] Caflisch, R. E., Morokoff, W. and Owen, A. B. (1997). Valuation of mortgage-backed securities using Brownian bridges to reduce effective dimension. J. Comput. Finance 1 27–46.
[6] Chelson, P. (1976). Quasi-random techniques for Monte Carlo methods. Ph.D. dissertation, Claremont Graduate School.
[7] Cochran, W. G. (1977). Sampling Techniques , 3rd ed. Wiley, New York. · Zbl 0353.62011
[8] Cranley, R. and Patterson, T. (1976). Randomization of number theoretic methods for multiple integration. SIAM J. Numer. Anal. 13 904–914. JSTOR: · Zbl 0354.65016
[9] Efron, B. and Stein, C. (1981). The jackknife estimate of variance. Ann. Statist. 9 586–596. JSTOR: · Zbl 0481.62035
[10] Fang, K.-T. and Wang, Y. (1994). Number-Theoretic Methods in Statistics . Chapman and Hall, London. · Zbl 0925.65263
[11] 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
[12] Fishman, G. (1996). Monte Carlo: Concepts, Algorithms, and Applications . Springer, New York. · Zbl 0859.65001
[13] Heinrich, S., Hickernell, F. J. and Yue, R.-X. (2004). Optimal quadrature for Haar wavelet spaces. Math. Comp. 73 259–277. · Zbl 1035.65004
[14] Hickernell, F. J. (1996). Quadrature error bounds with applications to lattice rules. SIAM J. Numer. Anal. 33 1995–2016; corrected printing of Sections 3–6 (1997) 34 853–866. JSTOR: · Zbl 0855.41024
[15] Hickernell, F. J., Hong, H. S., L’Ecuyer, P. and Lemieux, C. (2000). Extensible lattice sequences for quasi-Monte Carlo quadrature. SIAM J. Sci. Comput. 22 1117–1138. · Zbl 0974.65004
[16] Hickernell, F. J. and Niederreiter, H. (2003). The existence of good extensible rank-1 lattices. J. Complexity 19 286–300. · Zbl 1029.65004
[17] Hickernell, F. J. and Yue, R.-X. (2000). The mean square discrepancy of scrambled \((t,s)\)-sequences. SIAM J. Numer. Anal. 38 1089–1112. · Zbl 1049.65005
[18] Hoeffding, W. (1948). A class of statistics with asymptotically normal distribution. Ann. Math. Statist. 19 293–325. · Zbl 0032.04101
[19] Hong, H. S. and Hickernell, F. J. (2003). Algorithm 823: Implementing scrambled digital sequences. AMS Trans. Math. Software 29 95–109. · Zbl 1068.11049
[20] Hua, L. and Wang, Y. (1981). Applications of Number Theory to Numerical Analysis . Springer, Berlin. · Zbl 0465.10045
[21] Korobov, N. M. (1959). The approximate computation of multiple integrals. Dokl. Akad. Nauk SSSR 124 1207–1210. · Zbl 0089.04201
[22] Kuipers, L. and Niederreiter, H. (1974). Uniform Distribution of Sequences . Wiley, New York. · Zbl 0281.10001
[23] L’Ecuyer, P. and Lemieux, C. (2002). Recent advances in 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, Dordrecht.
[24] Liao, J. G. (1998). Variance reduction in Gibbs sampler using quasi random numbers. J. Comput. Graph. Statist. 7 253–266.
[25] Loh, W.-L. (2003). On the asymptotic distribution of scrambled net quadrature. Ann. Statist. 31 1282–1324. · Zbl 1105.62304
[26] Lohr, S. (1999). Sampling: Design and Analysis . Brooks/Cole, Pacific Grove, CA. · Zbl 0967.62005
[27] Matoušek, J. (1998). On the \(L_2\)-discrepancy for anchored boxes. J. Complexity 14 527–556. · Zbl 0942.65021
[28] Matoušek, J. (1999). Geometric Discrepancy: An Illustrated Guide . Springer, Heidelberg. · Zbl 0930.11060
[29] Morokoff, W. and Caflisch, R. E. (1995). Quasi-Monte Carlo integration. J. Comput. Phys. 122 218–230. · Zbl 0863.65005
[30] Niederreiter, H. (1987). Point sets and sequences with small discrepancy. Monatsh. Math. 104 273–337. · Zbl 0626.10045
[31] Niederreiter, H. (1992). Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia. · Zbl 0761.65002
[32] Niederreiter, H. and Pirsic, G. (2001). The microstructure of (\(t,m,s\))-nets. J. Complexity 17 683–696. · Zbl 0997.11059
[33] Niederreiter, H. and Xing, C. (2001). Rational Points on Curves over Finite Fields: Theory and Applications. London Math. Soc. Lecture Note Ser. 285 . Cambridge Univ. Press. · Zbl 0971.11033
[34] Ostland, M. and Yu, B. (1997). Exploring quasi Monte Carlo for marginal density approximation. Statist. Comput. 7 217–228.
[35] Owen, A. B. (1992). A central limit theorem for Latin hypercube sampling. J. Roy. Statist. Soc. Ser. B 54 541–551. JSTOR: · Zbl 0776.62041
[36] Owen, A. B. (1995). Randomly permuted \((t,m,s)\)-nets and \((t,s)\)-sequences. Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing. Lecture Notes in Statist. 106 299–317. Springer, New York. · Zbl 0831.65024
[37] Owen, A. B. (1997a). Monte Carlo variance of scrambled net quadrature. SIAM J. Numer. Anal. 34 1884–1910. JSTOR: · Zbl 0890.65023
[38] Owen, A. B. (1997b). Scrambled net variance for integrals of smooth functions. Ann. Statist. 25 1541–1562. · Zbl 0886.65018
[39] Owen, A. B. (1998a). Latin supercube sampling for very high dimensional simulations. ACM Transactions on Modeling and Computer Simulation 8 71–102. · Zbl 0917.65022
[40] Owen, A. B. (1998b). Scrambling Sobol’ and Niederreiter–Xing points. J. Complexity 14 466–489. · Zbl 0916.65017
[41] Owen, A. B. (2002). Scrambled net variance with alternative scramblings. Technical report, Dept. Statistics, Stanford Univ.
[42] Paskov, S. (1993). Average case complexity of multivariate integration for smooth functions. J. Complexity 9 291–312. · Zbl 0781.65017
[43] Ripley, B. D. (1987). Stochastic Simulation . Wiley, New York. · Zbl 0613.65006
[44] Ritchken, P., Sankarasubramanian, L. and Vijh, A. M. (1993). The valuation of path dependent contracts on the average. Management Sci. 39 1202–1213. · Zbl 0798.90025
[45] Sarkar, P. K. and Prasad, M. A. (1987). A comparative study of pseudo- and quasirandom sequences for the solution of integral equations. J. Comput. Phys. 68 66–88. · Zbl 0605.65100
[46] Schlier, C. (2002). A practitioner’s view on QMC integration. Technical report, Fakultät für Physik, Univ. Freiburg.
[47] Sloan, I. H. and Joe, S. (1994). Lattice Methods for Multiple Integration . Oxford Univ. Press, New York. · Zbl 0855.65013
[48] Sloan, I. H., Kuo, F. Y. and Joe, S. (2002a). Constructing randomly shifted lattice rules in weighted Sobolev spaces. SIAM J. Numer. Anal. 40 1650–1665. · Zbl 1037.65005
[49] Sloan, I. H., Kuo, F. Y. and Joe, S. (2002b). On the step-by-step construction of quasi-Monte Carlo integation rules that achieve strong tractability error bounds in weighted Sobolev spaces. Math. Comp. 71 1609–1640. JSTOR: · Zbl 1011.65001
[50] Sloan, I. H. and Reztsov, A. V. (2002). Component-by-component construction of good lattice rules. Math. Comp. 71 263–273. JSTOR: · Zbl 0985.65018
[51] Sobol’, I. M. (1967). The distribution of points in a cube and the accurate evaluation of integrals. Zh. Vychisl. Mat. i Mat. Fiz. 7 784–802. (In Russian.) · Zbl 0185.41103
[52] Sobol’, I. M. (1969). Multidimensional Quadrature Formulas and Haar Functions . Nauka, Moscow. (In Russian.) · Zbl 0195.16903
[53] 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
[54] Tezuka, S. (1995). Uniform Random Numbers: Theory and Practice . Kluwer, Boston. · Zbl 0841.65004
[55] van der Corput, J. G. (1935a). Verteilungsfunktionen I. Nederlandse Akademie van Wetenschappen Proceedings 38 813–821. · Zbl 0012.34705
[56] van der Corput, J. G. (1935b). Verteilungsfunktionen II. Nederlandse Akademie van Wetenschappen Proceedings 38 1058–1066. · Zbl 0013.05703
[57] Weyl, H. (1914). Über ein Problem aus dem Gebeite der diophantischen Approximationen. Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. II 234–244. · JFM 45.0325.01
[58] Weyl, H. (1916). Über die Gleichverteilung von Zahlen mod. eins. Math. Ann. 77 313–352. · JFM 46.0278.06
[59] Yue, R.-X. (1999). Variance of quadrature over scrambled unions of nets. Statist. Sinica 9 451–473. · Zbl 0952.65001
[60] 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
[61] Zaremba, S. K. (1968). Some applications of multidimensional integration by parts. Ann. Polon. Math. 21 85–96. · Zbl 0174.08402
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.