On the complexity of stochastic integration

Wasilkowski, G.; Woźniakowski, H.

doi:10.1090/S0025-5718-00-01214-X

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.