zbMATH — the first resource for mathematics

Perturbation analysis for denumerable Markov chains with application to queueing models. (English) Zbl 1062.60066
Summary: We study the parametric perturbation of Markov chains with denumerable state spaces. We consider both regular and singular perturbations. By the latter we mean that transition probabilities of a Markov chain, with several ergodic classes, are perturbed such that (rare) transitions among the different ergodic classes of the unperturbed chain are allowed. Singularly perturbed Markov chains have been studied in the literature under more restrictive assumptions such as strong recurrence ergodicity or Doeblin conditions. We relax these conditions so that our results can be applied to queueing models (where the conditions mentioned above typically fail to hold). Assuming \(\nu\)-geometric ergodicity, we are able to explicitly express the steady-state distribution of the perturbed Markov chain as a Taylor series in the perturbation parameter. We apply our results to quasi-birth-and-death processes and queueing models.

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J22 Computational methods in Markov chains
60J27 Continuous-time Markov processes on discrete state spaces
60K25 Queueing theory (aspects of probability theory)
Full Text: DOI
[1] Altman, E., Artiges, D. and Traore, K. (1999). On the integration of best-effort and guaranteed performance services. Europ. Trans. Telecommun. 10, 125–134.
[2] Anisimov, V. V. (2001). Asymptotic analysis of some type optimal maintenance policies in multicomponent systems with Markov switches. In Proc. 10th Internat. Symp. Appl. Stoch. Models Data Anal. (Compiegne, June 2001), pp. 112–117. Available at http://www.hds.utc.fr/asmda2001/.
[3] Avrachenkov, K. E. (1999). Analytic perturbation theory and its applications. Doctoral Thesis, University of South Australia. Available at http://www-sop.inria.fr/mistral/personnel/K.Avrachenkov/moi.html Avrachenkov, K. E., Filar, J. A. and Haviv, M. (2002). Singular perturbations of Markov chains and decision processes. In Handbook of Markov Decision Processes: Methods and Applications , eds E. A. Feinberg and A. Shwartz, Kluwer, Boston, MA, pp. 113–150. · Zbl 1014.90108
[4] Bielecki, T. R. and Stettner, L. (1998). Ergodic control of singularly perturbed Markov process in discrete time with general state and compact action spaces. Appl. Math. Optimization 38, 261–281. · Zbl 0916.60058 · doi:10.1007/s002459900091
[5] Cao, X.-R. and Chen, H.-F. (1997). Perturbation realization, potentials, and sensitivity analysis of Markov processes. IEEE Trans. Automatic Control 42, 1382–1393. · Zbl 0889.93039 · doi:10.1109/9.633827
[6] Chang, C.-S. and Nelson, R. (1993). Perturbation analysis of the M/M/1 queue in a Markovian environment via the matrix-geometric method. Commun. Statist. Stoch. Models 9, 233–246. · Zbl 0771.60075 · doi:10.1080/15326349308807264
[7] Courtois, P. J. (1977). Decomposability: Queueing and Computer System Applications. Academic Press, New York. · Zbl 0368.68004
[8] Dekker, R., Hordijk, A. and Spieksma, F. M. (1994). On the relation between recurrence and ergodicity properties in denumerable Markov decision chains. Math. Operat. Res. 19, 539–559. · Zbl 0843.90127 · doi:10.1287/moor.19.3.539
[9] Delebecque, F. (1983). A reduction process for perturbed Markov chains. SIAM J. Appl. Math. 43, 325–350. · Zbl 0518.60080 · doi:10.1137/0143023
[10] Gelenbe, E. and Rosenberg, C. (1990). Queues with slowly varying arrival and service processes. Management Sci. 36, 928–937. · Zbl 0713.60105 · doi:10.1287/mnsc.36.8.928
[11] Glasserman, P. (1991). Gradient Estimation via Perturbation Analysis . Kluwer, Boston, MA. · Zbl 0746.90024
[12] Heidergott, B. and Cao, X.-R. (2002). A note on the relation between weak derivatives and perturbation realization. IEEE Trans. Automatic Control 47, 1112–1115. · Zbl 1364.60092 · doi:10.1109/TAC.2002.800648
[13] Heidergott, B., Hordijk, A. and Weisshaupt, H. (2002). Measure-valued differentiation for stationary Markov chains. Res. Rep. 2002–27, EURANDOM. Available at http://staff.feweb.vu.nl/bheidergott/. · Zbl 1278.90428
[14] Kolmogorov, A. N. and Fomīn, S. V. (1975). Introductory Real Analysis . Dover, New York.
[15] Kontoyiannis, I. and Meyn, S. P. (2003). Spectral theory and limit theory for geometrically ergodic Markov processes. Ann. Appl. Prob. 13, 304–362. · Zbl 1016.60066 · doi:10.1214/aoap/1042765670
[16] Koole, G. (1998). The deviation matrix of the M/M/\(1/\infty\) and M/M/\(1/N\) queue with applications to controlled queueing models. In Proc. IEEE CDC’98 (Tampa, FL), pp. 56–59. · Zbl 0917.90136 · doi:10.1023/A:1019177307418
[17] Korolyuk, V. S. and Turbin, A. F. (1993). Mathematical Foundations of The State Lumping of Large Systems . Kluwer, Dordrecht. · Zbl 0834.60001
[18] Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling . SIAM, Philadelphia, PA. · Zbl 0922.60001 · doi:10.1137/1.9780898719734
[19] Latouche, G. and Schweitzer, P. G. (1995). A Markov modulated, nearly completely decomposable M/M/1 queue. In Computations with Markov chains , ed. W. J. Stewart, Kluwer, Boston, MA. · Zbl 0862.60086
[20] Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability . Springer, London. · Zbl 0925.60001
[21] Meyn, S. P. and Tweedie, R. L. (1994). Computable bounds for geometric convergence rates of Markov chains. Ann. Appl. Prob. 4, 981–1012. JSTOR: · Zbl 0812.60059 · doi:10.1214/aoap/1177004900 · links.jstor.org
[22] Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach . Johns Hopkins University Press, Baltimore, MD. · Zbl 0469.60002
[23] Núñez-Queija, R. (1999). Processor-sharing models for integrated-services networks. Doctoral Thesis, Eindhoven University of Technology. Available at http://www.cwi.nl/\(\sim\)sindo/.
[24] Pervozvanski, A. A. and Gaitsgori, V. G. (1988). Theory of Suboptimal Decisions . Kluwer, Dordrecht. Russian original: Decomposition, Aggregation and Approximate Optimization , Nauka, Moscow, 1979. · Zbl 0691.90075
[25] Pflug, G. (1992). Gradient estimates for the performance of Markov chains and discrete event processes. Ann. Operat. Res. 39, 173–194. · Zbl 0766.60088 · doi:10.1007/BF02060941
[26] Spieksma, F. M. (1990). Geometrically ergodic Markov chains and the optimal control of queues. Doctoral Thesis, Leiden University.
[27] Spieksma, F. M. and Tweedie, R. L. (1994). Strengthening ergodicity to geometric ergodicity for Markov chains. Commun. Statist. Stoch. Models 10, 45–74. · Zbl 0797.60053 · doi:10.1080/15326349408807288
[28] Yin, G. and Zhang, H. (2002). Countable-state-space Markov chains with two time scales and applications to queueing systems. Adv. Appl. Prob. 34, 662–688. · Zbl 1020.60065 · doi:10.1239/aap/1033662170
[29] Yin, G. and Zhang, Q. (1998). Continuous-Time Markov Chains and Applications. A Singular Perturbation Approach (Appl. Math. 37 ). Springer, New York. · Zbl 0896.60039
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.