Large Deviations Theory: Basic Principles and Applications to Communication Networks

The theory of large deviations refers to a collection of techniques for estimating properties of rare events such as their frequency and most likely manner of occurrence. Loosely speaking, LDT can be seen as a refinement of the classical limit theorems of probability theory and it is useful when simulation or numerical techniques become increasingly difficult as a parameter of interest tends to its limit. The first part of this tutorial deals with the behaviour of the empirical mean of IID RVs, the most natural framework to introduce the basic concepts and theorems of LDT and to highlight their heuristic interpretation. Then, the large deviation principle for the single server queue is presented and its implications on network dimensioning are discussed. Finally, the tutorial overviews the application of LDT to rare event simulation, for the choice of the optimal change of measure in Importance Sampling