Explicit criteria for several types of ergodicity of the embedded M/G/1 and GI/M/\(n\) queues. (English) Zbl 1065.60134

Summary: This paper investigates the rate of convergence to the probability distribution of the embedded M/G/\(1\) and GI/M/\(n\) queues. We introduce several types of ergodicity including \(l\)-ergodicity, geometric ergodicity, uniformly polynomial ergodicity and strong ergodicity. The usual method to prove ergodicity of a Markov chain is to check the existence of a Foster-Lyapunov function or a drift condition, while here we analyse the generating function of the first return probability directly and obtain practical criteria. Moreover, the method can be extended to M/G/\(1\)- and GI/M/\(1\)-type Markov chains.


60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
Full Text: DOI


[1] Chen, M. F. (1992). From Markov Chains to Nonequilibrium Particle Systems . World Scientific, Singapore. · Zbl 0753.60055
[2] Foster, F. G. (1953). On the stochastic matrices associated with certain queuing processes. Ann. Math. Statist. 24, 355–360. · Zbl 0051.10601 · doi:10.1214/aoms/1177728976
[3] Gail, H. R., Hantler, S. L. and Taylor, B. A. (1996). Spectral analysis of M/G/1 and G/M/1 type Markov chains. Adv. Appl. Prob. 28, 114–165. · Zbl 0845.60092 · doi:10.2307/1427915
[4] Hou, Z. T. and Guo, Q. F. (1988). Homogeneous Denumerable Markov Processes . Springer, New York. · Zbl 0662.60002
[5] Kemeny, J. G., Snell, J. L. and Knapp, A. W. (1976). Denumerable Markov Chains (Graduate Texts Math. 40 ), 2nd edn. Springer, New York. · Zbl 0348.60090
[6] Kendall, D. G. (1951). Some problems in the theory of queues. J. R. Statist. Soc. B 13, 151–185. · Zbl 0045.07801
[7] Kendall, D. G. (1953). Stochastic processes occurring in the theory of queues and their analysis by the method of imbedded Markov chains. Ann. Math. Statist. 24, 338–354. · Zbl 0051.10505 · doi:10.1214/aoms/1177728975
[8] Mao, Y. H. (2003). Algebraic Convergence for discrete-time ergodic Markov chains. Sci. China Ser. A 46, 621–630. · Zbl 1084.60534 · doi:10.1360/02ys0202
[9] Markushevich, A. I. (1977). Theory of Functions of a Complex Variable , 2nd edn. Chelsea, New York. · Zbl 0357.30002
[10] Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability . Springer, London. · Zbl 0925.60001
[11] Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models (Johns Hopkins Ser. Math. Sci. 2 ). Johns Hopkins University Press, Baltimore, MD. · Zbl 0469.60002
[12] Neuts, M. F. (1989). Structured Stochastic Matrices of M/G/\(1\) Type and Their Applications (Prob. Pure Appl. 5 ). Marcel Dekker, New York. · Zbl 0695.60088
[13] Neuts, M. F. and Teugels, J. L. (1969). Exponential ergodicity of the M/G/1 queue. SIAM J. Appl. Math. 17, 921–929. · Zbl 0183.49303 · doi:10.1137/0117081
[14] Tuominen, P. and Tweedie, R. L. (1979). Exponential ergodicity in Markovian queueing and dam models. J. Appl. Prob . 16, 867–880. · Zbl 0422.60074 · doi:10.2307/3213152
[15] Tuominen, P. and Tweedie, R. L. (1994). Subgeometric rates of convergence of \(f\)-ergodic Markov chains. Adv. Appl. Prob. 26, 775–798. · Zbl 0803.60061 · doi:10.2307/1427820
[16] Tweedie, R. L. (1983). Criteria for rates of convergence of Markov chains with application to queueing and storage theory. In Probability, Statistics and Analysis (London Math. Soc. Lecture Note Ser. 79 ), eds J. F. C. Kingman and G. E. H. Reuter, Cambridge University Press, pp. 260–276. · Zbl 0501.60072
[17] Widder, D. V. (1946). The Laplace Transform . Princeton University Press. · Zbl 0060.24801
[18] Zhang, H. J., Lin, X. and Hou, Z. T. (2000). Polynomial uniform convergence for standard transition functions. Chinese Ann. Math. A 21, 351–356. · Zbl 0966.60032
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.