A sequential particle algorithm that keeps the particle system alive

Dr Francoise LeGland (IRISA / INRIA Rennes)
joint with Nadia Oudjane (EDF RD Clamart + Université Paris XIII)

Abstract

The problem of approximating a nonlinear (unnormalized) Feynman-Kac flow is considered, in the special case where the selection functions are only nonnegative and can take the zero value. Several important practical situations are described where this case occurs:

  • simulation of rare events using multilevel splitting,
  • simulation of a random variable in the tail of a given probability distribution,
  • simulation of a Markov chain conditionned or constrained to visit given subspaces of the state space (this includes tracking a mobile in a constrained environment, or in the presence of obstacles),
  • nonlinear filtering with bounded observation noise,
  • robustification approach to nonlinear filtering, using truncation of the likelihood function,
  • approximation of general nonlinear filtering, where hidden state and observation are jointly simulated, and where the simulated observation is validated against the actual observation.

    If the selection functions are only nonnegative, it can happen with a standard particle algorithm that all the simulated particles receive a zero weight, with the effect that the particle system dies out. To guarantee that the particle system never dies, a sequential particle algorithm is introduced, which adapts the number of particles, and some limit theorems are proved, including a central limit theorem.

    While in standard nonsequential algorithms the computational effort is fixed but the performance is random, in the proposed sequential algorithm the performance is guaranteed at the expense of a random computational effort. The different results are illustrated in the simple case of binary selection functions.

    Back to Control Seminars Page