Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-25T16:08:25.872Z Has data issue: false hasContentIssue false
  • English
  • Français

On the ergodicity of a class of level-dependent quasi-birth-and-death processes

Part of: Markov processes Ergodic theory

Published online by Cambridge University Press:  15 November 2019

James D. Cordeiro ,
Jeffrey P. Kharoufeh  and
Mark E. Oxley
James D. Cordeiro*
Affiliation:
University of Dayton
Jeffrey P. Kharoufeh*
Affiliation:
Clemson University
Mark E. Oxley*
Affiliation:
Air Force Institute of Technology
*
*Postal address: Department of Mathematics, University of Dayton, Dayton, OH, USA.
**Postal address: Department of Industrial Engineering, Clemson University, Clemson, SC, USA.
***Postal address: Department of Mathematics and Statistics, Air Force Institute of Technology, Wright-Patterson AFB, OH, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We examine necessary and sufficient conditions for recurrence and positive recurrence of a class of irreducible, level-dependent quasi-birth-and-death (LDQBD) processes with a block tridiagonal structure that exhibits asymptotic convergence in the rows as the level tends to infinity. These conditions are obtained by exploiting a multi-dimensional Lyapunov drift approach, along with the theory of generalized Markov group inverses. Additionally, we highlight analogies to well-known average drift results for level-independent quasi-birth-and-death (QBD) processes.

Keywords

LDQBD processpositive recurrenceLyapunov potential

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 37A30: Ergodic theorems, spectral theory, Markov operators
Type
Original Article
Information
Advances in Applied Probability , Volume 51 , Issue 4 , December 2019 , pp. 1109 - 1128
Copyright
© Applied Probability Trust 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alfa, A. (2006). Discrete-time analysis of GI/G/1 system with Bernoulli retrials: an algorithmic approach. Ann. Operat. Res. 141, 51–66.CrossRefGoogle Scholar
Anisimov, V. and Artalejo, J. (2002). Approximation of multiserver retrial queues by means of generalized truncated models. TOP 10, 51–66.CrossRefGoogle Scholar
Artalejo, J. and Chakravarthy, S. (2006). Algorithmic analysis of the MAP/PH/1 retrial queue. TOP 14, 293–332.CrossRefGoogle Scholar
Artalejo, J., Krishnamoorthy, A. and Lopez-Herrero, M. (2006). Numerical analysis of (s,S) inventory systems with repeated attempts. Ann. Operat. Res. 141, 67–83.CrossRefGoogle Scholar
Avram, F. and Gwmez-Corral, A. (2006). On bulk-service MAP/PHL,N/1/N G-queues with repeated attempts. Ann. Operat. Res. 141, 109–137.CrossRefGoogle Scholar
Baumann, H., Dayar, T., Orhan, M. C. and Sandmann, W. (2013). On the numerical solution of Kronecker-based infinite level-dependent QBD processes. Performance Evaluation 70, 663–681.CrossRefGoogle Scholar
Breuer, L., Dudin, A. and Klimenok, V. (2002). A retrial BMAP/PH/N system. Queueing Systems 40, 433–457.CrossRefGoogle Scholar
Bright, L. and Taylor, P. (1995). Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes. Commun. Statist. Stoch. Models 11, 497–525.CrossRefGoogle Scholar
Ciardo, G. and Smirni, E. (1999). ETAQA: an efficient technique for the analysis of QBD-processes by aggregation. Performance Evaluation 36, 71–93.CrossRefGoogle Scholar
Dayar, T., Sandmann, W., Spieler, D. and Wolf, V. (2011). Infinite level-dependent QBD processes and matrix-analytic solutions for stochastic chemical kinetics. Adv. Appl. Prob. 43 (4), 1005–1026.CrossRefGoogle Scholar
Dudin, A. and Klimenok, V. (1999). BMAP/SM/1 model with Markov modulated retrials. TOP 7, 267–278.CrossRefGoogle Scholar
Dudin, A. and Klimenok, V. (1999). Multi-dimensional quasitoeplitz Markov chains. J. Appl. Math. Stoch. Anal. 12, 393–415.CrossRefGoogle Scholar
Dudin, A. and Klimenok, V. (2000). A retrial BMAP/SM/1 system with linear repeated requests. Queueing Systems 34, 47–66.CrossRefGoogle Scholar
Eisen, M. and Tainiter, M. (1963). Stochastic variations in queuing processes. Operat. Res. 11, 922–927.CrossRefGoogle Scholar
Fayolle, G., Malyshev, V. and Menshikov, M. (1992). Random walks in a quarter plane with zero drifts, I: Ergodicity and null recurrence. Ann. Inst. H. Poincaré Prob. Statist. 28, 179–194.Google Scholar
Fayolle, G., Malyshev, V. and Menshikov, M. (1995). Topics in the Constructive Theory of Countable Markov Chains. Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Foster, F. G. (1953). On the stochastic matrices associated with certain queuing processes. Ann. Math. Statist. 24, pp. 355–360.CrossRefGoogle Scholar
Gordan, P. (1873). Über die auflösung linearer Gleichungen mit reelen Coefficienten [On the solution of linear inequalities with real coefficients]. Math. Ann. 6, 23–28.CrossRefGoogle Scholar
Kaplan, M. (1979). A sufficient condition of nonergodicity of a Markov chain. IEEE Trans. Inform. Theory 25, 470–471.CrossRefGoogle Scholar
Kim, C. S., Klimenok, V., Mushko, V. and Dudin, A. (2010). The BMAP/PH/N retrial queueing system operating in Markovian random environment. Comput. Operat. Res. 37, 1228–1237.CrossRefGoogle Scholar
Klimenok, V. and Dudin, A. (2006). Multi-dimensional asymptotically quasi-Toeplitz Markov chains and their application in queueing theory. Queueing Systems 54, 245–259.CrossRefGoogle Scholar
Koukoutsidis, I., Altman, E. and Kelif, J. M. (2005). A non-homogeneous QBD approach for the admission and GoS control in a multiservice WCDMA system. In Proceedings of IWQoS 2005 (Lecture Notes Comput. Sci. 3552), pp. 327–340. IFIP International Federation for Information Processing, INRIA.CrossRefGoogle Scholar
Kumar, B., Rukmani, R. and Thangaraj, V. (2009). An M/M/c retrial queueing system with Bernoulli vacations. J. Systems Sci. Systems Engineering 18, 222–242.CrossRefGoogle Scholar
Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling. Society for Industrial and Applied Mathematics, Philadelphia, PA.CrossRefGoogle Scholar
Latouche, G. and Taylor, P. G. (2003). Drift conditions for matrix-analytic models. Math. Operat. Res. 28, 346–360.CrossRefGoogle Scholar
Li, Q., Ying, Y. and Zhao, Y. (2006). A BMAP/G/1 retrial queue with server subject to breakdowns and repairs. Ann. Operat. Res. 141, 233–270.CrossRefGoogle Scholar
Malyshev, V. (1993). Networks and dynamical systems. Adv. Appl. Prob. 25, 140–175.CrossRefGoogle Scholar
Mangasarian, O. (1994). Nonlinear Programming. Society for Industrial and Applied Mathematics, Philadelphia, PA.CrossRefGoogle Scholar
Marlin, P. G. (1973). On the ergodic theory of Markov chains. Operat. Res. 21, 617–622.CrossRefGoogle Scholar
Mertens, J.-F., Samuel-Cahn, E. and Zamir, S. (1978). Necessary and sufficient conditions for recurrence and transience of Markov chains, in terms of inequalities. J. Appl. Prob. 15, 848–851.CrossRefGoogle Scholar
Meyer, C. D. (1975). The role of the group generalized inverse in the theory of finite Markov chains. SIAM Rev. 17, 443–464.CrossRefGoogle Scholar
Montoro Cazorla, D. and Perez-Ocon, R. (2008). An LDQBD process under degradation, inspection, and two types of repair. Europ. J. Operat. Res. 190, 494–508.CrossRefGoogle Scholar
Mushko, V., Jacob, M., Ramakrishnan, K., Krishnanmoorthy, A. and Dudin, A. (2006). Multiserver queue with addressed retrials. Ann. Operat. Res. 141, 283–301.CrossRefGoogle Scholar
Neuts, M. F. (1971). A queue subject to extraneous phase changes. Adv. Appl. Prob. 3, 78–119.CrossRefGoogle Scholar
Neuts, M. F. (1978). Further results on the M/M/1 queue with randomly varying rates. OPSEARCH 15, 158–168.Google Scholar
Neuts, M. F. (1978). The M/M/1 queue with randomly varying arrival and service rates. OPSEARCH 15, 139–157.Google Scholar
Neuts, M. F. (1979). A versatile Markovian point process. J. Appl. Prob. 16, 764–779.CrossRefGoogle Scholar
Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach (Dover Books on Advanced Mathematics). Dover Publications, New York.Google Scholar
Pakes, A. G. (1969). Some conditions for ergodicity and recurrence of Markov chains. Operat. Res. 17, 1058–1061.CrossRefGoogle Scholar
Purdue, P. (1974). The M/M/1 queue in a Markovian environment. Operat. Res. 22, 562–569.CrossRefGoogle Scholar
Rao, C. R. and Mitra, S. K. (1972). Generalized inverse of a matrix and its applications. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1: Theory of Statistics, pp. 601–620. University of California Press, Berkeley, CA.Google Scholar
Rosberg, Z. (1980). A positive recurrence criterion associated with multidimensional queueing processes. J. Appl. Prob. 17, 790–801.CrossRefGoogle Scholar
Rosberg, Z. (1981). A note on the ergodicity of Markov chains. J. Appl. Prob. 18, 112–121.CrossRefGoogle Scholar
Sennott, L. I. (1985). Tests for the nonergodicity of multidimensional Markov chains. Operat. Res. 33, 161–167.CrossRefGoogle Scholar
Sennott, L. I., Humblet, P. A. and Tweedie, R. L. (1983). Mean drifts and the non-ergodicity of Markov chains. Operat. Res. 31, 783–788.CrossRefGoogle Scholar
Shin, Y. (2007). Multi-server retrial queue with negative customers and disasters. Queueing Systems 55, 223–237.CrossRefGoogle Scholar
Szpankowski, W. (1984). Ergodicity aspects of multidimensional Markov chains with application to computer communication system analysis. In Modelling and Performance Evaluation Methodology (Lecture Notes Control Inform. Sci. 60), eds. Baccelli, F. and Fayolle, G., pp. 297–319. Springer, Berlin.Google Scholar
Tweedie, R. L. (1975). Sufficient conditions for ergodicity and recurrence of Markov chains on a general state space. Stoch. Process. Appl. 3, 385–403.CrossRefGoogle Scholar
Tweedie, R. L. (1976). Criteria for classifying general Markov chains. Adv. Appl. Prob. 8, 737–771.CrossRefGoogle Scholar
Yechiali, U. and Naor, P. (1971). Queuing problems with heterogeneous arrivals and service. Operat. Res. 19, 722–734.CrossRefGoogle Scholar