Perfect sampling for infinite server and loss systems

DOI10.1239/AAP/1444308881MaRDI QIDQ3450508zbMATH OpenOpenAlexFDO

Authors Jing Dong, Jose Blanchet

Publication date 6 November 2015

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.4088

zbMATH Keywords

algorithminfinite server queueperfect samplingrenewal point processdominated coupling from the pastmany-server asymptoticsloss queuenon-Markovian loss system

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Queueing theory (aspects of probability theory) (60K25)

Abstract: We present the first class of perfect sampling (also known as exact simulation) algorithms for the steady-state distribution of non-Markovian loss networks. We use a variation of Dominated Coupling From The Past for which we simulate a stationary infinite server queue 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 use the infinite server queue as an upper bound process to simulate loss systems. 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 sub-exponential 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 convergence.

Recommendations

• Perfect sampling of GI/GI/\(c\) queues
• Perfect sampling of Jackson queueing networks
• Perfect and nearly perfect sampling of work-conserving queues
• Perfect Sampling of Networks with Finite and Infinite Capacity Queues
• Perfect sampling of a single-server queue with periodic Poisson arrivals

Cited in

(13)

• ɛ-Strong Simulation of Fractional Brownian Motion and Related Stochastic Differential Equations
• scientific article; zbMATH DE number 1833414 (Why is no real title available?)
• Perfect simulation of \(\mathrm{M}/\mathrm{G}/c\) queues
• Perfect sampling of GI/GI/\(c\) queues
• Perfect and nearly perfect sampling of work-conserving queues
• Perfect sampling of Jackson queueing networks
• Perfect sampling of a single-server queue with periodic Poisson arrivals
• Simulation study for the clan of ancestors in a perfect simulation scheme of a continuous one-dimensional loss network
• Omnithermal perfect simulation for multi-server queues
• Exact sampling of the infinite horizon maximum of a random walk over a nonlinear boundary
• Coupling in the queue with impatience: case of several servers
• Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers
• Exact sampling for some multi-dimensional queueing models with renewal input

This page was built for publication: Perfect sampling for infinite server and loss systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3450508)