Large Deviations in Rare Events Simulation: Examples, Counterexamples and Alternatives
When simulating small probabilities, say of order 10−6 or less, by importance sampling, an established principle is to choose the importance sampling distribution as close to the conditional distribution given the rare event as possible. Implementing this
- PDF / 1,201,269 Bytes
- 9 Pages / 439.37 x 666.14 pts Page_size
- 112 Downloads / 208 Views
1
Introduction
The evalu ation of small prob abilities, of ord er from 10- 2 to 10- 10 , comes up in a numb er of applicat ion areas like insuran ce risk , telecommunications and reliability. The difficulty in evaluating th em by simul ation lies in controlling the relative err or. Formally, let A(x) be a family of event s indexed by a par amet er x and satisfying z(x) = lP(A(x)) -+ 0, x -+ 00 . A simulation est imat ion scheme is then a family of r.v.'s Z( x) which can be generated by simul ation and has lEZ( x) = z(x) (in practice , th e simulation of z(x) is performed by producing N i.i.d. replications of Z(x) , using the average as estimator of z(x ) and assessing the st atis tical err or by a confidence int erval based upon the empirical variance) . If we let u2( x) = Var(Z(x)) , the relative error is defined as u( x)j z(x) , and ideally, one looks for schemes having t he property th at this quantity remains bounded as x -+ 00 or at least grows slower than any negative power of z(x) (this property is referr ed to as logarithmic efficiency). This fails in parti cular for the crude Monte Carlo method, where Z( x) is the indi cator of A(x) and u 2 = z(x )(1 - z(x)) is of ord er z(x), impl ying th at N must be chosen very larg e as z(x) becomes small. The pro to type of an algorithm with bounded relative err or is the algorithm of Siegmund [15] for est imating th e probability z(x) th at a random walk with negative drift ever exceeds level x . If F is the incr ement distribution, the algorit hm uses importan ce sampling, where F is exponentially tilted with a certain par amet er familiar from work of Cram er and Feller . A similar simple example of exponential tilting is th e estimation of the probability K.‒T. Fang et al. (eds.)., Monte Carlo and Quasi-Monte Carlo Methods 2000 © Springer-Verlag Berlin Heidelberg 2002
2
that a sum of n i.i.d . terms is much bigger than its mean, where the choice of the tilting parameter is based upon the familiar saddlepoint argument . We survey these algorithms in Section 2. In more complex situations, it is usually not obvious how to choose the importance sampling distribution lP*. A general approach is based upon the observation that choosing lP* as lP x , the conditional lP-distribution given A(x), would lead to (j2=O. This choice is not practicable because the likelihood ratio involves z(x) which is unknown, but suggests to try to make lP* as close to lP x as possible. This necessitates a study of the asymptotic form of lP x , in particular of describing the most likely path leading to the rare event, and is often performed using large deviations techniques. Indeed this approach explains the particular form of the exponential tilting in the above two simple examples, as well as it applies to a number of other problems. Rather recent counterexamples indicate, however, that the idea of involving asymptotics of lP x has its limitations. For example, Glasserman & Kou [11] found an example in tandem queues (mathematically, a two-dimensional reflected random walk) where a path
Data Loading...
