Exact Sampling of Stationary and Time-Reversed Queues

DOI10.1145/2822892MaRDI QIDQ4635229zbMATH OpenOpenAlexFDO

Authors Aya Wallwater, Jose Blanchet

Publication date 16 April 2018

Published in ACM Transactions on Modeling and Computer Simulation (Search for Journal in Brave)

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

zbMATH Keywords

simulation of discrete eventssimulation output analysissimulation theory

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Queues and service in operations research (90B22)

Abstract: We provide the first algorithm that under minimal assumptions allows to simulate the stationary waiting-time sequence of a single-server queue backwards in time, jointly with the input processes of the queue (inter-arrival and service times). The single-server queue is useful in applications of DCFTP (Dominated Coupling From The Past), which is a well known protocol for simulation without bias from steady-state distributions. Our algorithm terminates in finite time assuming only finite mean of the inter-arrival and service times. In order to simulate the single-server queue in stationarity until the first idle period in finite expected termination time we require the existence of finite variance. This requirement is also necessary for such idle time (which is a natural coalescence time in DCFTP applications) to have finite mean. Thus, in this sense, our algorithm is applicable under minimal assumptions.

Recommendations

• Sampling at subexponential times, with queueing applications
• Exact sampling for some multi-dimensional queueing models with renewal input
• Perfect sampling for queues and network models
• Perfect sampling of GI/GI/\(c\) queues
• Perfect sampling of Jackson queueing networks
• Behaviour of queueing approximations based on sample moments
• Perfect sampling of a single-server queue with periodic Poisson arrivals
• Perfect Sampling of Networks with Finite and Infinite Capacity Queues

Cited in

(15)

• Sampling at subexponential times, with queueing applications
• Perfect sampling of GI/GI/\(c\) queues
• On logarithmically optimal exact simulation of max-stable and related random fields on a compact set
• Perfect simulation of \(\mathrm{M}/\mathrm{G}/c\) queues
• Perfect Sampling of Networks with Finite and Infinite Capacity Queues
• Exact simulation of the stationary distribution of the FIFO M/G/c queue
• Relating Time and Customer Averages for Queues Using ‘forward’ Coupling from the Past
• Exact simulation of the stationary distribution of the FIFO M/G/c queue: the general case for \(\rho < c\)
• A dichotomy for sampling barrier-crossing events of random walks with regularly varying tails
• scientific article; zbMATH DE number 1833414 (Why is no real title available?)
• Exact sampling of the infinite horizon maximum of a random walk over a nonlinear boundary
• Perfect Sampling of Hawkes Processes and Queues with Hawkes Arrivals
• Exact sampling for some multi-dimensional queueing models with renewal input
• Perfect Sampling of Generalized Jackson Networks
• Sampling the functional Kolmogorov forward equations for nonstationary queueing networks

This page was built for publication: Exact Sampling of Stationary and Time-Reversed Queues

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