Perfect simulation for the Feynman-Kac law on the path space

Christophe Andrieu, Nicolás Chopin, Randal Douc, Sylvain RubenthalerarXiv 2012 · DOI · arXiv

Abstract

This paper introduces an algorithm for the perfect simulation of Feynman-Kac laws on path spaces. By integrating branching particle systems with a "Coupling From The Past" (CFTP) framework, the method allows for exact sampling from complex path distributions, bypassing the convergence and approximation issues typical of standard Monte Carlo approaches. This preliminary work establishes the algorithm's structure and demonstrates its efficacy on discrete and continuous models.

Introduction

Feynman-Kac models are a cornerstone of modern statistics and physics, used to describe systems where a Markov process is weighted by a series of potentials. These models are ubiquitous in fields ranging from protein folding to financial modeling. Traditionally, sampling from these models relies on Sequential Monte Carlo (SMC) or Markov Chain Monte Carlo (MCMC). However, SMC can suffer from path degeneracy as path length increases, and MCMC requires a burn-in period with no definitive way to verify convergence to the target distribution.

The authors address these challenges by proposing a method for perfect simulation: generating samples guaranteed to be distributed exactly according to the target law, eliminating approximation errors and convergence uncertainty.

Methodology

The proposed approach combines two sophisticated probabilistic frameworks: branching particle systems and backward coupling.

Branching Systems as Proposals

Instead of tracking a single trajectory, the algorithm simulates a "forest" of branching particles. At each time step, particles die or multiply based on the model's potentials. This branching system serves as a proposal for a Metropolis-Hastings step.

Metropolis-Hastings on Forests

The authors define a target distribution on the space of these branching systems (forests) that contains a trajectory from the desired Feynman-Kac law. A key finding is that the ratio of the target density to the proposal density simplifies to a ratio of population sizes, making the acceptance probability computationally tractable.

Backward Coupling (CFTP)

To achieve perfect simulation, the algorithm employs the Propp-Wilson "Coupling From The Past" framework. By looking backwards in time and using a fixed sequence of random seeds, the algorithm identifies a point where the simulation's state becomes independent of its starting value.

The Perfect Simulation Algorithm uses backward coupling to ensure the final output is drawn exactly from the target distribution.

Experimental Evaluation

The algorithm was evaluated on two mathematical benchmarks:

  1. Random Directed Polymers: A discrete model where paths move on a lattice through a random environment of potentials.
  2. Continuous State Space (Gaussian): A model where the underlying process is a linear Gaussian Markov chain, testing the algorithm's performance with continuous variables.

Key Results and Insights

The algorithm successfully generates exact trajectories for the random directed polymer model, capturing the "weak disorder" behavior predicted by theory, where the maximum displacement of trajectories scales with $n^\zeta$ (where $\zeta = 1/2$).

A visualization of 100 trajectories of a random directed polymer, showing how the paths cluster and branch.

Computational Efficiency

For the polymer model, the computational cost scales as $O(P^2)$, where $P$ is the path length. This quadratic scaling suggests the method is practical for relatively long paths, a significant improvement over naive exact sampling methods.

Stability and Tuning

A critical requirement for the algorithm is the stability of the branching process. The authors suggest using a preliminary SMC run to tune branching parameters, ensuring the population neither explodes nor vanishes prematurely.

Limitations and Future Work

As a preliminary version, several areas remain for further development:

  • Complexity Bounds: Rigorous mathematical bounds on complexity across diverse potential types are still being established.
  • Population Bounding: The algorithm requires a known upper bound on population size, which can be difficult to determine for complex continuous state spaces.
  • Scalability: While $O(P^2)$ is efficient for the tested models, high-dimensional spaces or high-variance potentials may still challenge the stability of the branching process.

Summary updated

Abstract

This paper describes an algorithm of interest. This is a preliminary version and we intend on writing a better descripition of it and getting bounds for its complexity.
BibTeX
@misc{andrieu2012perfect,
  author = {Christophe Andrieu and Nicolás Chopin and Randal Douc and Sylvain Rubenthaler},
  title = {{Perfect simulation for the Feynman-Kac law on the path space}},
  year = {2012},
  eprint = {1210.0376},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1210.0376},
}
Figure