Informatics and Applications

2014, Volume 8, Issue 1, pp 106-117

GENERAL BOUNDS FOR NONSTATIONARY CONTINUOUS-TIME MARKOV CHAINS

A.I. Zeifman
V.Yu. Korolev
A.V. Korotysheva
S.Ya. Shorgin

Abstract

A general approach for obtaining perturbation bounds of nonstationary continuous-time Markov chains is considered. The suggested approach deals with a special weighted norms related to total variation. The method is based on the notion of a logarithmic norm of a linear operator function and respective bounds for the Cauchy operator of a differential equation. Special transformations of the reduced intensity matrix of the process are applied. The statements are proved which provide estimates of perturbation of probability characteristics for the case of absence of ergodicity in uniform operator topology. Birth–death–catastrophe queueing models and queueing systems with batch arrivals and group services are also considered in the paper. Some classes of such systems are studied, and bounds of perturbations are obtained. Particularly, such bounds are given for the Mt/Mt/S queueing system with possible catastrophes and a simplemodel of a queueing system with batch arrivals and group services is analyzed. Moreover, approximations of limiting characteristics are considered for the queueing model.

[+] References (49)

Stoyan, D. 1977. Qualitative Eigenschaften und Absch.atzungen stochastischer Modelle. Berlin: Akademie-Verlag. 198 p.
Zolotarev, V.M. 1978. Quantitative estimates for the continuity property of queueing systems of typeG/G/..Theory Probab. Appl. 22(4):679–691. doi: 10.1137/1122083.
Kalashnikov, V. V. 1978. Kachestvennyy analiz slozhnykh sistem metodom probnykh funktsiy [Qualitative analysis of complex systems behavior by test functions method]. Moscow: Nauka. 248 p.
Kalashnikov, V. V., and V.M. Zolotarev, eds. 1983. Stability problems for stochastic models. Lecture notes in mathematics. N.Y.: Springer Verlag. Vol. 983. 295 p.
Kalashnikov, V. V., V. Penkov, and V.M. Zolotarev, eds. 1987. Stability problems for stochastic models. Lecture notes in mathematics. N.Y.: Springer Verlag. Vol. 1233. 224 p.
Kalashnikov, V. V., and V.M. Zolotarev, eds. 1989. Stability problems for stochastic models. Lecture notes in mathematics. N.Y.: Springer Verlag. Vol. 1412. 380 p.
Zolotarev, V.M., V.M. Kruglov, and V. Yu. Korolev, eds. 1994. Stability problems for stochastic models. 15th Perm Seminar Proceedings. Perm, Russia. 312 p.
Kalashnikov, V. V., and V.M. Zolotarev, eds. 1993. Stability problems for stochastic models. Lecture notes in mathematics. N.Y.: Springer Verlag. Vol. 1546. 229 p.
Gnedenko, B. V., and V. Yu. Korolev. 1996. Random summation: Limit theorems and applications. Boca Raton: CRC Press. 267 p.
Kartashov, N. V. 1981. Sil’no ustoychivye tsepi Markova [Strong stable Markov chains]. Problemy ustoychivosti stokhasticheskikh modeley: Trudy seminara [“Stability Problems for Stochastic Models” Seminar Proceedings]. Moscow: VNIISI. 54–59.
Kartashov, N. V. 1986. Inequalities in theorems of ergodicity and stability for Markov chains with common phase space. I. Theory Probab. Appl. 30(2):247–259. doi: 10.1137/1122083.
Zeifman, A. I. 1985. Stability for contionuous-time nonhomogeneousMarkov chains. Lecture notes in mathematics. N.Y.: Springer Verlag. 1155:401–414.
Aldous, D. J., and J. Fill. Reversible Markov chains and random walks on graphs. Ch. 8. Available at: http://www.stat.berkeley.edu/users/aldous/RWG/ book.html (accessed December 25, 2013).
Diaconis, P., and D. Stroock. 1991. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1:36–61. doi: 10.1214/aoap/1177005980.
Mitrophanov, A.Yu. 2003. Stability and exponential convergence of continuous-time Markov chains. J. Appl. Probab. 40:970–979. doi: 10.1239/jap/1067436094.
Mitrophanov, A. Yu. 2004. The spectral gap and perturbation bounds for reversible continuous-time Markov chains. J. Appl. Probab. 41:1219–1222. doi: 10.1239/ jap/1101840568.
Mitrophanov, A. Yu. 2005. Ergodicity coefficient and perturbation bounds for continuous-time Markov chains. Math. Inequal. Appl. 8:159–168. doi: 10.7153/mia-08-15.
Mitrophanov, A. Yu. 2006. Stability estimates for finite homogeneous continuous-time Markov chains. Theory Probab. Appl. 50(2):319–326. doi: 10.1137/ S0040585X97981718.
Kartashov, N. V. 1996. Strong stable Markov chains. Utrecht, Kiev: VSP, TBiMC. 138 p.
Altman, E., K. Avrachenkov, and R. Nunez-Queija. 2004. Perturbation analysis for denumerableMarkov chainswith application to queueing models. Adv. Appl. Probab. 36: 839–853. doi: 10.1239/aap/1093962237.
Mouhoubi, Z., and D. Aissani. 2010. New perturbation bounds for denumerable Markov chains. Linear Algebra and Its Applications. 432:1627–1649. doi: 10.1016/j.laa.2009.11.020.
Ferre, D., L. Herve, and J. Ledoux. 2013. Regular perturbation of V-geometrically ergodicMarkov chains. J. Appl. Probab. 50:184–194. doi: 10.1239/jap/1363784432.
Meyn, S. P., and R. L. Tweedie. 1994. Computable bounds for geometric convergence rates of Markov chains. Ann. Appl. Probab. 4: 981–1012. doi:10.1214/ aoap/1177004900.
Yuanyuan, L. 2012. Perturbation bounds for the stationary distributions ofMarkov chains. SIAMJ.Matrix Anal. Appl. 33:1057–1074. doi: 10.1137/110838753.
Gnedenko, D.B. 1972. On a generalization of Erlang formulae. Zastosow. Mat. 12:239–242.
Gnedenko, B., and A. Soloviev. 1973. On the conditions of the existence of final probabilities for aMarkov process. Math. Oper. Stat. 4:379–390.
Massey, W.A., and W. Whitt. 1998. Uniform acceleration expansions for Markov chains with time-varying rates. Ann. Appl. Probab. 8:1130–1155. doi: 10.1214/ aoap/1028903375.
Gnedenko,B. V., and I. P. Makarov. 1971. Svoystva resheniy zadachi s poteryami v sluchae periodicheskikh intensivnostey [Properties of the solution to the loss problem for periodic rates]. Differentsial’nye Uravneniya [Differential Equations] 7:1696–1698.
Zeifman, A. I. 1991. Qualitative properties of inhomogeneous birth and death processes. J. Math. Sci. 57:3217– 3224. doi: 10.1007/BF01099019.
Zeifman, A. I. 1989. Properties of a system with losses in the case of variable rates. Autom. Rem. Contr. 50:82–87.
Zeifman, A. I. 1991. Some estimates of the rate of convergence for birth and death processes. J. Appl. Probab. 28:268–277.
Zeifman, A. I. 1995. Upper and lower bounds on the rate of convergence for nonhomogeneous birth and death processes. Stoch. Proc. Appl. 59:157–173. doi: 10.1016/0304- 4149(95)00028-6.
Granovsky, B. L., and A. I. Zeifman. 2004. Nonstationary queues: Estimation of the rate of convergence. Queueing Syst. 46:363–388. doi: 10.1023/B:QUES. 0000027991.19758.b4.
Zeifman, A. I., V. E. Bening, and I.A. Sokolov. 2008. Markovskie tsepi i modeli s nepreryvnym vremenem [Continuous-time Markov chains and models]. Moscow: Elex-KM. 168 p.
Van Doorn, E.A., A. I. Zeifman, and T.L. Panfilova. 2010. Bounds and asymptotics for the rate of convergence of birth–death processes. Theory Probab. Appl. 54:97–113. doi: 10.1137/S0040585X97984097.
Zeifman, A. I., and D. Isaacson. 1994. On strong ergodicity for nonhomogeneous continuous-time Markov chains. Stoch. Proc. Appl. 50:263–273. doi: 10.1016/0304- 4149(94)90123-6.
Zeifman, A. I. 1998. Stability of birth and death processes. J. Math. Sci. 91:3023–3031. doi: 10.1007/BF02432876.
Zeifman, A. I., and A. Korotysheva. 2012. Perturbation bounds forMt/Mt/N queue with catastrophes. Stochastic models 28:49–62. doi: 10.1080/15326349.2011.614900.
Zeifman, A., V. Korolev, A. Korotysheva, Y. Satin, and V. Bening. 2014 (in press). Perturbation bounds and truncations for a class ofMarkovian queues. Queueing Syst.
Zeifman, A. I., S. Leorato, E. Orsingher, Y. Satin, and G. Shilova. 2006. Some universal limits for nonhomogeneous birth and death processes. Queueing Syst. 52:139– 151. doi: 10.1007/s11134-006-4353-9.
Daleckij, Ju, L. and M.G. Krein. 1974. Stability of solutions of differential equations in Banach space. Am.Math. Soc. Transl. 43. 386 p.
Zeifman, A. I., Ya. Satin, and T. Panfilova. 2013. Limiting characteristics for finite birth–death–catastrophe processes. Math. Biosci. 245:96–102. doi: 10.1016/ j.mbs.2013.02.009.
Thorne, J. L., H. Kishino, and J. Felsenstein. 1991. An evolutionary model for maximum-likelihood alignment of DNA sequences. J. Mol. Evol. 33:114–124. doi: 10.1007/ BF02193625.
Mitrophanov, A. Yu., and M. Borodovsky. 2007. Convergence rate estimation for the TKF91 model of biological sequence length evolution. Math. Biosci. 209:470–485. doi: 10.1016/j.mbs.2007.02.011.
Satin, Ya.A., A. I. Zeifman, A. V. Korotysheva, and S. Ya. Shorgin. 2011. Ob odnom klasse markovskikh sistem obsluzhivaniya [On a class of Markovian queues]. Informatika i ee Primeneniya — Inform. Appl. 5(4):18–24.
Satin, Ya.A., A. I. Zeifman, A. V. Korotysheva. 2013. On the rate of convergence and truncations for a class of Markovian queueing systems. Theory Probab. Appl. 57:529–539. doi: 10.1137/S0040585X97986151.
Zeifman, A. I., A. Korotysheva, Ya. Satin, G. Shilova, and T. Panfilova. 2013. On a queueing model with group services. Lecture notes in communications in computer and information science. 356:198–205. doi: 10.1007/978-3- 642-35980-4 22.
Zeifman, A. I., Y. Satin, G. Shilova, V. Korolev, V. Bening, and S. Shorgin. 2013. OnMt/Mt/S type queue with group services. ECMS 2013: 27th Conference (European) on Modeling and Simulation Proceedings. Alesund, Norway. 604–609. doi: 10.7148/2013-0604.
Zeifman, A. I., A. V. Korotysheva, Ya.A. Satin, and S. Ya. Shorgin. 2012. Otsenki v nul’-ergodicheskom sluchae dlya nekotorykh sistem obsluzhivaniya [Bounds in null ergodic case for some queueing systems]. Informatika i ee Primeneniya — Inform. Appl. 6(4):27–33.

[+] About this article