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.