On the complexity of stochastic integration

G. W. Wasilkowski, H. Woźniakowski

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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 ε-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.

Original languageEnglish
Pages (from-to)685-698
Number of pages14
JournalMathematics of Computation
Issue number234
StatePublished - Apr 2001


  • Complexity
  • Ito integrals
  • Optimal algorithms
  • Stratonovich integrals

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'On the complexity of stochastic integration'. Together they form a unique fingerprint.

Cite this