Collaborative Research: Perfect Simulation of Stochastic Networks

合作研究：随机网络的完美模拟

• 批准号: 1538217
• 负责人: Jose Blanchet
• 金额: $ 12.76万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1538217&HistoricalAwards=false
• 关键词: Collaborative; Research; Perfect; Simulation; Stochastic

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.

随机网络是一类具有有限资源竞争的时变概率模型。 它们用于广泛的工程应用，例如通信网络、呼叫中心和制造系统。这些类型的系统的操作者通常对长期实现高水平的性能感兴趣，即，在稳定状态下。因此，设计有效的随机网络稳态分析计算方法是非常重要的。 仿真是估计稳态性能的最常用方法之一，但直接应用会导致初始瞬态偏差。该奖项提供了一套全面的工具，将使精确的（即没有初始瞬态偏差）稳态随机模拟的广泛的复杂的随机网络的利益。这个特性（完全偏差删除）是完美模拟算法的定义。因此，这项研究将能够在广泛的社会影响领域进行准确的稳态分析，从而使运营商能够提高效率和性能。由于稳态分析出现在包括贝叶斯统计在内的各种领域，该奖项的影响力也将超出前面提到的应用类型。随机网络（包括一般随机网络）的稳态性能分析在运筹学中具有重要意义。随机模拟一直是建模者和研究人员用来执行稳态计算的传统工具。稳态模拟的关键挑战是量化与任何直接随机模拟过程相关的初始瞬态行为所引起的偏差。该奖项的重点是在非渐近意义上完全消除初始瞬态偏差的算法;这些算法被称为完美仿真算法。这项研究将产生第一类完美的模拟算法的一般随机网络的功能，如非马尔可夫输入，时间非齐次（周期性）的特点，长程相关业务（如分数布朗运动），和多维网络的容量限制和没有（如广义杰克逊网络）。 这项研究结合了稀有事件模拟和稳态模拟等领域的技术，这些技术尚未连接到开发计算方法的目的。该项目具有重要的影响，其他科学领域的极大的相关性，如贝叶斯统计，由于通过马尔可夫链蒙特卡罗方法之间的连接稳态模拟。