{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T03:04:29Z","timestamp":1785207869580,"version":"3.55.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,11,16]],"date-time":"2015-11-16T00:00:00Z","timestamp":1447632000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CMMI-0846816, CMMI-1069064, and DMS-1320550"],"award-info":[{"award-number":["CMMI-0846816, CMMI-1069064, and DMS-1320550"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2015,11,16]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2822892","type":"journal-article","created":{"date-parts":[[2015,11,18]],"date-time":"2015-11-18T13:42:28Z","timestamp":1447854148000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Exact Sampling of Stationary and Time-Reversed Queues"],"prefix":"10.1145","volume":"25","author":[{"given":"Jose","family":"Blanchet","sequence":"first","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aya","family":"Wallwater","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,11,16]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Applied Probability and Queues","author":"Asmussen S.","unstructured":"S. Asmussen . 2003. Applied Probability and Queues ( 2 nd Ed.). Springer , New York, NY . S. Asmussen. 2003. Applied Probability and Queues (2nd Ed.). Springer, New York, NY.","edition":"2"},{"key":"e_1_2_1_2_1","unstructured":"J. Blanchet and X. Chen. 2012. Steady-State Simulation for Reflected Brownian Motion and Related Networks. Retrieved October 5 2015 from http:\/\/arxiv.org\/pdf\/1202.2062.pdf.  J. Blanchet and X. Chen. 2012. Steady-State Simulation for Reflected Brownian Motion and Related Networks. Retrieved October 5 2015 from http:\/\/arxiv.org\/pdf\/1202.2062.pdf."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 2012 Winter Simulation Conferrence.","author":"Blanchet J.","unstructured":"J. Blanchet and J. Dong . 2012. Sampling point processes on stable unbounded regions and exact simulation of queues . In Proceedings of the 2012 Winter Simulation Conferrence. J. Blanchet and J. Dong. 2012. Sampling point processes on stable unbounded regions and exact simulation of queues. In Proceedings of the 2012 Winter Simulation Conferrence."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1318940463"},{"key":"e_1_2_1_5_1","unstructured":"S. Connor and S. Kendall. 2014. Perfect Simulation of M\/G\/c Queues. Retrieved October 5 2015 from http:\/\/arxiv.org\/abs\/1402.7248.  S. Connor and S. Kendall. 2014. Perfect Simulation of M\/G\/c Queues. Retrieved October 5 2015 from http:\/\/arxiv.org\/abs\/1402.7248."},{"key":"e_1_2_1_6_1","series-title":"Duxbury Advanced Series.","volume-title":"Probability: Theory and Examples","author":"Durrett R.","year":"2005","unstructured":"R. Durrett . 2005 . Probability: Theory and Examples . Duxbury Advanced Series. R. Durrett. 2005. Probability: Theory and Examples. Duxbury Advanced Series."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-3758(99)00075-0"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-006-4261-z"},{"key":"e_1_2_1_9_1","unstructured":"J. Blanchet J. Dong and Y. Pei. 2015. Perfect Sampling of GI\/G\/c Queues. Retrieved October 5 2015 from http:\/\/www.columbia.edu\/&sim;jb2814\/papers\/exact_multiserver_v12.pdf.  J. Blanchet J. Dong and Y. Pei. 2015. Perfect Sampling of GI\/G\/c Queues. Retrieved October 5 2015 from http:\/\/www.columbia.edu\/&sim;jb2814\/papers\/exact_multiserver_v12.pdf."},{"key":"e_1_2_1_10_1","volume-title":"Probability Towards","author":"Kendall W. S.","year":"2000","unstructured":"W. S. Kendall . 1998. Perfect simulation for the area-interaction point process . In Probability Towards 2000 . Lecture Notes in Statistics, Vol. 128 . Springer , 218--234. W. S. Kendall. 1998. Perfect simulation for the area-interaction point process. In Probability Towards 2000. Lecture Notes in Statistics, Vol. 128. Springer, 218--234."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100036094"},{"key":"e_1_2_1_12_1","unstructured":"K. Murthy S. Juneja and J. Blanchet. 2013. State-Independent Importance Sampling for Random Walks with Regularly Varying Increments. Retrieved October 5 2015 from http:\/\/arxiv.org\/pdf\/1206.3390.pdf.  K. Murthy S. Juneja and J. Blanchet. 2013. State-Independent Importance Sampling for Random Walks with Regularly Varying Increments. Retrieved October 5 2015 from http:\/\/arxiv.org\/pdf\/1206.3390.pdf."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 7th International Conference on Random Structures and Algorithms. 223--252","author":"Propp J. G.","unstructured":"J. G. Propp and D. B. Wilson . 1996. Exact sampling with coupled Markov chains and applications to statistical mechanics . In Proceedings of the 7th International Conference on Random Structures and Algorithms. 223--252 . J. G. Propp and D. B. Wilson. 1996. Exact sampling with coupled Markov chains and applications to statistical mechanics. In Proceedings of the 7th International Conference on Random Structures and Algorithms. 223--252."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1318940466"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-011-9266-6"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2822892","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2822892","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:31Z","timestamp":1750225711000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2822892"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,16]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,11,16]]}},"alternative-id":["10.1145\/2822892"],"URL":"https:\/\/doi.org\/10.1145\/2822892","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"value":"1049-3301","type":"print"},{"value":"1558-1195","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,16]]},"assertion":[{"value":"2013-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}