Splitting for Rare Event Simulation: A Large Deviations Approach to Design and Analysis

Abstract

Particle splitting methods are considered for the estimation of rare events. The probability of interest is that a Markov process first enters a set B before another set A, and it is assumed that this probability satisfies a large deviation scaling. A notion of subsolution is defined for the related calculus of variations problem, and two main results are proved under mild conditions. The first is that the number of particles generated by the algorithm grows subexponentially if and only if a certain scalar multiple of the importance function is a subsolution. The second is that, under the same condition, the variance of the algorithm is characterized "asymptotically" in terms of the subsolution. The design of asymptotically optimal schemes is discussed, and numerical examples are presented.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2007
Accession Number
ADA476248

Entities

People

  • Aul Dupuis
  • Thomas Dean

Organizations

  • Brown University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Calculus
  • Calculus Of Variations
  • Differential Equations
  • Equations
  • Estimators
  • Markov Processes
  • Mathematics
  • Operations Research
  • Particles
  • Probability
  • Queueing Theory
  • Random Variables
  • Simulations
  • Splitting
  • Stochastic Processes

Fields of Study

  • Mathematics

Readers

  • Approximation Theory.
  • Mathematical Modeling and Probability Theory.
  • Parasitology and Pharmacology of Malaria.