On the complexity of stochastic integration
HTML articles powered by AMS MathViewer
- by G. W. Wasilkowski and H. Woźniakowski PDF
- Math. Comp. 70 (2001), 685-698 Request permission
Abstract:
We study the complexity of approximating stochastic integrals with error $\varepsilon$ for various classes of functions. For Ito integration, we show that the complexity is of order $\varepsilon ^{-1}$, even for classes of very smooth functions. The lower bound is obtained by showing that Ito integration is not easier than Lebesgue integration in the average case setting with the Wiener measure. The upper bound is obtained by the Milstein algorithm, which is almost optimal in the considered classes of functions. The Milstein algorithm uses the values of the Brownian motion and the integrand. It is bilinear in these values and is very easy to implement. For Stratonovich integration, we show that the complexity depends on the smoothness of the integrand and may be much smaller than the complexity of Ito integration.References
- K. L. Chung and R. J. Williams, Introduction to stochastic integration, 2nd ed., Probability and its Applications, Birkhäuser Boston, Inc., Boston, MA, 1990. MR 1102676, DOI 10.1007/978-1-4612-4480-6
- O. Faure, Simulation du mouvement brownien et des diffusions, These ENPC, Paris, 1992.
- N. Hofmann, T. Müller-Gronbach, and K. Ritter, Optimal approximation of stochastic differential equations by adaptive step-size control, Math. Comp., Posted on May 20, 1999, PII S 0025-5718(99)01177-1 (to appear in print).
- Peter E. Kloeden and Eckhard Platen, Numerical solution of stochastic differential equations, Applications of Mathematics (New York), vol. 23, Springer-Verlag, Berlin, 1992. MR 1214374, DOI 10.1007/978-3-662-12616-5
- D. Lee, Approximation of linear operators on a Wiener space, Rocky Mountain J. Math. 16 (1986), no. 4, 641–659. MR 871027, DOI 10.1216/RMJ-1986-16-4-641
- Bernt Øksendal, Stochastic differential equations, 3rd ed., Universitext, Springer-Verlag, Berlin, 1992. An introduction with applications. MR 1217084, DOI 10.1007/978-3-662-02847-6
- J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691
- G. W. Wasilkowski, Information of varying cardinality, J. Complexity 2 (1986), no. 3, 204–228. MR 922813, DOI 10.1016/0885-064X(86)90002-6
- G. W. Wasilkowski and H. Woźniakowski, Mixed settings for linear problems, J. Complexity 5 (1989), no. 4, 457–465. MR 1028907, DOI 10.1016/0885-064X(89)90020-4
- G. W. Wasilkowski and H. Woźniakowski, Weighted approximation over $\mathbb {R}$, to appear in J. Approx. Theory.
Additional Information
- G. W. Wasilkowski
- Affiliation: Department of Computer Science, University of Kentucky, Lexington, KY 40506, USA
- MR Author ID: 189251
- ORCID: 0000-0003-4727-7368
- Email: greg@cs.uky.edu
- H. Woźniakowski
- Affiliation: Department of Computer Science, Columbia University, New York, NY 10027, USA, and Institute of Applied Mathematics and Mechanics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland
- Email: henryk@cs.columbia.edu
- Received by editor(s): October 19, 1998
- Received by editor(s) in revised form: April 6, 1999
- Published electronically: March 2, 2000
- Additional Notes: The authors were partially supported by the National Science Foundation under Grants CCR-9729971 and CCR-9731858, respectively. This work was completed while the second author was a member of the Mathematical Sciences Research Institute at Berkeley in Fall 1998.
- © Copyright 2000 American Mathematical Society
- Journal: Math. Comp. 70 (2001), 685-698
- MSC (2000): Primary 60H05; Secondary 60H10
- DOI: https://doi.org/10.1090/S0025-5718-00-01214-X
- MathSciNet review: 1697653