We present an algorithm for the efficient sampling of conditional paths of stochastic
differential equations (SDEs). While unconditional path sampling of SDEs is
straightforward, albeit expensive for high dimensional systems of SDEs, conditional
path sampling can be difficult even for low dimensional systems. This is because we
need to produce sample paths of the SDE that respect both the dynamics of the
SDE and the initial and endpoint conditions. The dynamics of a SDE are
governed by the deterministic term (drift) and the stochastic term (noise).
Instead of producing conditional paths directly from the original SDE, one can
consider a sequence of SDEs with modified drifts. The modified drifts should be
chosen so that it is easier to produce sample paths that satisfy the initial and
endpoint conditions. Also, the sequence of modified drifts should converge to the
drift of the original SDE. We construct a simple Markov chain Monte Carlo
algorithm that samples, in sequence, conditional paths from the modified
SDEs, by taking the last sampled path at each level of the sequence as an
initial condition for the sampling at the next level in the sequence. The
algorithm can be thought of as a stochastic analog of deterministic homotopy
methods for solving nonlinear algebraic equations or as a SDE generalization of
simulated annealing. The algorithm is particularly suited for filtering/smoothing
applications. We show how it can be used to improve the performance of particle
filters. Numerical results for filtering of a stochastic differential equation are
included.
