{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:18:14Z","timestamp":1672291094511},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2006,4]]},"abstract":"\n In this article, we study a queue fed by a large number\n n<\/jats:italic>\n of independent discrete-time Gaussian processes with stationary increments. We consider the many-sources asymptotic regime, that is, the buffer-exceedance threshold\n B<\/jats:italic>\n and the service capacity\n C<\/jats:italic>\n are scaled by the number of sources (\n B<\/jats:italic>\n \u2261\n nb<\/jats:italic>\n and\n C<\/jats:italic>\n \u2261\n nc<\/jats:italic>\n ).We discuss four methods for simulating the steady-state probability that the buffer threshold is exceeded: the single-twist method (suggested by large deviation theory), the cut-and-twist method (simulating timeslot by timeslot), the random-twist method (the twist is sampled from a discrete distribution), and the sequential-twist method (simulating source by source).The asymptotic efficiency of these four methods is analytically investigated for\n n<\/jats:italic>\n \u2192 \u221e. A necessary and sufficient condition is derived for the efficiency of the single-twist method, indicating that it is nearly always asymptotically inefficient. The other three methods, however, are asymptotically efficient. We numerically evaluate the four methods by performing a detailed simulation study where it is our main objective to compare the three efficient methods in practical situations.\n <\/jats:p>","DOI":"10.1145\/1138464.1138466","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"119-151","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Fast simulation of overflow probabilities in a queue with Gaussian input"],"prefix":"10.1145","volume":"16","author":[{"given":"A. B.","family":"Dieker","sequence":"first","affiliation":[{"name":"CWI and University of Twente"}]},{"given":"M.","family":"Mandjes","sequence":"additional","affiliation":[{"name":"CWI and University of Twente"}]}],"member":"320","published-online":{"date-parts":[[2006,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1002\/ett.4460130303","article-title":"Most probable paths and performance formulae for buffers with Gaussian input traffic","volume":"13","author":"Addie R.","year":"2002","journal-title":"European Trans. Telecommun."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","article-title":"Risk theory in a Markovian environment","author":"Asmussen S.","year":"1989","journal-title":"Scand. Actuar. J., 69--100.","DOI":"10.1080\/03461238.1989.10413858"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Asmussen S. 2000. Ruin Probabilities. World Scientific Publishing Co. Inc. Asmussen S. 2000. Ruin Probabilities. World Scientific Publishing Co. Inc.","DOI":"10.1142\/2779"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"297","DOI":"10.2143\/AST.27.2.542054","article-title":"Simulation of ruin probabilities for subexponential claims","volume":"27","author":"Asmussen S.","year":"1997","journal-title":"ASTIN Bull."},{"key":"e_1_2_1_5_1","unstructured":"Asmussen S. and Rubinstein R. Y. 1995. Steady state rare events simulation in queueing models and its complexity properties. In Advances in Queueing J. Dshalalow ed. CRC Boca Raton Fla. 429--461. Asmussen S. and Rubinstein R. Y. 1995. Steady state rare events simulation in queueing models and its complexity properties. In Advances in Queueing J. Dshalalow ed. CRC Boca Raton Fla. 429--461."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1214\/aop\/1176994985","article-title":"Large deviations of the sample mean in general vector spaces","volume":"7","author":"Bahadur R. R.","year":"1979","journal-title":"Ann. Probab."},{"key":"e_1_2_1_7_1","unstructured":"Baldi P. and Pacchiarotti B. 2004. Importance sampling for the ruin problem for general Gaussian processes. Preprint. Baldi P. and Pacchiarotti B. 2004. Importance sampling for the ruin problem for general Gaussian processes. Preprint."},{"key":"e_1_2_1_8_1","unstructured":"Bingham N. H. Goldie C. M. and Teugels J. L. 1989. Regular Variation. Cambridge University Press Cambridge Mass. Bingham N. H. Goldie C. M. and Teugels J. L. 1989. Regular Variation. Cambridge University Press Cambridge Mass."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017.S026996480216205X"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"44","DOI":"10.2307\/3214594","article-title":"Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains","volume":"27","author":"Bucklew J. A.","year":"1990","journal-title":"J. Appl. Probab."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1214\/aoap\/1015961169","article-title":"Importance sampling techniques for the multidimensional ruin problem for general Markov additive sequences of random vectors","volume":"12","author":"Collamore J. F.","year":"2002","journal-title":"Ann. Appl. Probab."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1093\/biomet\/74.1.95","article-title":"Tests for Hurst effect","volume":"74","author":"Davies R. B.","year":"1987","journal-title":"Biometrika"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1239\/jap\/1059060897","article-title":"Exact overflow asymptotics for queues with many Gaussian inputs","volume":"40","author":"D\u0229bicki K.","year":"2003","journal-title":"J. Appl. Probab."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019136415112"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Dembo A. and Zeitouni O. 1998. Large Deviations Techniques and Applications 2nd ed. Springer Verlag New York. Dembo A. and Zeitouni O. 1998. Large Deviations Techniques and Applications 2nd ed. Springer Verlag New York.","DOI":"10.1007\/978-1-4612-5320-4"},{"key":"e_1_2_1_16_1","unstructured":"Deuschel J.-D. and Stroock D. W. 1989. Large Deviations. Academic Press Boston Mass. Deuschel J.-D. and Stroock D. W. 1989. Large Deviations. Academic Press Boston Mass."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1016\/j.spa.2004.11.008","article-title":"Conditional limit theorems for queues with Gaussian input, a weak convergence approach","volume":"115","author":"Dieker A. B.","year":"2005","journal-title":"Stochastic Process. Appl."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964803173081"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1239\/aap\/1118858638","article-title":"On asymptotically efficient simulation of large deviation probabilities","volume":"37","author":"Dieker A. B.","year":"2005","journal-title":"Adv. in Appl. Probab."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827592240555"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1080\/10451120410001733845","article-title":"Importance sampling, large deviations, and differential games","volume":"76","author":"Dupuis P.","year":"2004","journal-title":"Stoch. Stoch. Rep."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Ganesh A. O'Connell N. and Wischik D. 2004. Big Queues. Springer Verlag Berlin. Ganesh A. O'Connell N. and Wischik D. 2004. Big Queues. Springer Verlag Berlin.","DOI":"10.1007\/978-3-540-39889-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1214\/aoap\/1034801251","article-title":"Counterexamples in importance sampling for large deviations probabilities","volume":"7","author":"Glasserman P.","year":"1997","journal-title":"Ann. Appl. Probab."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/203091.203094"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1080\/15326349908807544","article-title":"Fast simulation of queues with long-range dependent traffic","volume":"15","author":"Huang C.","year":"1999","journal-title":"Comm. Statist. Stochastic Models"},{"key":"e_1_2_1_26_1","volume-title":"Stochastic Networks: Theory and Applications, F. Kelly et al. eds","author":"Kelly F."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","article-title":"On asymptotically efficient simulation of ruin probabilities in a Markovian environment","author":"Lehtonen T.","year":"1992","journal-title":"Scand. Actuar. J., 60--75.","DOI":"10.1080\/03461238.1992.10413897"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"858","DOI":"10.2307\/1427716","article-title":"Simulating level-crossing probabilities by importance sampling","volume":"24","author":"Lehtonen T.","year":"1992","journal-title":"Adv. in Appl. Probab."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.282603"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1239\/jap\/1032374231","article-title":"Cell loss asymptotics for buffers fed with a large number of independent stationary sources","volume":"36","author":"Likhanov N.","year":"1999","journal-title":"J. Appl. Probab."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/PL00020921","article-title":"On tail probabilities and first passage times for fractional Brownian motion","volume":"49","author":"Michna Z.","year":"1999","journal-title":"Math. Meth. Oper. Res."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Mitrinovi\u0107 D. S. 1970. Analytic Inequalities. Springer Verlag New York. Mitrinovi\u0107 D. S. 1970. Analytic Inequalities. Springer Verlag New York.","DOI":"10.1007\/978-3-642-99970-3"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF01158964","article-title":"A storage model with self-similar input","volume":"16","author":"Norros I.","year":"1994","journal-title":"Queueing Syst."},{"key":"e_1_2_1_34_1","unstructured":"Rockafellar R. T. 1970. Convex Analysis. Princeton University Press Princeton N.J. Rockafellar R. T. 1970. Convex Analysis. Princeton University Press Princeton N.J."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1109\/9.106154","article-title":"Large deviations and efficient simulation of excessive backlogs in a GI\/G\/m queue","volume":"36","author":"Sadowsky J.","year":"1991","journal-title":"IEEE Trans. Autom. Control"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1109\/18.54903","article-title":"On large deviations theory and asymptotically efficient Monte Carlo estimation","volume":"36","author":"Sadowsky J. S.","year":"1990","journal-title":"IEEE Trans. Inform. Theory"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1214\/aos\/1176343541","article-title":"Importance sampling in the Monte Carlo study of sequential tests","volume":"4","author":"Siegmund D.","year":"1976","journal-title":"Ann. Statist."},{"key":"e_1_2_1_38_1","unstructured":"Wischik D. 2001a. Moderate deviations in queueing theory. Preprint. Wischik D. 2001a. Moderate deviations in queueing theory. Preprint."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1214\/aoap\/1015345296","article-title":"Sample path large deviations for queues with many inputs","volume":"11","author":"Wischik D.","year":"2001","journal-title":"Ann. Appl. Probab."},{"key":"e_1_2_1_40_1","first-page":"409","article-title":"Simulation of stationary Gaussian processes in {0,1}d","volume":"3","author":"Wood A. T. A.","year":"1994","journal-title":"J. Comput. Graphical Statistics"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1138464.1138466","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T18:42:53Z","timestamp":1672252973000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1138464.1138466"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["10.1145\/1138464.1138466"],"URL":"http:\/\/dx.doi.org\/10.1145\/1138464.1138466","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"value":"1049-3301","type":"print"},{"value":"1558-1195","type":"electronic"}],"subject":["Computer Science Applications","Modeling and Simulation"],"published":{"date-parts":[[2006,4]]},"assertion":[{"value":"2006-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}