Collaborative Research: Perfect Simulation of Stochastic Networks

点击翻译按钮获取中文摘要

Stochastic networks are a general class of time-varying probabilistic models where there is competition for limited resources. They are used in a wide range of engineering applications such as communication networks, call centers, and manufacturing systems. Operators of these types of systems are often interested in achieving a high level of performance over the long run, i.e., in steady state. Thus, it is important to devise efficient computational methods for steady-state analysis of stochastic networks. Simulation is one of the most commonly used methods for estimating steady-state performance but straightforward application results in an initial-transient bias. This award provides a comprehensive set of tools that will enable exact (i.e. with no initial-transient bias) steady-state stochastic simulation of a wide range of complex stochastic networks of interest. This characteristic (complete bias deletion) is what defines a perfect simulation algorithm. This research will therefore enable accurate steady-state analysis in a wide range of areas of societal impact, thereby allowing operators to improve efficiency and performance. Because steady-state analysis arises in a wide variety of areas, including Bayesian Statistics, the award will also be impactful beyond the types of applications mentioned earlier. Steady-state performance analysis of stochastic networks (including general queueing networks) is of great importance in operations research. Stochastic simulation has been a traditional tool used by modelers and researchers to perform steady-state computations. The key challenge in steady-state simulation is the quantification of the bias caused by the initial transient behavior associated to any direct stochastic simulation procedure. This award's focus is on algorithms that fully eliminate the initial transient bias in a non-asymptotic sense; these are known as perfect simulation algorithms. This research will produce the first class of perfect simulation algorithms for general stochastic networks with features such as non-Markovian input, time-inhomogeneous (periodic) characteristics, long-range dependence traffic (e.g. fractional Brownian motion), and multidimensional networks with and without capacity constraints (such as generalized Jackson networks). This research combines techniques from areas such as rare-event simulation and steady-state simulation, which have not been connected for the purpose of developing computational methods. The project has important implications for other scientific areas of great relevance, such as Bayesian Statistics, due to the connection between steady-state simulation through Markov chain Monte Carlo method.