Efficient importance sampling for Monte Carlo evaluation of exceedance probabilities (Q2455052): Difference between revisions

The importance sampling is a powerful technique to compute the probabilities of rare events by Monte Carlo simulation. In the introduction of the paper some important notions of the theory of large deviations as a rare functions, exceedance probabilities, a consistence with large deviations, an asymptotically optimal choice and others are reminded. In section 2 asymptotically optimal importance sampling measures for the Monte Carlo evaluation of the boundary crossing probability \(Q_{c}\) and the tail probability \(Q_{n}\) are derived. A more precise definition of the asymptotic optimality of the choices of the importance sampling measures is given. A much more general way for constructing the asymptotically efficient importance sampling distribution is presented. Theorems 1 and 2, respectively, give the form of the asymptotically importance sampling measure \(Q_{c}\) and the asymptotically optimal importance sampling measure \(Q_{n}\) for evaluating the tail probability. Section 3 generalizes the methods and results of section 2 to the case of a Markov random walk. Section 3.1 is a modification of the usual likelihood ratio martingale to circumvent difficulties with an analysis of eigenfunctions for likelihood ratios. In section 3.2 a new renewal-theoretic approach to an extension of \textit{D. Siegmund}'s result [Ann. Stat. 4, 673--684 (1976; Zbl 0353.62044)] on exponential tilting to the Markov random walks is developed. In section 3.3 an extension of Theorem 1 to Markov setting is given. In section 3.4 an extension of Theorem 2 to Markov additive processes is proposed. A comparison with the dynamic importance sampling method is given. In section 4 numerical methods to address certain implementation issues are described. Numerical examples are provided to illustrate the effectiveness of the considered methods. Results obtained by applying the direct Monte Carlo method and the importance sampling are compared.