Rare events in Heavy-tailed Stochastic Systems: Algorithms and Analysis

Events that occur with low probability are called rare events. In the design of probabilistic models, it is important to ensure that certain undesirable events, for example, bankruptcy of financial institutions (or) data loss in communication networks, do not happen (or) if at all they happen, they happen with low probability. Conventional theory of large deviations, which is usually used to explain the behaviour of such rare events, is inapplicable when the random variables involved are heavy-tailed. We call a random variable to be heavy-tailed if its tail probabilities decay slowly at some polynomial rate. Simulation of rare events, in particular, has been traditionally considered difficult when heavy-tailed random variables are involved. In this work, we analyse asymptotic behaviour of certain rare events involving heavy-tailed random variables and develop simulation algorithms that are provably efficient. To be specific, we discuss the following contributions in the talk:
 
1) Based on the "big jump principle", we develop an entirely new methodology for the estimation of various large deviations and level crossing probabilities that arise in the context of heavy-tailed sums. Our key contribution has been to question the prevailing view that one needs to resort to state-dependent methods when a large number of heavy-tailed random variables are involved. The algorithms we develop are provably efficient, follow a general template, and are easy to generalize, as we shall see, to settings more general than sums of independent random variables. In addition to simulation involving finite sums, we tackle the problem of estimating tail probabilities of sums of infinite sums, where bias is generally a problem. Apart from eliminating bias, our algorithm computes tail probabilities with uniformly bounded computational effort.
 
2) Building up on the theory of rare events in heavy-tailed sums, we attempt to explain how large delays in service happen in multi-server queues when incoming jobs are heavy-tailed (in size) and traffic intensity is an integer. In the current literature, characterizations of steady-state delay exist only when the traffic intensity is not an integer. There are qualitative reasons, as we shall see, that makes the integer case more delicate to analyse. Our main contribution is that we develop the first known tail asymptotic for steady-state delay in multi-server queues when the traffic intensity is an integer. Specifically, we consider a two-server queue and identify interesting transitions in the tail behaviour of steady-state delay via a careful analysis that is not typical in the analysis of queuing systems.