On the Particle Approximation of Lagged Feynman-Kac Formulae

In this paper we examine the numerical approximation of the limiting invariant measure associated with Feynman-Kac formulae. These are expressed in a discrete time formulation and are associated with a Markov chain and a potential function. The typical application considered here is the computation of eigenvalues associated with non-negative operators as found, for example, in physics or particle simulation of rare-events. We focus on a novel lagged approximation of this invariant measure, based upon the introduction of a ratio of time-averaged Feynman-Kac marginals associated with a positive operator iterated l times; a lagged Feynman-Kac formula. This estimator and its approximation using Diffusion Monte Carlo (DMC) have been extensively employed in the physics literature. In short, DMC is an iterative algorithm involving N particles or walkers simulated in parallel, that undergo sampling and resampling operations. In this work, it is shown that for the DMC approximation of the lagged Feynman-Kac formula, one has an almost sure characterization of the L₁-error as the time parameter (iteration) goes to infinity and this is at most of O(exp\-κ l\/N), for κ>0. In addition a non-asymptotic in time, and time uniform L₁-bound is proved which is O(l/√N). We also prove a novel central limit theorem to give a characterization of the exact asymptotic in time variance. This analysis demonstrates that the strategy used in physics, namely, to run DMC with N and l small and, for long time enough, is mathematically justified. Our results also suggest how one should choose N and l in practice. We emphasize that these results are not restricted to physical applications; they have broad relevance to the general problem of particle simulation of the Feynman-Kac formula.