Skip to main content
SpringerLink
Log in

Quasi-Monte Carlo — Discrepancy between Theory and Practice

  • Conference paper
Monte Carlo and Quasi-Monte Carlo Methods 2000

Abstract

In this paper, we survey the current status of theory and practice of quasi-Monte Carlo methods. First, we discuss one of the most important research directions for accelerating Monte Carlo simulations. It is described as MC → QMC → RQMC → Derandomized RQMC, where RQMC means randomized QMC. We give some interesting open questions concerning the gap between theory and practice of derandomized RQMC. Secondly, we overview the dramatic success of quasi-Monte Carlo methods for very high dimensional numerical integration problems in finance. In the last five years, the question of how to explain this success has been extensively investigated, and two classes of problems have been identified for which QMC (or RQMC) is much more efficient than MC. One is a class of problems with small “effective” dimensions; the other is a class of isotropic problems. Some interesting results and issues on these problems are discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Atanassov, E. I. (March 2000) On the Discrepancy of the Halton Sequences. manuscript

    Google Scholar 

  2. Braaten, E., Weiler, G. (1979) An Improved Low Discrepancy Sequence for Multidimensional Quasi-Monte Carlo Integration. J. Comput. Phys., 3.3, 249–258

    Article  Google Scholar 

  3. Caflisch, R. E., Morokoff, W., Owen, A. (1997) Valuation of Mortgage Backed Securities using Brownian Bridges to Reduce Effective Dimension. Journal of Computational Finance, 1, 27–46

    Google Scholar 

  4. Case, J. (December 1995) Wall Street's Dalliance with Number Theory. SIAM News, 28, 10, 8–9

    Google Scholar 

  5. Chen, W. W. L., Skriganov, M. M. (2000) Explicit Constructions in the Classical Mean Squares Problem in Irregularities of Point Distribution, manuscript

    Google Scholar 

  6. Cranley, R., Patterson, T. (1976) Randomization of Number Theoretic Methods for Multiple Integration. SIAM Journal of Numerical Analysis, 13, 904–914

    Article  MathSciNet  MATH  Google Scholar 

  7. Curbera, F. (2001) Algorithms and Complexity for Gaussian Integration and Applications to Financial Problems, PhD Thesis, Columbia University, New York

    Google Scholar 

  8. Faure, H. (1982) Discrepances de suites associées a un système de numeration en dimension s. Acta Arith., XLI, 337–351

    MathSciNet  Google Scholar 

  9. Faure, H. (1992) Good Permutation for Extreme Discrepancy. J. Number Theory, 41, 47–56

    Article  MathSciNet  Google Scholar 

  10. Faure, H., Tezuka, S. (2001) A New Generation of Digital (0, 5)-Sequences. Research Report RT0412, IBM Tokyo Research Laboratory

    Google Scholar 

  11. Fox, B. L. (1999) Strategies for Quasi-Monte Carlo, Kluwer Academic Publishers, Boston

    Book  Google Scholar 

  12. Hickernell F. J. (2000) What Affects the Accuracy of Quasi-Monte Carlo Quadrature? in Monte Carlo and Quasi-Monte Carlo Methods 1998, edited by H. Niederreit er and J. Spanier, Springer, Berlin, 16–55

    Google Scholar 

  13. Matousek, J. (1999) Geometric Discrepancy: An Illustrated Guide, Springer, Berlin

    Book  MATH  Google Scholar 

  14. Matousek, J. (1998) On the L 2-Discrepancy for Anchored Boxes. Journal of Complexity, 14, 527–556

    Article  MathSciNet  MATH  Google Scholar 

  15. Niederreiter, H. (1978) Quasi-Monte Carlo Methods and Pseudorandom Numbers. Bull. Amer. Math. Soc, 84, 957–1041

    Article  MathSciNet  MATH  Google Scholar 

  16. Niederreiter, H. (1987) Point Sets and Sequences with Small Discrepancy. Monatsh. Math., 104, 273–337

    Article  MathSciNet  MATH  Google Scholar 

  17. Niederreiter, H. (1992) Random Number Generation and Quasi-Monte Carlo Methods, CBMS-NSF Regional Conference Series in Applied Mathematics, No.63, SIAM

    Google Scholar 

  18. Niederreiter, H., Xing, C. (1998) Nets, (t,s)-sequences, and Algebraic Geometry, in Random and Quasi-Random Point Sets, edited by P. Hellekalek and G. Larcher, Lecture Notes in Statistics, 138, Springer, New York, 267–302

    Google Scholar 

  19. Novak, E., Ritter, K. (1996) High Dimensional Integration of Smooth Functions over Cubes. Numer. Math., 75, 79–97

    MathSciNet  MATH  Google Scholar 

  20. Novak, E., Woźniakowski, H. (2001) When are Integration and Discrepancy Tractable? in Foundations of Computational Mathematics, edited by R.A. DeVore et al., London Mathematical Society Lecture Note Series 284, Cambridge Univ. Press, 211–266

    Google Scholar 

  21. Owen, A. (1997a) Scrambled Net Variance for Integrals of Smooth Functions. The Annals of Statistics, 25(4), 1541–1562

    Article  MathSciNet  MATH  Google Scholar 

  22. Owen, A. (1997b) How Nearly Linear is a Function? Technical Report, Statistics Dept., Stanford University

    Google Scholar 

  23. Owen, A. (2000) Monte Carlo, Quasi-Monte Carlo, and Randomized Quasi-Monte Carlo. in Monte Carlo and Quasi-Monte Carlo Methods 1998, edited by H. Niederreiter and J. Spanier, Springer, Berlin, 86–97

    Google Scholar 

  24. Papageorgiou, A. (2001) Fast Convergence of Quasi-Monte Carlo for a Class of Isotropic Integrals. Math. Comp., 70, 233, 297–306

    Article  MathSciNet  MATH  Google Scholar 

  25. Papageorgiou, A., Traub, J. F. (June 1996) Beating Monte Carlo. RISK, 9, 63–65

    Google Scholar 

  26. Papageorgiou, A., Traub, J. F. (Nov/Dec 1997) Faster Evaluation of Multidimensional Integrals. Computers in Physics, 11, 574–578

    Article  Google Scholar 

  27. Paskov, S. H. (1997) New Methodologies for Valuing Derivatives. in Mathematics of Derivative Securities, edited by M. A. H. Dempster and S. Pliska, Isaac Newton Institute, Cambridge University Press, Cambridge UK, 545–582

    Google Scholar 

  28. Paskov, S. H., Traub, J. F. (Fall 1995) Faster Valuation of Financial Derivatives, Journal of Portfolio Management, 22(1), 113–120

    Article  Google Scholar 

  29. Sloan, I. H. (2001) QMC Integration — Beating Intractability by Weighting the Coordinate Directions, in this volume

    Google Scholar 

  30. Sloan, I. H., Kuo, F. Y., Joe, S. (October 2000) On the Step-by-Step Construction of Quasi-Monte Carlo Integration Rules That Achieve Strong Tractability Error Bounds in Weighted Sobolev Spaces. Applied Math. Report AMR00/24, University of New South Wales

    Google Scholar 

  31. Sloan, I. H., Woźniakowski, H. (1998) When are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals. Journal of Complexity, 14, 1–33

    Article  MathSciNet  MATH  Google Scholar 

  32. Tezuka, S. (1995) Uniform Random Numbers: Theory and Practice, Kluwer Academic Publishers, Boston

    Book  MATH  Google Scholar 

  33. Tezuka, S. (1998) Financial Applications of Monte Carlo and Quasi-Monte Carlo Methods, in Random and Quasi-Random Point Sets, edited by P. Hellekalek and G. Larcher, Lecture Notes in Statistics, 138, Springer, New York, 303–332

    Google Scholar 

  34. Tezuka, S. (2000) Quasi-Monte Carlo Methods for Financial Applications, in ICIAM99, edited by J. M. Ball and J. C. R. Hunt, Oxford Univ. Press, New York, 234–245

    Google Scholar 

  35. Tezuka, S. (2000) Discrepancy Theory and Its Application to Finance, in IFIP TCS2000, edited by J. van Leeuwen et al., Lecture Notes in Computer Science, 1872, Springer, New York, 243–256

    Google Scholar 

  36. Traub, J. F., Werschulz, A. G. (1998) Complexity and Information, Cambridge Univ. Press

    Google Scholar 

  37. Warnock, T. (1972) Computational Investigation of Low-Discrepancy Point Sets. in Applications of Number Theory to Numerical Analysis, edited by S. K. Zaremba, Academic Press, New York, 319–343

    Google Scholar 

  38. Woźniakowski, H. (1991) Average Case Complexity of Multivariate Integration. Bull. Amer. Math. Soc., 24, 185–194

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM Tokyo Research Laboratory, 1623-14, Shimotsuruma, Yamato, Kanagawa, Japan, 242-8502

    Shu Tezuka

Authors
  1. Shu Tezuka
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong SAR, China

    Kai-Tai Fang  & Fred J. Hickernell  & 

  2. Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore, 117543, Republic of Singapore

    Harald Niederreiter

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Tezuka, S. (2002). Quasi-Monte Carlo — Discrepancy between Theory and Practice. In: Fang, KT., Niederreiter, H., Hickernell, F.J. (eds) Monte Carlo and Quasi-Monte Carlo Methods 2000. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-56046-0_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-56046-0_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42718-6

  • Online ISBN: 978-3-642-56046-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation