Exact Sampling of Stationary and Time-Reversed Queues

DOI10.1145/2822892zbMATH Open1384.90025arXiv1403.8117OpenAlexW158389970MaRDI QIDQ4635229FDOQ4635229

Aya Wallwater, Jose Blanchet

Publication date: 16 April 2018

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

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.

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

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

zbMATH Keywords

simulation output analysissimulation theorysimulation of discrete events

Mathematics Subject Classification ID

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

Cited In (12)

• Perfect Sampling of Hawkes Processes and Queues with Hawkes Arrivals
• Title not available (Why is that?)
• Perfect simulation of \(\mathrm{M}/\mathrm{G}/c\) queues
• Sampling at subexponential times, with queueing applications
• Perfect sampling of GI/GI/\(c\) queues
• Perfect Sampling of Networks with Finite and Infinite Capacity Queues
• Exact sampling of the infinite horizon maximum of a random walk over a nonlinear boundary
• Relating Time and Customer Averages for Queues Using ‘forward’ Coupling from the Past
• A dichotomy for sampling barrier-crossing events of random walks with regularly varying tails
• Perfect Sampling of Generalized Jackson Networks
• Exact sampling for some multi-dimensional queueing models with renewal input
• On logarithmically optimal exact simulation of max-stable and related random fields on a compact set

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)