zbMATH — the first resource for mathematics

A unified perturbation analysis framework for countable Markov chains. (English) Zbl 1370.60118
Summary: In this paper, we are devoted to singular perturbation analysis for discrete-time or continuous-time Markov chains. We modify and extend the drift condition method, well known for regular perturbation, to develop a new framework for singular perturbation analysis. Our results extend and improve the corresponding ones in [E. Altman et al., Adv. Appl. Probab. 36, No. 3, 839–853 (2004; Zbl 1062.60066)] for singularly perturbed Markov chains by allowing a general perturbation form, less restrictive conditions, and more computable bounds. Our analysis covers the regular perturbation analysis, and hence unifies singular and regular perturbation analysis. Furthermore, our results are illustrated by two two-dimensional Markov chains, including a discrete-time queue and a continuous-time level dependent quasi-birth-death process.
Reviewer: Reviewer (Berlin)

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J27 Continuous-time Markov processes on discrete state spaces
60J22 Computational methods in Markov chains
60K25 Queueing theory (aspects of probability theory)
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
Full Text: DOI
[1] Abbas, K.; Berkhout, J.; Heidergott, B., A critical account of perturbation analysis of Markov chains, Markov Process. Related Fields, 22, 227-265, (2016) · Zbl 1359.60089
[2] Altman, E.; Avrachenkov, K. E.; Núñez-Queija, R., Perturbation analysis for denumerable Markov chains with application to queueing models, Adv. in Appl. Probab., 36, 839-853, (2004) · Zbl 1062.60066
[3] Bielecki, T. R.; Stettner, L., Ergodic control of singularly perturbed Markov process in discrete time with general state and compact action spaces, Appl. Math. Optim., 38, 261-281, (1998) · Zbl 0916.60058
[4] Chen, M. F., From Markov chains to non-equilibrium particle systems, (2003), World Scientific Singapore
[5] Coolen-Schrijner, P.; van Doorn, E. A., The deviation matrix of a continuous-time Markov chains, Probab. Engrg. Inform. Sci., 16, 351-366, (2002) · Zbl 1011.60057
[6] Delebecque, F., A reduction process for perturbed Markov chains, SIAM J. Appl. Math., 43, 2, 325-350, (1983) · Zbl 0518.60080
[7] Delebecque, F.; Quadrat, J., Optimal control of Markov chains admitting strong and weak interactions, Automatica, 17, 2, 281-296, (1981) · Zbl 0467.49020
[8] Heidergott, B.; Hordijk, A.; Leder, N., Series expansions for continuous-time Markov processes, Oper. Res., 58, 756-767, (2010) · Zbl 1228.90145
[9] Heidergott, B.; Hordijk, A.; van Uitert, M., Series expansions for finite-state Markov chains, Probab. Engrg. Inform. Sci., 21, 381-400, (2007) · Zbl 1124.60056
[10] Hou, Z.; Liu, Y., Explicit criteria for several types of ergodicity of the embedded M/G/1 and GI/M/n queues, J. Appl. Probab., 41, 778-790, (2004) · Zbl 1065.60134
[11] Kartashov, N. V., Strongly stable Markov chains, J. Sov. Math., 34, 1493-1498, (1986) · Zbl 0594.60069
[12] Kartashov, N. V., Strong stable Markov chains, (1996), VSP/TBIMC Scientific Publishers Utrecht/Kiev, Edition · Zbl 0874.60082
[13] Kemeny, J. G.; Laurie, S. J.; Knapp, A. W., Denumerable Markov chains, (1976), Springer-Verlag New York, Heidelberg, Berlin, US · Zbl 0348.60090
[14] Khasminskii, R.; Yin, G.; Zhang, Q., Asymptotic expansions of singularly perturbed systems involving rapidly fluctuating Markov chains, SIAM J. Appl. Math., 56, 1, 277-293, (1996) · Zbl 0849.34047
[15] Korolyuk, V.; Turbin, A., Mathematical foundations of the state lumping of large systems, (1993), Kluwer Dordrecht
[16] Latouche, G.; Schweitzer, P. J., A Markov modulated, nearly completely decomposable M/M/1 queue, (Stewart, W. J., Computations with Markov Chains, (1995), Kluwer Academic Publishers Boston, MA), 39-48 · Zbl 0862.60086
[17] Li, H.; Zhao, Y. Q., Tail asymptotics for a generalized two demand queueing model - a kernel method, Queueing Syst., 69, 77-100, (2011) · Zbl 1235.60132
[18] Liu, Y., Perturbation bounds for the stationary distributions of Markov chains, SIAM J. Matrix Anal. Appl., 33, 4, 1057-1074, (2012) · Zbl 1264.60052
[19] Liu, Y., Perturbation analysis for continuous-time Markov chains, Sci. China Math., 58, 12, 2633-2642, (2015) · Zbl 1342.60128
[20] Liu, Y.; Hou, Z., Several types of ergodicity for M/G/1-type Markov chains and Markov processes, J. Appl. Probab., 43, 1, 141-158, (2006) · Zbl 1101.60052
[21] Liu, R.; Zhang, Q.; Yin, G., Nearly optimal control of singularly perturbed Markov decision processes in discrete time, Appl. Math. Optim., 44, 2, 105-129, (2001) · Zbl 0990.90125
[22] Meyn, S. P.; Tweedie, R. L., Markov chains and stochastic stability, (2009), Cambridge University Press · Zbl 0925.60001
[23] Mitrophanov, A. Y., Stability estimates for finite homogeneous continuous-time Markov chains, Theory Probab. Appl., 50, 319-326, (2006) · Zbl 1089.60045
[24] Miyazawa, M., Tail decay rates in double QBD processes and related reflected random walks, Math. Oper. Res., 34, 547-575, (2009) · Zbl 1213.60151
[25] Mouhoubi, Z.; Aissani, D., New perturbation bounds for denumerable Markov chains, Linear Algebra Appl., 432, 1627-1649, (2010) · Zbl 1190.60063
[26] Yang, H.; Yin, G.; Yin, K.; Zhang, Q., Control of singularly perturbed Markov chains: a numerical study, ANZIAM J., 49-74, (2003) · Zbl 1054.93055
[27] Yin, G.; Zhang, H., Singularly perturbed discrete-time Markov chains, SIAM J. Appl. Math., 61, 3, 834-854, (2000) · Zbl 0972.60068
[28] Yin, G.; Discrete-time, Zhang H., Markov chains with two-time scales and a countable state space: limit results and queueing applications, Stoch. Int. J. Probab. Stoch. Process., 80, 4, 339-369, (2008) · Zbl 1145.60322
[29] Tweedie, R. L., Perturbations of countable Markov chains and processes, Ann. Inst. Statist. Math., 32, 283-290, (1980) · Zbl 0452.60075
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.