Browse Prior Art Database

Reverse-time Simulation of Rare Events

IP.com Disclosure Number: IPCOM000121261D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 3 page(s) / 100K

Publishing Venue

IBM

Related People

Heidelberger, P: AUTHOR [+2]

Abstract

Using simulation to accurately estimate the probability of rare events can be extremely time consuming. The general technique of importance sampling is typically applied to speed up rare event simulations by reducing the variance of simulation estimates (see, e.g., [1]). The theory of large deviations often provides a basis for selecting effective importance sampling distributions. A connection between large deviations and time reversal for certain rare events in Jackson Queueing networks is established in [2]. A more general result connecting time reversal and the occurrence of rare events is given in [3]. The above-mentioned references (and others) all suggest using particular importance sampling distributions for simulation of the forward time process to estimate the probability of rare events.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Reverse-time Simulation of Rare Events

      Using simulation to accurately estimate the probability
of rare events can be extremely time consuming. The general technique
of importance sampling is typically applied to speed up rare event
simulations by reducing the variance of simulation estimates (see,
e.g., [1]).  The theory of large deviations often provides a basis
for selecting effective importance sampling distributions.  A
connection between large deviations and time reversal for certain
rare events in Jackson Queueing networks is established in [2].  A
more general result connecting time reversal and the occurrence of
rare events is given in [3].   The above-mentioned references (and
others) all suggest using particular importance sampling
distributions for simulation of the forward time process to estimate
the probability of rare events.

      We describe an efficient technique that uses simulation of the
reverse time process, with no importance sampling, to estimate the
probability of certain rare events in Markov chains.

      To describe the method, we need some notation. Let {X(n),n / 0}
be a stationary positive recurrent, irreducible Markov chain with
transition matrix P = (P(ij)) and stationary distribution f = (f(i)).
For any set S, let t(S) = inf{n>0:X(n) e S}.  Let B be a set
such that f(B) is small. It is often of interest to estimate a =
P{t(B)<t(A) X(0) e A}.  For example, in a reliability model, if A =
{0} represents the all components operational state and B represents
the set of failure states, then a = P{t(0)<t(A) X(0) = 0} and
estimation of this quantity arises in estimating E(t(B) X(0) = 0)
which is the mean time to first failure.
      We define X(n) = X (-n) to be the reverse time process. If
{X(n} is stationary, then {X(n)} is a stationary Markov chain with
station                                                ary
distribution f and transition matrix P = (P(ij)) where P(ij)) =
f(j)P(ji)/f(i).  For any set S, let t(S) = inf{n>0:X(n) e S}.
Reverse Time Simulation

      The method is based on the identity (not derived here) where a
= P{t(A)<t(B) X(0) e B}.  Note that a is the probability that the
reverse time process hits the set A before returning to set B, given
that it starts in set B.

      To estimate a, M independent and identically distributed
samples are drawn where the n-th sample is described as follows:
1. Choose a starting point K(n) in set B.  The probabili...