Estimation of overflow probabilities for models with heavy tails and complex dependencies

Events such as loss packets in queueing systems and bankruptcy probabilities for insurance companies are rare but consequential. The likelihood of such events can often be linked to the maximum of a stochastic process. We refer to such quantities as overflow probabilities--due to their connection to queueing. Current Monte Carlo algorithms for efficient evaluation of overflow probabilities often assume features such as light tails or independence among increments. Our contribution lies in the design and the rigorous statistical analysis of estimators that are applicable to a class of problems with heavy-tailed features or arbitrary dependence structures. The first part of this dissertation deals with heavy tailed models that exhibit simple correlation. We construct a state-dependent importance sampling estimator for the tail distribution of heavy-tailed compound sums. This is the first provable strongly efficient estimator under basically minimal assumptions within a heavy-tailed environment. In the second part, we consider the evaluation of overflow probabilities of Markov random walks. We describe the elements behind the large deviations theory and efficient Monte Carlo estimators in this setting. These elements include the evaluation of certain eigenvalues and eigenfunctions of associated integral operators, which we obtain explicitly for a class of time series models. Finally, in third part of dissertation, we study discrete-time Gaussian processes with negative drift and arbitrary dependence structures. In great generality overflow probabilities to a level b for such processes converge to zero exponentially fast in b . Under mild assumptions on the marginal distributions of the process and no assumption on the correlation structure, we develop an importance sampling algorithm, called Target Bridge Sampler (TBS) that estimates the required overflow probability with polynomial complexity in b . This is the first provably efficient estimator for overflow probabilities of Gaussian processes that might exhibit long range dependence. TBS can also be used to generate exact samples for such processes given a large overflow.