Perfect sampling for infinite server and loss systems
Perfect sampling for infinite server and loss systems
复制标题
无限服务器和丢失系统的完美采样
DOI：
--
复制
发表时间：
2013
影响因子：
1.2
通讯作者：
Jing Dong
中科院分区：
文献类型：
--
作者：
J. Blanchet;Jing Dong
对于非马尔科夫损失系统的稳态分布，我们提出了第一类完全抽样(也称为精确模拟)算法。我们使用了过去的支配耦合的一种变体。我们首先对一个固定的无限服务器系统进行时间倒推模拟，并对系统在繁忙流量下的运行时间进行分析。特别地，我们能够模拟无界区域上的平稳更新标记点过程。然后以无限服务系统作为上界过程来模拟损失系统。在质量驱动(QD)和质量和效率驱动(QD)两种情况下，我们对损失系统的完美抽样算法进行了运行时间分析。在这两种情况下，我们证明了随着服务器数量和到达率的增加，我们的算法达到了次指数复杂度。此外，在QD机制下，我们的算法获得了近乎最优的复杂度。
We present the first class of perfect sampling (also known as exact simulation) algorithms for the steady-state distribution of non-Markovian loss systems. We use a variation of dominated coupling from the past. We first simulate a stationary infinite server system backwards in time and analyze the running time in heavy traffic. In particular, we are able to simulate stationary renewal marked point processes in unbounded regions. We then use the infinite server system as an upper bound process to simulate the loss system. The running time analysis of our perfect sampling algorithm for loss systems is performed in the quality-driven (QD) and the quality-and-efficiency-driven regimes. In both cases, we show that our algorithm achieves subexponential complexity as both the number of servers and the arrival rate increase. Moreover, in the QD regime, our algorithm achieves a nearly optimal rate of complexity.