On asymptotically efficient simulation of large deviation probabilities.

ABSTRACT: Consider a family of probabilities for which the decay is governed by a large deviation principle. To find an estimate for a fixed member of this family, one is often forced to use simulation techniques. Direct Monte Carlo simulation, however, is often impractical, particularly if the probability that should be estimated is extremely small. Importance sampling is a technique in which samples are drawn from an alternative distribution, and an unbiased estimate is found after a likelihood ratio correction. Specific exponentially twisted distributions were shown to be good sampling distributions under fairly general circumstances. In this paper, we present necessary and sufficient conditions for asymptotic efficiency of a single exponentially twisted distribution, sharpening previously established conditions. Using the insights that these conditions provide, we construct an example for which we explicitly compute the 'best' change of measure. However, simulation using the new measure faces exactly the same difficulties as direct Monte Carlo simulation. We discuss the relation between this example and other counterexamples in the literature. We also apply the conditions to find necessary and sufficient conditions for asymptotic efficiency of the exponential twist in a Mogul'skii sample-path problem. An important special case of this problem is the probability of ruin within finite time. 2000 Mathematics Subject Classification: Primary 65C05; secondary 60F10, 60K10. Keywords and Phrases: Rare event simulation, asymptotic efficiency, importance sampling, Monte Carlo methods, exponential twisting, large deviations, hitting probabilities. Note: The research of A. B. Dieker was supported by the Netherlands Organization for Scientific Research