Multilevel Approximations of Markovian Jump Processes with Applications in Communication Networks

  • Pedro Vilanova

Student thesis: Doctoral Thesis

Abstract

This thesis focuses on the development and analysis of efficient simulation and inference techniques for Markovian pure jump processes with a view towards applications in dense communication networks. These techniques are especially relevant for modeling networks of smart devices —tiny, abundant microprocessors with integrated sensors and wireless communication abilities— that form highly complex and diverse communication networks. During 2010, the number of devices connected to the Internet exceeded the number of people on Earth: over 12.5 billion devices. By 2015, Cisco’s Internet Business Solutions Group predicts that this number will exceed 25 billion. The first part of this work proposes novel numerical methods to estimate, in an efficient and accurate way, observables from realizations of Markovian jump processes. In particular, hybrid Monte Carlo type methods are developed that combine the exact and approximate simulation algorithms to exploit their respective advantages. These methods are tailored to keep a global computational error below a prescribed global error tolerance and within a given statistical confidence level. Indeed, the computational work of these methods is similar to the one of an exact method, but with a smaller constant. Finally, the methods are extended to systems with a disparity of time scales. The second part develops novel inference methods to estimate the parameters of Markovian pure jump process. First, an indirect inference approach is presented, which is based on upscaled representations and does not require sampling. This method is simpler than dealing directly with the likelihood of the process, which, in general, cannot be expressed in closed form and whose maximization requires computationally intensive sampling techniques. Second, a forward-reverse Monte Carlo Expectation-Maximization algorithm is provided to approximate a local maximum or saddle point of the likelihood function of the parameters given a set of observations. The third part is devoted to applications in communication networks where also mean field or fluid approximations techniques, to substantially reduce the computational work of simulating large communication networks are explored. These methods aim to capture the global behaviour of systems with large state spaces by using an aggregate approximation, which is often described by means of a non-linear dynamical system.
Date of AwardMay 4 2015
Original languageEnglish
Awarding Institution
  • Computer, Electrical and Mathematical Science and Engineering
SupervisorRaul Tempone (Supervisor)

Keywords

  • inference for continuous-time
  • Markov Chains
  • error control
  • weak approximation
  • multilevel monte carlo
  • chernoff tau-leap

Cite this

'