Importance Sampling for rare event probability estimation

Importance sampling is a Monte Carlo method that allows to compute some properties of a particular distribution given some samples generated from a different distribution (called biased distribution) rather than from the distribution of interest. This method can be employed to reduce significantly the number of samples needed by a Monte Carlo simulation. In particular the estimation of rare event probabilities is a remarkably inefficient problem for direct Monte Carlo method. Rare event probability estimation can be useful because, even if these events are rare, they can have large impact on the studied situation, influencing heavily the mean value. Importance sampling can give a significant improvement on simulation performance. The strategy is to find an efficient distribution biased toward the rare event to generate more relevant samples for the studied system. To be efficient a biased distribution should make the number of samples as low as possible. From the number of samples estimation can be found, using large deviation theory, an efficient biased distribution. The theory of large deviations aims to find the asymptotic behaviour of remote tails of sequences of probability distributions. The thesis provides an introduction to rare events simulation using importance sampling. It also contains an introduction to large deviation theory and how is it liked to importance sampling biased distribution. At the end all the strategies explained are employed to estimate rare event probability in hidden Markov models.