Diffusion models and steady-state approximations for exponentially ergodic Markovian queues. (English) Zbl 1333.60194

Author’s abstract: Motivated by queues with many servers, we study Brownian steady-state approximations for continuous time Markov chains (CTMCs). Our approximations are based on diffusion models (rather than a diffusion limit) whose steady-state, we prove, approximates that of the Markov chain with notable precision. Strong approximations provide such “limitless” approximations for process dynamics. Our focus here is on steady-state distributions, and the diffusion model that we propose is tractable relative to strong approximations. {
} Within an asymptotic framework, in which a scale parameter \(n\) is taken large, a uniform (in the scale parameter) Lyapunov condition imposed on the sequence of diffusion models guarantees that the gap between the steady-state moments of the diffusion and those of the properly centered and scaled CTMCs shrinks at a rate of \(\sqrt{n}\). {
} Our proofs build on gradient estimates for solutions of the Poisson equations associated with the (sequence of) diffusion models and on elementary martingale arguments. As a by-product of our analysis, we explore connections between Lyapunov functions for the fluid model, the diffusion model and the CTMC.
Reviewer’s comment: In my opinion, it is a high-level paper with sound mathematics and applicable in practical problems.


60K25 Queueing theory (aspects of probability theory)
60J60 Diffusion processes
60F17 Functional limit theorems; invariance principles
90B22 Queues and service in operations research
90B36 Stochastic scheduling theory in operations research
90B20 Traffic problems in operations research
49L20 Dynamic programming in optimal control and differential games
Full Text: DOI arXiv Euclid


[1] Ata, B. and Gurvich, I. (2012). On optimality gaps in the Halfin-Whitt regime. Ann. Appl. Probab. 22 407-455. · Zbl 1236.60087
[2] Baxendale, P. H. (2005). Renewal theory and computable convergence rates for geometrically ergodic Markov chains. Ann. Appl. Probab. 15 700-738. · Zbl 1070.60061
[3] Borkar, V. and Budhiraja, A. (2004/05). Ergodic control for constrained diffusions: Characterization using HJB equations. SIAM J. Control Optim. 43 1467-1492. · Zbl 1101.93082
[4] Brémaud, P. (1981). Point Processes and Queues : Martingale Dynamics . Springer, New York.
[5] Budhiraja, A. and Lee, C. (2007). Long time asymptotics for constrained diffusions in polyhedral domains. Stochastic Process. Appl. 117 1014-1036. · Zbl 1119.60066
[6] Budhiraja, A. and Lee, C. (2009). Stationary distribution convergence for generalized Jackson networks in heavy traffic. Math. Oper. Res. 34 45-56. · Zbl 1214.60013
[7] Dai, J., Dieker, A. and Gao, X. (2012). Validity of heavy-traffic steady-state approximations in many-server queues with abandonment. Unpublished manuscript. · Zbl 1310.60127
[8] Dai, J. G., He, S. and Tezcan, T. (2010). Many-server diffusion limits for \(G/Ph/n+GI\) queues. Ann. Appl. Probab. 20 1854-1890. · Zbl 1202.90085
[9] Dieker, A. B. and Gao, X. (2013). Positive recurrence of piecewise Ornstein-Uhlenbeck processes and common quadratic Lyapunov functions. Ann. Appl. Probab. 23 1291-1317. · Zbl 1273.60108
[10] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes : Characterization and Convergence . Wiley, New York. · Zbl 0592.60049
[11] Galtchouk, L. and Pergamenchtchikov, S. (2012). Geometric ergodicity for families of homogeneous Markov chains. Available at . 1002.2341
[12] Gamarnik, D. and Zeevi, A. (2006). Validity of heavy traffic steady-state approximation in generalized Jackson networks. Ann. Appl. Probab. 16 56-90. · Zbl 1094.60052
[13] Gilbarg, D. and Trudinger, N. S. (2001). Elliptic Partial Differential Equations of Second Order . Springer, Berlin. · Zbl 1042.35002
[14] 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. Inst. Math. Stat. Collect. 4 195-214. IMS, Beachwood, OH. · Zbl 1170.68389
[15] Gurvich, I., Huang, J. and Mandelbaum, A. (2014). Excursion-based universal approximations for the Erlang-A queue in steady-state. Math. Oper. Res. 39 325-373. · Zbl 1322.60192
[16] Horn, R. A. and Johnson, C. R. (1994). Matrix Analysis . Cambridge Univ. Press, Cambridge. · Zbl 0801.15001
[17] Karatzas, I. and Shreve, S. E. (1991). Brownian Motion and Stochastic Calculus , 2nd ed. Graduate Texts in Mathematics 113 . Springer, New York. · Zbl 0734.60060
[18] Khasminskii, R. (2012). Stochastic Stability of Differential Equations , 2nd ed. Stochastic Modelling and Applied Probability 66 . Springer, Heidelberg. · Zbl 1259.60058
[19] Klebaner, F. C. (2005). Introduction to Stochastic Calculus with Applications , 2nd ed. Imperial College Press, London. · Zbl 1077.60001
[20] Meyn, S. P. and Tweedie, R. L. (1993). Stability of Markovian processes. III. Foster-Lyapunov criteria for continuous-time processes. Adv. in Appl. Probab. 25 518-548. · Zbl 0781.60053
[21] Pardoux, E. and Veretennikov, A. Y. (2001). On the Poisson equation and diffusion approximation. I. Ann. Probab. 29 1061-1085. · Zbl 1029.60053
[22] Qian, Z. and Zheng, W. (2004). A representation formula for transition probability densities of diffusions and applications. Stochastic Process. Appl. 111 57-76. · Zbl 1070.60072
[23] Robert, P. (2003). Stochastic Networks and Queues , French ed. Applications of Mathematics ( New York ) 52 . Springer, Berlin. · Zbl 1038.60091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.