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

HTML articles powered by AMS MathViewer

- by A. Papageorgiou;
- Math. Comp.
**70**(2001), 297-306 - DOI: https://doi.org/10.1090/S0025-5718-00-01231-X
- Published electronically: February 23, 2000
- PDF | 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

## Bibliographic Information

**A. Papageorgiou**- Affiliation: Department of Computer Science, Columbia University, New York, NY 10027
- Email: ap@cs.columbia.edu
- Received by editor(s): March 2, 1999
- Published electronically: February 23, 2000
- Additional Notes: This research has been supported in part by the NSF
- © Copyright 2000 American Mathematical Society
- Journal: Math. Comp.
**70**(2001), 297-306 - MSC (2000): Primary 65D30, 65D32
- DOI: https://doi.org/10.1090/S0025-5718-00-01231-X
- MathSciNet review: 1709157