Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On the complexity of stochastic integration

Authors: G. W. Wasilkowski and H. Wozniakowski
Journal: Math. Comp. 70 (2001), 685-698
MSC (2000): Primary 60H05; Secondary 60H10
Published electronically: March 2, 2000
MathSciNet review: 1697653
Full-text PDF

Abstract | References | Similar Articles | Additional Information


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

  • 1. K. L. Chung and R. J. Williams, Introduction to Stochastic Integration, (2nd ed.), Birkhäuser, Boston, 1990. MR 92d:60057
  • 2. O. Faure, Simulation du mouvement brownien et des diffusions, These ENPC, Paris, 1992.
  • 3. 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).
  • 4. P. E. Kloeden and E. Platen, Numerical Solutions of Stochastic Differential Equations, Springer-Verlag, Berlin, 1992. MR 94b:60069
  • 5. D. Lee, Approximation of linear operators on a Wiener space, Rocky Mount. J. Math. 16 (1986), 641-659. MR 88f:41053
  • 6. B. Øksendal, Stochastic Differential Equations, (3rd ed.), Springer-Verlag, New York, 1992. MR 94g:60112
  • 7. J. F. Traub, G. W. Wasilkowski, and H. Wozniakowski, Information-Based Complexity, Academic Press, New York, 1988. MR 90f:68085
  • 8. G. W. Wasilkowski, Information of varying cardinality, J. Complexity, 2 (1986), 204-228. MR 88m:65099
  • 9. G. W. Wasilkowski and H. Wozniakowski, Mixed settings for linear problems, J.of Complexity, 5 (1989), 457-465. MR 91b:65065
  • 10. G. W. Wasilkowski and H. Wozniakowski, Weighted approximation over $\mathbb{R}$, to appear in J. Approx. Theory.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 60H05, 60H10

Retrieve articles in all journals with MSC (2000): 60H05, 60H10

Additional Information

G. W. Wasilkowski
Affiliation: Department of Computer Science, University of Kentucky, Lexington, KY 40506, USA

H. Wozniakowski
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

Keywords: Ito integrals, Stratonovich integrals, optimal algorithms, complexity
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.
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society