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.

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