Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

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


Author: A. Papageorgiou
Journal: Math. Comp. 70 (2001), 297-306
MSC (2000): Primary 65D30, 65D32
Published electronically: February 23, 2000
MathSciNet review: 1709157
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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.
  • 2. Capstick, S., and Keister, B.D. (1996), Multidimensional quadrature algorithms at higher degree and/or dimension, Journal of Computational Physics, 123, 267-273. CMP 96:07
  • 3. Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456 (98j:11057)
  • 4. Joy, C., Boyle, P.P., and Tan, K.S. (1996), Quasi-Monte Carlo Methods in Numerical Finance, Management Science, 42, No. 6, 926-938.
  • 5. Keister, B.D. (1996), Multidimensional Quadrature Algorithms, Computers in Physics, 10:20, 119-122.
  • 6. 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 (93h:65008)
  • 7. Ninomiya, S., and Tezuka, S. (1996), Toward real-time pricing of complex financial derivatives, Applied Mathematical Finance, 3, 1-20.
  • 8. Erich Novak and Klaus Ritter, High-dimensional integration of smooth functions over cubes, Numer. Math. 75 (1996), no. 1, 79–97. MR 1417864 (97k:65057), http://dx.doi.org/10.1007/s002110050231
  • 9. Novak, E., Ritter, K., Schmitt, R., Steinbauer, A. (1997), On a recent interpolatory method for high dimensional integration, Preprint University of Erlangen.
  • 10. Papageorgiou, A., and Traub, J.F. (1996), Beating Monte Carlo, Risk, 9:6, 63-65.
  • 11. Papageorgiou, A., and Traub, J.F. (1997), Faster evaluation of multi-dimensional integrals, Computers in Physics, Nov./Dec., 574-578.
  • 12. Paskov, S.H. and Traub, J.F., Faster Valuation of Financial Derivatives, Journal of Portfolio Management, Fall, 1995, 113-120.
  • 13. 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. CMP 98:06
  • 14. Sloan, I.H., and Wozniakowski, H. (1998), When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?, J. Complexity, 14(1), 1-33.
  • 15. Tezuka, S. (1995), Uniform Random Numbers: Theory and Practice,Kluwer Academic Publishers, Boston.
  • 16. Y. L. Tong, The multivariate normal distribution, Springer Series in Statistics, Springer-Verlag, New York, 1990. MR 1029032 (91g:60021)
  • 17. Traub, J.F. and Werschulz, A.G. (1998), Complexity and Information,Cambridge University Press, Cambridge, UK. CMP 99:13
  • 18. H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), no. 1, 185–194. MR 1072015 (91i:65224), http://dx.doi.org/10.1090/S0273-0979-1991-15985-9

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65D30, 65D32

Retrieve articles in all journals with MSC (2000): 65D30, 65D32


Additional Information

A. Papageorgiou
Affiliation: Department of Computer Science, Columbia University, New York, NY 10027
Email: ap@cs.columbia.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-00-01231-X
PII: S 0025-5718(00)01231-X
Keywords: Multidimensional integration, quadrature, Monte Carlo methods, low discrepancy sequences, quasi-Monte Carlo methods
Received by editor(s): March 2, 1999
Published electronically: February 23, 2000
Additional Notes: This research has been supported in part by the NSF
Article copyright: © Copyright 2000 American Mathematical Society