Contents of this page:
Denis Miretskiy studied Applied Mathematics at Volgograd State University, Russia and received his Specialist degree in June 2004. Later that year he continued his study in Utrecht University, The Netherlands. He received his M.Sc. degree in Applied Mathematics in June 2005. Subsequently, he became a Ph.D. student at the Stochastic Operations Research group at the University of Twente, The Netherlands. In 2009, he finished his Ph.D. thesis on 'Queueing networks: rare events and fast simulations'
This monograph focuses on rare events. Even though they are extremely unlikely, they can still occur and then could have significant consequences.
We mainly consider rare events in queueing networks. More precisely, we are interested in the probability of collecting some large number of jobs in the downstream queue of a two-node tandem network. We consider the Jackson network case, as well as a generalization, the so-called slowdown network. In practice these models can be used to model overflows in telecommunication networks. We chose these networks as a first step in developing a methodology that can be extended to more general networks.
We investigate rare events from two different sides. On the one hand we are interested in the nature of the event, i.e., how the event builds up. At first we identify the structure of a specific path to overflow, which plays the role of our candidate for the most probable trajectory to overflow. We use some simple, but powerful large deviations based heuristics to this end. The shape of the trajectory crucially depends on both the starting state and the system parameters. We then provide a rigorous proof that this trajectory is indeed the most probable path to overflow. Thus our method combines simplicity (as it is easy to identify) and precision (as it is backed up by rigorous mathematical support).
On the other hand our ultimate goal is to design accurate and efficient techniques to estimate the probability of our interest; in particular we aim for techniques that are asymptotically efficient, which effectively means that the number of replications needed to obtain an estimator with predetermined relative error grows sub-exponentially when the probability of interest decays exponentially. We present several importance sampling schemes based on the large deviations results. We begin with naıve, state-independent algorithms and end up with a family of simple and efficient state-dependent schemes. We also develop a multilevel splitting scheme, which turns out to be efficient for a wider class of processes. Strengths and weaknesses of the importance sampling schemes and multilevel splitting schemes are also discussed in this work.
To download the thesis, which I finished in 2009, press: thesis.
NL 1001 GB Amsterdam