Fast convergence of quasi-Monte Carlo for a class of isotropic integrals

Papageorgiou, A.

doi:10.1090/S0025-5718-00-01231-X

Fast convergence of quasi-Monte Carlo for a class of isotropic integrals
HTML articles powered by AMS MathViewer

by A. Papageorgiou PDF

Math. Comp. 70 (2001), 297-306 Request permission

Abstract:

We consider the approximation of $d$-dimensional weighted integrals of certain isotropic functions. We are mainly interested in cases where $d$ is large. We show that the convergence rate of quasi-Monte Carlo for the approximation of these integrals is $O(\sqrt {\log n}/n)$. Since this is a worst case result, compared to the expected convergence rate $O(n^{-1/2})$ of Monte Carlo, it shows the superiority of quasi-Monte Carlo for this type of integral. This is much faster than the worst case convergence, $O(\log ^d n/n)$, of quasi-Monte Carlo.

References

Bratley, P., Fox, B.L., and Niederreiter, H. (1992), Implementation and Tests of Low-Discrepancy Sequences, ACM Trans. on Modeling and Computer Simulation, 2:3, 195–213.
Capstick, S., and Keister, B.D. (1996), Multidimensional quadrature algorithms at higher degree and/or dimension, Journal of Computational Physics, 123, 267–273.
Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456, DOI 10.1007/BFb0093404
Joy, C., Boyle, P.P., and Tan, K.S. (1996), Quasi-Monte Carlo Methods in Numerical Finance, Management Science, 42, No. 6, 926–938.
Keister, B.D. (1996), Multidimensional Quadrature Algorithms, Computers in Physics, 10:20, 119–122.
Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
Ninomiya, S., and Tezuka, S. (1996), Toward real-time pricing of complex financial derivatives, Applied Mathematical Finance, 3, 1–20.
Erich Novak and Klaus Ritter, High-dimensional integration of smooth functions over cubes, Numer. Math. 75 (1996), no. 1, 79–97. MR 1417864, DOI 10.1007/s002110050231
Novak, E., Ritter, K., Schmitt, R., Steinbauer, A. (1997), On a recent interpolatory method for high dimensional integration, Preprint University of Erlangen.
Papageorgiou, A., and Traub, J.F. (1996), Beating Monte Carlo, Risk, 9:6, 63–65.
Papageorgiou, A., and Traub, J.F. (1997), Faster evaluation of multi-dimensional integrals, Computers in Physics, Nov./Dec., 574–578.
Paskov, S.H. and Traub, J.F., Faster Valuation of Financial Derivatives, Journal of Portfolio Management, Fall, 1995, 113–120.
Paskov, S.H. (1997), New Methodologies for Valuing Derivatives, in “Mathematics of Derivative Securities,” S. Pliska and M. Dempster eds., Isaac Newton Institute, Cambridge University Press, Cambridge, UK, 545–582.
Sloan, I.H., and Woźniakowski, H. (1998), When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?, J. Complexity, 14(1), 1–33.
Tezuka, S. (1995), “Uniform Random Numbers: Theory and Practice,” Kluwer Academic Publishers, Boston.
Y. L. Tong, The multivariate normal distribution, Springer Series in Statistics, Springer-Verlag, New York, 1990. MR 1029032, DOI 10.1007/978-1-4613-9655-0
Traub, J.F. and Werschulz, A.G. (1998), “Complexity and Information,” Cambridge University Press, Cambridge, UK.
H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), no. 1, 185–194. MR 1072015, DOI 10.1090/S0273-0979-1991-15985-9