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 Free Access

Abstract | References | Similar Articles | Additional Information

We study the complexity of approximating stochastic integrals with error for various classes of functions. For Ito integration, we show that the complexity is of order , 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.

**1.**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****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.**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****5.**D. Lee,*Approximation of linear operators on a Wiener space*, Rocky Mountain J. Math.**16**(1986), no. 4, 641–659. MR**871027**, 10.1216/RMJ-1986-16-4-641**6.**Bernt Øksendal,*Stochastic differential equations*, 3rd ed., Universitext, Springer-Verlag, Berlin, 1992. An introduction with applications. MR**1217084****7.**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****8.**G. W. Wasilkowski,*Information of varying cardinality*, J. Complexity**2**(1986), no. 3, 204–228. MR**922813**, 10.1016/0885-064X(86)90002-6**9.**G. W. Wasilkowski and H. Woźniakowski,*Mixed settings for linear problems*, J. Complexity**5**(1989), no. 4, 457–465. MR**1028907**, 10.1016/0885-064X(89)90020-4**10.**G. W. Wasilkowski and H. Wozniakowski, Weighted approximation over , to appear in J. Approx. Theory.

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

Email:
greg@cs.uky.edu

**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

Email:
henryk@cs.columbia.edu

DOI:
https://doi.org/10.1090/S0025-5718-00-01214-X

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