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.

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