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 device 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.