On tractability of path integration

Grzegorz W. Wasilkowski, Henryk Woźniakowski

Research output: Contribution to journalArticlepeer-review

39 Scopus citations


Many applications require approximate values of path integrals. A typical approach is to approximate the path integral by a high dimensional integral and apply a Monte Carlo (randomized) algorithm. However, Monte Carlo algorithm requires roughly ∈-2 integrand evaluations to provide an ∈ approximation. Moreover, the error bound of ∈ is guaranteed only in a stochastic sense. Do we really need to use randomized algorithms for path integrals? Perhaps, we can find a deterministic algorithm that is more effective even in the worst case setting. To answer this question, we study the worst case complexity of path integration, which, roughly speaking, is defined as the minimal number of the integrand evaluations needed to compute an approximation with error at most ∈. We consider path integration with respect to a Gaussian measure, and for various classes of integrands. Tractability of path integration means that the complexity depends polynomially on 1/∈. We show that for the class of r times Frechet differentiable integrands, tractability of path integration holds iff the covariance operator of the Gaussian measure has finite rank. Hence, if the Gaussian measure is supported on an infinite dimensional space then path integration is intractable. In this case, there exists no effective deterministic algorithm, and the use of randomized algorithms is justified. In fact, for this class of integrands, the classical Monte Carlo algorithm is (almost) optimal and the complexity in the randomized setting is proportional to ∈-2. On the other hand, for a particular class of entire integrands, the worst case complexity of path integration is at most of order ∈-p with p depending on the Gaussian measure. Hence, path integration is now tractable. Furthermore, for any Gaussian measure, the exponent p is less than or equal to 2. For the Wiener measure, p = 2/3. For this class, we provide effective deterministic algorithms which solve the path integration problem with (worst case) cost that is usually much less than the (randomized) cost of the classical Monte Carlo algorithm.

Original languageEnglish
Pages (from-to)2071-2088
Number of pages18
JournalJournal of Mathematical Physics
Issue number4
StatePublished - Apr 1996

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics


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

Cite this