Jose Blanchet and Aya Wallwater. 2015. Exact Sampling of Stationary and Time-Reversed Queues. ACM Trans. Model. Comput. Simul. 25, 4, Article 26 (November 2015), 27 pages. https://doi.org/10.1145/2822892
Abstract
We provide the first algorithm that, under minimal assumptions, allows simulation of the stationary waiting-time sequence of a single-server queue backward in time, jointly with the input processes of the queue (interarrival and service times). The single-server queue is useful in applications of Dominated Coupling from the Past (DCFTP), 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 interarrival and service times. 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.
Authors
Jose Blanchet, Aya Wallwater
Publication date
2015/11/16
Journal
ACM Transactions on Modeling and Computer Simulation (TOMACS)
Volume
25
Issue
4
Pages
1-27
Publisher
ACM
