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. Woźniakowski
Journal: Math. Comp. 70 (2001), 685-698
MSC (2000): Primary 60H05; Secondary 60H10
Published electronically: March 2, 2000
MathSciNet review: 1697653
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

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
MR Author ID: 189251
ORCID: 0000-0003-4727-7368

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

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