On three methods for bounding the rate of convergence for some continuous-time Markov chains

Zeifman, Alexander ; Satin, Yacov ; Kryukova, Anastasia ; Razumchik, Rostislav ; Kiseleva, Ksenia ; Shilova, Galina

International Journal of Applied Mathematics and Computer Science, Tome 30 (2020) no. 2, pp. 251-266.

Résumé

Consideration is given to three different analytical methods for the computation of upper bounds for the rate of convergence to the limiting regime of one specific class of (in)homogeneous continuous-time Markov chains. This class is particularly well suited to describe evolutions of the total number of customers in (in)homogeneous M/M/S queueing systems with possibly state-dependent arrival and service intensities, batch arrivals and services. One of the methods is based on the logarithmic norm of a linear operator function; the other two rely on Lyapunov functions and differential inequalities, respectively. Less restrictive conditions (compared with those known from the literature) under which the methods are applicable are being formulated. Two numerical examples are given. It is also shown that, for homogeneous birth-death Markov processes defined on a finite state space with all transition rates being positive, all methods yield the same sharp upper bound.

Détail

Keywords: inhomogeneous continuous time Markov chains, weak ergodicity, Lyapunov function, differential inequalities, forward Kolmogorov system
Mots-clés : łańcuchy Markowa z czasem ciągłym, funkcja Lapunowa, nierówność różniczkowa, system Kołmogorowa

Bibliographie

[1] Almasi, B., Roszik, J. and Sztrik, J. (2005). Homogeneous finite-source retrial queues with server subject to breakdowns and repairs, Mathematical and Computer Modelling 42(5): 673–682.

[2] Brugno, A., D’Apice, C., Dudin, A. and Manzo, R. (2017). Analysis of an MAP/PH/1 queue with flexible group service, International Journal of Applied Mathematics and Computer Science 27(1): 119–131, DOI: 10.1515/amcs-2017-0009.

[3] Crescenzo, A.D., Giorno, V., Kumar, B.K. and Nobile, A. (2018). A time-non-homogeneous double-ended queue with failures and repairs and its continuous approximation, Mathematics 6(5): 81.

[4] Doorn, E. V., Zeifman, A. and Panfilova, T. (2010). Bounds and asymptotics for the rate of convergence of birth-death processes, Theory of Probability and Its Applications 54(1): 97–113.

[5] Giorno, V., Nobile, A.G. and Spina, S. (2014). On some time non-homogeneous queueing systems with catastrophes, Applied Mathematics and Computation 245: 220–234.

[6] Granovsky, B. and Zeifman, A. (2004). Nonstationary queues: Estimation of the rate of convergence, Queueing Systems 46(3–4): 363–388.

[7] Kalashnikov, V. (1971). Analysis of ergodicity of queueing systems by Lyapunov’s direct method, Automation and Remote Control 32(4): 559–566.

[8] Kartashov, N. (1985). Criteria for uniform ergodicity and strong stability of Markov chains with a common phase space, Theory of Probability and Mathematical Statistics 30: 71–89.

[9] Li, H., Zhao, Q. and Yang, Z. (2007). Reliability modeling of fault tolerant control systems, International Journal of Applied Mathematics and Computer Science 17(4): 491–504, DOI: 10.2478/v10006-007-0041-0.

[10] Li, J. and Zhang, L. (2017). MX/M/c queue with catastrophes and state-dependent control at idle time, Frontiers of Mathematics in China 12(6): 1427–1439.

[11] Liu, Y. (2012). Perturbation bounds for the stationary distributions of Markov chains, SIAM Journal on Matrix Analysis and Applications 33(4): 1057–1074.

[12] Malyshev, V. and Menshikov, M. (1982). Ergodicity, continuity and analyticity of countable Markov chains, Transactions of the Moscow Mathematical Society 1(148).

[13] Meyn, S. and Tweedie, R. (1993). Stability of Markovian processes. III: Foster–Lyapunov criteria for continuous time processes, Advances in Applied Probability 25(3):518–548.

[14] Meyn, S. and Tweedie, R. (2012). Markov Chains and Stochastic Stability, Springer Science Business Media, Berlin/Heidelberg/New York, NY.

[15] Mitrophanov, A. (2003). Stability and exponential convergence of continuous-time Markov chains, Journal of Applied Probability 40(4): 970–979.

[16] Mitrophanov, A. (2004). The spectral gap and perturbation bounds for reversible continuous-time Markov chains, Journal of Applied Probability 41(4): 1219–1222.

[17] Mitrophanov, A. (2018). Connection between the rate of convergence to stationarity and stability to perturbations for stochastic and deterministic systems, Proceedings of the 38th International Conference ‘Dynamics Days Europe’, DDE 2018, Loughborough, UK, pp. 3–7.

[18] Moiseev, A. and Nazarov, A. (2016). Queueing network MAP − (GI/∞)K with high-rate arrivals, European Journal of Operational Research 254(1): 161–168.

[19] Nelson, R., Towsley, D. and Tantawi, A. (1988). Performance analysis of parallel processing systems, IEEE Transactions on Software Engineering 14(4): 532–540.

[20] Olwal, T.O., Djouani, K., Kogeda, O.P. and van Wyk, B.J. (2012). Joint queue-perturbed and weakly coupled power control for wireless backbone networks, International Journal of Applied Mathematics and Computer Science 22(3): 749–764, DOI: 10.2478/v10006-012-0056-z.

[21] Rudolf, D. and Schweizer, N. (2018). Perturbation theory for Markov chains via Wasserstein distance, Bernoulli 24(4A): 2610–2639.

[22] Satin, Y., Zeifman, A. and Kryukova, A. (2019). On the rate of convergence and limiting characteristics for a nonstationary queueing model, Mathematics 7(678): 1–11.

[23] Schwarz, J., Selinka, G. and Stolletz, R. (2016). Performance analysis of time-dependent queueing systems: Survey and classification, Omega 63: 170–189.

[24] Trejo, K.K., Clempner, J.B. and Poznyak, A.S. (2019). Proximal constrained optimization approach with time penalization, Engineering Optimization 51(7): 1207–1228.

[25] Vvedenskaya, N., Logachov, A., Suhov, Y. and Yambartsev, A. (2018). A local large deviation principle for inhomogeneous birth-death processes, Problems of Information Transmission 54(3): 263–280.

[26] Wieczorek, R. (2010). Markov chain model of phytoplankton dynamics, International Journal of Applied Mathematics and Computer Science 20(4): 763–771, DOI: 10.2478/v10006-010-0058-7.

[27] Zeifman, A. (1985). Stability for continuous-time nonhomogeneous Markov chains, in V.V. Kalashnikov and V.M. Zolotarev (Eds), Stability Problems for Stochastic Models, Springer, Berlin/Heidelberg, pp. 401–414.

[28] Zeifman, A. (1989). Properties of a system with losses in the case of variable rates, Automation and Remote Control 50(1): 82–87.

[29] Zeifman, A., Kiseleva, K., Satin, Y., Kryukova, A. and Korolev, V. (2018a). On a method of bounding the rate of convergence for finite Markovian queues, 10th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), Moscow, Russia, pp. 1–5.

[30] Zeifman, A. and Korolev, V. (2014). On perturbation bounds for continuous-time Markov chains, Statistics Probability Letters 88: 66–72.

[31] Zeifman, A., Korolev, V., Satin, Y. and Kiseleva, K. (2018b). Lower bounds for the rate of convergence for continuous-time inhomogeneous Markov chains with a finite state space, Statistics Probability Letters 137: 84–90.

[32] Zeifman, A., Korolev, V., Satin, Y., Korotysheva, A. and Bening, V. (2014a). Perturbation bounds and truncations for a class of Markovian queues, Queueing Systems 76(2): 205–221.

[33] Zeifman, A., Leorato, S., Orsingher, E., Satin, Y. and Shilova, G. (2006). Some universal limits for nonhomogeneous birth and death processes, Queueing Systems 52(2): 139–151.

[34] Zeifman, A., Razumchik, R., Satin, Y., Kiseleva, K., Korotysheva, K. and Korolev, V. (2018c). Bounds on the rate of convergence for one class of inhomogeneous Markovian queueing models with possible batch arrivals and services, International Journal of Applied Mathematics and Computer Science 28(1): 141–154, DOI: 10.2478/amcs-2018-0011.

[35] Zeifman, A., Satin, Y., Korolev, V. and Shorgin, S. (2014b). On truncations for weakly ergodic inhomogeneous birth and death processes, International Journal of Applied Mathematics and Computer Science 24(3): 503–518, DOI: 10.2478/amcs-2014-0037.

[36] Zeifman, A., Satin, Y. and Kryukova, A. (2019). Applications of differential inequalities to bounding the rate of convergence for continuous-time Markov chains, AIP Conference Proceedings 2116(090009): 1–5.