A new algorithm and worst case complexity for Feynman-Kac path integration

We study algorithms for approximation of Feynman-Kac path integrals in the worst case setting. The algorithms use a finite number of samples of the in itial condition and potential functions. We present a new algorithm and an explicit bound on its cost to compute an E-approximation to the Feynman-Kac path integral. We also establish bounds on the worst case complexity of Fe ynman-Kac path integration. The upper bound is equal to the cost of the new algorithm and is given in terms of the complexity of a certain function ap proximation problem. The lower bound is given in terms of the complexity of a certain weighted integration problem. For some classes of functions, the se two bounds coincide module a multiplicative factor. In this case, the ne w algorithm is almost optimal. The new algorithm requires precomputation of some real coefficients that are combinations of multivariate integrals wit h special weights. This precomputation is difficult and limits the applicat ion of the new algorithm. We report the results of the precomputation For s pecific cases. (C) 2000 Academic Press.