Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 6 (2016) open journal systems 


Stein's method for steady-state diffusion approximations: An introduction through the Erlang-A and Erlang-C models

Anton Braverman, Cornell University
J.G. Dai, Cornell University
Jiekun Feng, Cornell University


Abstract
This paper provides an introduction to the Stein method framework in the context of steady-state diffusion approximations. The framework consists of three components: the Poisson equation and gradient bounds, generator coupling, and moment bounds. Working in the setting of the Erlang-A and Erlang-C models, we prove that both Wasserstein and Kolmogorov distances between the stationary distribution of a normalized customer count process, and that of an appropriately defined diffusion process decrease at a rate of \(1/\sqrt{R}\), where \(R\) is the offered load. Futhermore, these error bounds are universal, valid in any load condition from lightly loaded to heavily loaded.

AMS 2000 subject classifications: 60K25, 60F99, 60J60

Keywords: Stein's method, steady-state, diffusion approximation, convergence rates, Erlang-A, Erlang-C

Creative Common LOGO

Full Text: PDF


Braverman, Anton, Dai, J.G., Feng, Jiekun, Stein's method for steady-state diffusion approximations: An introduction through the Erlang-A and Erlang-C models, Stochastic Systems, 6, (2016), 301-366 (electronic). DOI: 10.1214/15-SSY212.

References

[1]    Atar, R. (2012). A diffusion regime with nondegenerate slowdown. Operations Research, 60 490–500. URL http://dx.doi.org/10.1287/opre.1110.1030. MR2935073

[2]    Barbour, A. (1990). Stein’s method for diffusion approximations. Probability Theory and Related Fields, 84 297–322. URL http://dx.doi.org/10.1007/BF01197887. MR1035659

[3]    Barbour, A. and Brown, T. (1992). Stein’s method and point process approximation. Stochastic Processes and their Applications, 43 9 – 31. URL http://dx.doi.org/10.1016/0304-4149(92)90073-Y. MR1190904

[4]    Barbour, A. and Xia, A. (2006). On Stein’s factors for Poisson approximation in Wasserstein distance. Bernoulli, 12 943–954. URL http://dx.doi.org/10.3150/bj/1165269145.

[5]    Barbour, A. D. (1988). Stein’s method and Poisson process convergence. Journal of Applied Probability, 25 pp. 175–184. URL http://www.jstor.org/stable/3214155. MR0974580

[6]    Blanchet, J. and Glynn, P. (2007). Uniform renewal theory with applications to expansions of random geometric sums. Advances in Applied Probability, 39 1070–1097. URL https://doi.org/10.1017/S000186780000224X. MR2381589

[7]    Borovkov, A. (1964). Some limit theorems in the theory of mass service, I. Theory of Probability and its Applications, 9 550–565. URL http://dx.doi.org/10.1137/1109078.

[8]    Borovkov, A. (1965). Some limit theorems in the theory of mass service, II. Theory of Probability and its Applications, 10 375–400. URL http://dx.doi.org/10.1137/1110046.

[9]    Bramson, M. (1998). State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems, 30 89–140. URL http://dx.doi.org/10.1023/A:1019160803783. MR1663763

[10]    Braverman, A. and Dai, J. G. (2017). Stein’s method for steady-state diffusion approximations of M∕Ph∕n + M systems. Ann. Appl. Probab. URL http://arxiv.org/abs/1503.00774.

[11]    Brown, T. C. and Xia, A. (2001). Stein’s method and birth-death processes. Ann. Probab., 29 1373–1403. URL http://dx.doi.org/10.1214/aop/1015345606.

[12]    Budhiraja, A. and Lee, C. (2009). Stationary distribution convergence for generalized Jackson networks in heavy traffic. Mathematics of Operations Research, 34 45–56. URL http://dx.doi.org/10.1287/moor.1080.0353.

[13]    Chatterjee, S. (2014). A short survey of Stein’s method. To appear in Proceedings of ICM 2014, URL http://arxiv.org/abs/1404.1392.

[14]    Chen, L. H. Y. (1975). Poisson approximation for dependent trials. Ann. Probab., 3 534–545. URL http://dx.doi.org/10.1214/aop/1176996359.

[15]    Chen, L. H. Y., Goldstein, L. and Shao, Q.-M. (2011). Normal approximation by Stein’s method. Probability and its Applications (New York), Springer, Heidelberg. URL http://dx.doi.org/10.1007/978-3-642-15007-4.

[16]    Dai, J. G. and He, S. (2013). Many-server queues with customer abandonment: Numerical analysis of their diffusion model. Stochastic Systems, 3 96–146. URL http://dx.doi.org/10.1214/11-SSY029.

[17]    Dai, J. G., He, S. and Tezcan, T. (2010). Many-server diffusion limits for G∕Ph∕n + GI queues. Annals of Applied Probability, 20 1854–1890. URL http://projecteuclid.org/euclid.aoap/1282747403.

[18]    Dai, J. G. and Lin, W. (2008). Asymptotic optimality of maximum pressure policies in stochastic processing networks. Annals of Applied Probability, 18 2239–2299. URL http://projecteuclid.org/euclid.aoap/1227708918.

[19]    Ehm, W. (1991). Binomial approximation to the Poisson binomial distribution. Statistics & Probability Letters, 11 7 – 16. URL http://www.sciencedirect.com/science/article/pii/016771529190170V.

[20]    Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. Wiley, New York. URL http://onlinelibrary.wiley.com/book/10.1002/9780470316658.

[21]    Gamarnik, D. and Stolyar, A. L. (2012). Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution. Queueing Systems, 71 25–51. URL http://dl.acm.org/citation.cfm?id=2339029.

[22]    Gamarnik, D. and Zeevi, A. (2006). Validity of heavy traffic steady-state approximation in generalized Jackson networks. Ann. Appl. Probab., 16 56–90. URL http://projecteuclid.org/euclid.aoap/1141654281. MR2209336

[23]    Gan, H. and Xia, A. (2015). Stein’s method for conditional compound Poisson approximation. Statistics & Probability Letters, 100 19 – 26. URL http://www.sciencedirect.com/science/article/pii/S0167715215000486.

[24]    Gans, N., Koole, G. and Mandelbaum, A. (2003). Telephone call centers: Tutorial, review, and research prospects. Manufacturing & Service Operations Management, 5 79–141. http://msom.journal.informs.org/cgi/reprint/5/2/79.pdf, URL http://dx.doi.org/10.1287/msom.5.2.79.160719.

[25]    Gibbs, A. L. and Su, F. E. (2002). On choosing and bounding probability metrics. International Statistical Review / Revue Internationale de Statistique, 70 pp. 419–435. URL http://www.jstor.org/stable/1403865.

[26]    Glynn, P. W. and Zeevi, A. (2008). Bounding stationary expectations of Markov processes. In Markov processes and related topics: a Festschrift for Thomas G. Kurtz, vol. 4 of Inst. Math. Stat. Collect. Inst. Math. Statist., Beachwood, OH, 195–214. URL http://dx.doi.org/10.1214/074921708000000381.

[27]    Gรถtze, F. (1991). On the rate of convergence in the multivariate CLT. Ann. Probab., 19 724–739. URL http://dx.doi.org/10.1214/aop/1176990448.

[28]    Gurvich, I. (2014). Diffusion models and steady-state approximations for exponentially ergodic Markovian queues. The Annals of Applied Probability, 24 2527–2559. URL http://dx.doi.org/10.1214/13-AAP984.

[29]    Gurvich, I. (2014). Validity of heavy-traffic steady-state approximations in multiclass queueing networks: the case of queue-ratio disciplines. Mathematics of Operations Research, 39 121–162. URL http://dx.doi.org/10.1287/moor.2013.0593.

[30]    Gurvich, I. and Huang, J. (2016). Beyond heavy-traffic regimes: universal bounds and controls for the single-server queue. Working paper, URL https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2784752.

[31]    Gurvich, I., Huang, J. and Mandelbaum, A. (2014). Excursion-based universal approximations for the Erlang-A queue in steady-state. Mathematics of Operations Research, 39 325–373. URL http://dx.doi.org/10.1287/moor.2013.0606.

[32]    Halfin, S. and Whitt, W. (1981). Heavy-traffic limits for queues with many exponential servers. Oper. Res., 29 567–588. URL http://www.jstor.org/stable/170115.

[33]    Harrison, J. M. (1978). The diffusion approximation for tandem queues in heavy traffic. Advances in Applied Probability, 10 886–905. URL http://www.jstor.org/stable/1426665.

[34]    Harrison, J. M. and Nguyen, V. (1993). Brownian models of multiclass queueing networks: Current status and open problems. Queueing Systems: Theory and Applications, 13 5–40. URL http://dx.doi.org/10.1007/BF01158927.

[35]    Harrison, J. M. and Williams, R. J. (1987). Brownian models of open queueing networks with homogeneous customer populations. Stochastics, 22 77–115. URL http://dx.doi.org/10.1080/17442508708833469.

[36]    Henderson, S. G. (1997). Variance reduction via an approximating Markov process. Ph.D. thesis, Department of Operations Research, Stanford University. http://people.orie.cornell.edu/shane/pubs/thesis.pdf.

[37]    Iglehart, D. L. and Whitt, W. (1970). Multiple channel queues in heavy traffic I. Advances in Applied Probability, 2 150–177. URL http://www.jstor.org/stable/3518347.

[38]    Iglehart, D. L. and Whitt, W. (1970). Multiple channel queues in heavy traffic II: sequences, networks, and batches. Advances in Applied Probability, 2 355–369. URL http://www.jstor.org/stable/1426324.

[39]    Janssen, A. J. E. M., van Leeuwaarden, J. S. H. and Zwart, B. (2008). Corrected asymptotics for a multi-server queue in the Halfin-Whitt regime. Queueing Syst., 58 261–301. URL http://dx.doi.org/10.1007/s11134-008-9070-0.

[40]    Janssen, A. J. E. M., van Leeuwaarden, J. S. H. and Zwart, B. (2008). Gaussian expansions and bounds for the Poisson distribution applied to the Erlang B formula. Adv. in Appl. Probab., 40 122–143. URL http://dx.doi.org/10.1239/aap/1208358889.

[41]    Janssen, A. J. E. M., van Leeuwaarden, J. S. H. and Zwart, B. (2011). Refining square-root safety staffing by expanding Erlang C. Operations Research, 59 1512–1522. URL http://dx.doi.org/10.1287/opre.1110.0991.

[42]    Kang, W., Kelly, F., Lee, N. and Williams, R. (2009). State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy. The Annals of Applied Probability, 19 1719–1780. URL http://www.jstor.org/stable/25662521. MR2569806

[43]    Katsuda, T. (2010). State-space collapse in stationarity and its application to a multiclass single-server queue in heavy traffic. Queueing Systems: Theory and Applications, 65 237–273. URL http://dx.doi.org/10.1007/s11134-010-9178-x.

[44]    Kusuoka, S. and Tudor, C. A. (2012). Stein’s method for invariant measures of diffusions via malliavin calculus. Stochastic Processes and their Applications, 122 1627 – 1651. URL http://www.sciencedirect.com/science/article/pii/S0304414912000270.

[45]    Lindvall, T. (1992). Lectures on the coupling method. Wiley series in probability and mathematical statistics, Wiley, New York. A Wiley-Interscience publication.

[46]    Loh, W.-L. (1992). Stein’s method and multinomial approximation. Ann. Appl. Probab., 2 536–554. URL http://dx.doi.org/10.1214/aoap/1177005648. MR1177898

[47]    Meyn, S. P. and Tweedie, R. L. (1993). Stability of Markovian processes III: Foster-Lyapunov criteria for continuous time processes. Adv. Appl. Probab., 25 518–548. URL http://www.jstor.org/stable/1427522.

[48]    Pardoux, E. and Veretennikov, Y. (2001). On the Poisson equation and diffusion approximation. I. Ann. Probab., 29 1061–1085. URL http://dx.doi.org/10.1214/aop/1015345596.

[49]    Peterson, W. P. (1991). A heavy traffic limit theorem for networks of queues with multiple customer types. Mathematics of Operations Research, 16 90–118. URL http://www.jstor.org/stable/3689851.

[50]    Reed, J. (2009). The G∕GI∕N queue in the Halfin-Whitt regime. Annals of Applied Probability, 19 2211–2269. URL http://projecteuclid.org/euclid.aoap/1259158771.

[51]    Reiman, M. I. (1984). Open queueing networks in heavy traffic. Mathematics of Operations Research, 9 441–458. URL http://www.jstor.org/stable/3689532.

[52]    Ross, N. (2011). Fundamentals of Stein’s method. Probab. Surv., 8 210–293. URL http://dx.doi.org/10.1214/11-PS182.

[53]    Stein, C. (1972). A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 2: Probability Theory. University of California Press, Berkeley, Calif., 583–602. URL http://projecteuclid.org/euclid.bsmsp/1200514239.

[54]    Stein, C. (1986). Approximate computation of expectations. Lecture Notes-Monograph Series, 7. URL http://www.jstor.org/stable/4355512.

[55]    Stolyar, A. L. (2004). Maxweight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic. Ann. Appl. Probab., 14 1–53. URL http://dx.doi.org/10.1214/aoap/1075828046. MR2023015

[56]    Stolyar, A. L. (2015). Tightness of stationary distributions of a flexible-server system in the Halfin-Whitt asymptotic regime. Stoch. Syst., 5 239–267. URL http://dx.doi.org/10.1214/14-SSY139.

[57]    Stroock, D. W. and Varadhan, S. R. S. (1979). Multidimensional Diffusion Processes. Springer, New York. URL http://link.springer.com/book/10.1007\%2F3-540-28999-2.

[58]    Tezcan, T. (2008). Optimal control of distributed parallel server systems under the Halfin and Whitt regime. Mathematics of Operations Research, 33 51–90. URL http://search.proquest.com/docview/212618995?accountid=10267.

[59]    Ward, A. R. and Glynn, P. W. (2003). A diffusion approximation for a Markovian queue with reneging. Queueing Systems, 43 103–128. URL http://dx.doi.org/10.1023/A\%3A1021804515162.

[60]    Weinberg, G. V. (2000). Stein factor bounds for random variables. Journal of Applied Probability, 37 1181–1187. URL http://www.jstor.org/stable/3215511.

[61]    Whitt, W. (2002). Stochastic-process limits. Springer, New York. URL http://link.springer.com/book/10.1007\%2Fb97479.

[62]    Whitt, W. (2003). How multiserver queues scale with growing congestion-dependent demand. Operations Research, 51 531–542. URL http://pubsonline.informs.org/doi/abs/10.1287/opre.51.4.531.16093. MR1991969

[63]    Williams, R. J. (1998). Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Systems, 30 27–88. URL http://dx.doi.org/10.1023/A:1019108819713.

[64]    Ye, H.-Q. and Yao, D. D. (2012). A stochastic network under proportional fair resource control—diffusion limit with multiple bottlenecks. Operations Research, 60 716–738. URL http://dx.doi.org/10.1287/opre.1120.1047.

[65]    Ying, L. (2016). On the approximation error of mean-field models. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science. ACM, Antibes Juan-les-Pins, France, 285–297. URL http://dx.doi.org/10.1145/2964791.2901463.

[66]    Ying, L. (2016). On the rate of convergence of the power-of-two-choices to its mean-field limit. URL http://arxiv.org/abs/1605.06581.

[67]    Zhang, B., van Leeuwaarden, J. and Zwart, B. (2012). Staffing call centers with impatient customers: refinements to many-server asymptotics. Operations Research, 60 461–474. URL http://dx.doi.org/10.1287/opre.1110.1016.

[68]    Zhang, J. and Zwart, B. (2008). Steady state approximations of limited processor sharing queues in heavy traffic. Queueing Systems: Theory and Applications, 60 227–246. URL http://dx.doi.org/10.1007/s11134-008-9095-4.




Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238