Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-28T02:42:58.706Z Has data issue: false hasContentIssue false
  • English
  • Français

Perfect sampling for infinite server and loss systems

Part of: Special processes Probabilistic methods, simulation and stochastic differential equations

Published online by Cambridge University Press:  21 March 2016

Jose Blanchet  and
Jing Dong
Jose Blanchet*
Affiliation:
Columbia University
Jing Dong*
Affiliation:
Columbia University
*
∗ Postal address: Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027, USA. Email address: [email protected]
∗∗ Current address: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208, USA. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We present the first class of perfect sampling (also known as exact simulation) algorithms for the steady-state distribution of non-Markovian loss systems. We use a variation of dominated coupling from the past. We first simulate a stationary infinite server system backwards in time and analyze the running time in heavy traffic. In particular, we are able to simulate stationary renewal marked point processes in unbounded regions. We then use the infinite server system as an upper bound process to simulate the loss system. The running time analysis of our perfect sampling algorithm for loss systems is performed in the quality-driven (QD) and the quality-and-efficiency-driven regimes. In both cases, we show that our algorithm achieves subexponential complexity as both the number of servers and the arrival rate increase. Moreover, in the QD regime, our algorithm achieves a nearly optimal rate of complexity.

Keywords

Perfect samplingdominated coupling from the pastinfinite server queueloss queuerenewal point processmany-server asymptotics

MSC classification

Primary: 65C05: Monte Carlo methods 68U20: Simulation
Secondary: 60K25: Queueing theory
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 47 , Issue 3 , September 2015 , pp. 761 - 786
Copyright
Copyright © Applied Probability Trust 2015 

References

Adler, R. J. (1990). An Introduction to Continuity, Extrema, and Related Topics for General Gaussian Processes (IMS Lecture Notes Monogr. Ser. 12), IMS, Hayward, CA.Google Scholar
Asmussen, S. (2003). Applied Probability and Queues, 2nd edn. Spinger, New York.Google Scholar
Berthelsen, K. K. and M⊘ller, J. (2002). A primer on perfect simulation for spatial point processes. Bull. Braz. Math. Soc. (N.S.) 33, 351–367.Google Scholar
Blanchet, J. and Dong, J. (2012). Sampling point processes on stable unbounded regions and exact simulation of queues. In Proc. 2012 Winter Simulation Conference, IEEE, New York, pp. 1–12.Google Scholar
Blanchet, J. and Lam, H. (2014). Rare-event simulation for many-sever queues. Math. Operat. Res. 39, 1142–1178.Google Scholar
Blanchet, J. and Sigman, K. (2011). On exact sampling of stochastic perpetuities. In New Frontiers in Applied Probability (J. Appl. Prob. Spec. Vol. 48A, Applied Probability Trust, Sheffield, pp. 165–182.Google Scholar
Blanchet, J., Chen, X. and Lam, H. (2014). Two-parameter sample path large deviations for infinite-server queues. Stoch. Systems 4, 206–249.Google Scholar
Brown, L. et al. (2005). Statistical analysis of a telephone call center: a queueing-science perspective. J. Amer. Statist. Assoc. 100, 36–50.CrossRefGoogle Scholar
Bušić, A., Gaujal, B. and Perronnin, F. (2012). Perfect sampling of networks with finite and infinite capacity queues. In Analytical and Stochastic Modeling Techniques and Applications (Lecture Notes Comput. Sci. 7314), Springer, Berlin, pp. 136-149.CrossRefGoogle Scholar
Connor, S. B. and Kendall, W. S. (2007). Perfect simulation for a class of positive recurrent Markov chains. Ann. Appl. Prob. 17, 781–808. %ED: is this double page range correct—check?Google Scholar
Corcoran, J. N. and Tweedie, R. L. (2001). Perfect sampling of ergodic Harris chains. Ann. Appl. Prob. 11, 438–451.CrossRefGoogle Scholar
Dong, J. (2014). Studies in stochastoc networks: efficient Monte-Carlo methods, modeling and asymptotic analysis. Doctoral Thesis. Columbia University.Google Scholar
Ensor, K. B. and Glynn, P. W. (2000). Simulating the maximum of a random walk. J. Statist. Planning Infer. 85, 127–135.Google Scholar
Ferrari, P. A., Fernández, R. and Garcia, N. L. (2002). Perfect simulation for interacting point processes, loss networks and Ising models. Stoch. Process. Appl. 102, 63–88.Google Scholar
Foss, S. G. and Tweedie, R. L. (1998). Perfect simulation and backward coupling. Commun. Statist. Stoch. Models 14, 187–203.Google Scholar
Kelly, F. P. (1991). Loss networks. Ann. Appl. Prob. 1, 319–378.Google Scholar
Kendall, W. S. (1995). Perfect simulation for area-interaction point processes. In Probability Towards 2000, Springer, New York, pp. 218–234.Google Scholar
Kendall, W. S. (2004). Geometric ergodicity and perfect simulation. Electron. Commun. Prob. 9, 140–151.Google Scholar
Kendall, W. S. and M⊘ller, J. (2000). Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes. Adv. Appl. Prob. 32, 844–865.CrossRefGoogle Scholar
Murdoch, D. J. and Takahara, G. (2006). Perfect sampling for queues and network models. ACM Trans. Model. Comput. Simul. 16, 76–92.CrossRefGoogle Scholar
Pang, G. and Whitt, W. (2010). Two-parameter heavy-traffic limits for infinite-server queues. Queueing Systems 65, 325–364.Google Scholar
Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9, 223–252.3.0.CO;2-O>CrossRefGoogle Scholar
Sigman, K. (2011). Exact simulation of the stationary distribution of the FIFO M/G/c queue. In New Frontiers in Applied Probability (J. Appl. Prob. Spec. Vol. 48A), Applied Probability Trust, Sheffield, pp. 209–213.Google Scholar
Sigman, K. (2012). Exact simulation of the stationary distribution of the FIFO M/G/c queue: The general case of ρ < c . Queueing Systems 70, 37–43.Google Scholar