Error bounds for arbitrary approximations of “nearly reversible” Markov chains and a communications example. (English) Zbl 0914.60040

Author’s abstract: A condition is provided to conclude error bounds when using an arbitrary steady state approximation of a “nearly reversible” Markov chain. The error bound is of the form \(\Delta R\) where (i) \(\Delta\) can be computed by the approximation in order, (ii) \(R\) can be obtained analytically by the system of interest. The results will be illustrated for a communication system with different source characteristics. An approximation is suggested based on truncating the corresponding Möbius-function. An \(R\)-value is obtained by an inductive Markov reward equation. Numerical illustration indicates that the error bound can be useful for practical purposes.


60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
Full Text: EuDML Link


[1] T. Altiok, H. G. Perros: Queueing Networks with Blocking. North Holland, Amsterdam 1989. · Zbl 0699.68010
[2] V. E. Beneš: A thermodynamic theory of traffic in connecting network. Bell System Technical Journal VLII (1963), 3, 567-607.
[3] V. E. Beneš: Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, New York 1965. · Zbl 0138.40904
[4] P. J. Curtois: Decomposability: Queueing and Computer System Application. Academic Press, New York 1977.
[5] P. J. Curtois, P. Semal: Bounds and conditional steady-state distribution in large Markovian and queueing models. Teletraffic Analalysis and Computer Performance Evaluation (O. J. Boxma, J. W. Cohen and H. C. Tijms, North Holland, Amsterdam 1986.
[6] A. Hordijk, A. Ridder: Insensitive bounds for the stationary distribution on nonreversible Markov chains. J. Appl. Probab. 25 (1988), 9-20. · Zbl 0649.60095
[7] A. Hordijk, N. M. van Dijk: Networks of queues. Part I: Job-local balance and the adjoint process. Part II: General routing and service characteristics. Lecture Notes in Control and Inform. Sci. 60 (1983), 158-205. · Zbl 0599.60083
[8] F. P. Kelly: Reversibility and Stochastic Networks. Wiley, New York 1979. · Zbl 0422.60001
[9] J. G. Kemeny J. L. Snell, A. W. Knapp: Denumerable Markov Chains. Van Nostrand, Princeton N. J. 1966. · Zbl 0149.13301
[10] C. D. Meyer: The condition of finite Markov chain and perturbation bounds for the limiting probabilities. SIAM J. Algebraic Discrete Methods 1 (1980), 273-283. · Zbl 0498.60071
[11] R. R. Muntz E. De Souza e Silva, A. Goyal: Bounding availability of repairable computer systems. Performance Evaluation 17 (1989), 29-38. · Zbl 1395.68057
[12] J. K. Muppala, K. S. Trivedi: Numerical Transient Solution of Finite Markovian Systems. Research Report, Duke University 1990. · Zbl 0784.60089
[13] R. Nelson, L. Kleinrock: Rude–CSMA: A multihop channel access protocol. IEEE Trans. Comm. COM 33 (1985), 8, 785-791. · Zbl 0572.94004
[14] E. Pinsky, Y. Yemini: A statistical mechanics of some interconnection networks. Performance’84, Elsevier, North Holland, Amsterdam 1984.
[15] P. J. Schweitzer: Perturbation theory and undiscounted Markov renewal programming. Oper. Res. 17 (1969), 716-727. · Zbl 0176.50003
[16] E. Seneta: Sensitivity to perturbation of the stationary distribution: Some refinements. Linear Algebra Appl. 108 (1988), 121-126. · Zbl 0657.60096
[17] W. J. Stewart (ed.): Numerical Solutions of Markov Chains. Marcel Dekker, New York 1990.
[18] H. C. Tijms: Stochastic Modelling and Analysis. Wiley, New York 1986.
[19] J. van der Wal, P. J. Schweitzer: Iterative bounds on the equilibrium distribution of a finite Markov chain. Probab. in Engng. Inform. Sci. 1 (1987), 117-131. · Zbl 1133.60330
[20] N. M. van Dijk: On the importance of bias terms for error bounds and comparison results. Numerical Solutions of Markov Chains (W. J. Stewart, Marcel Dekker, New York 1991, pp. 618-647.
[21] N. M. van Dijk: Approximate uniformization for continuous-time Markov chains with an application to performability analysis. Stochastic Process. Appl. 40 (1992), 339-357. · Zbl 0753.60066
[22] N. M. van Dijk, M. L. Puterman: Perturbation theory for Markov reward processes with applications to queueing. Adv. in Appl. Probab. 20 (1988), 78-99. · Zbl 0642.60100
[23] N. M. van Dijk, J. P. Veltkamp: Product form for stochastic interference systems. Probab. in Engng. Inform. Sci. 2 (1988), 355-376. · Zbl 1134.60335
[24] J. P. Veltkamp: Cost Functions for Interference Systems and VLSI High-level Synthesis. Ph. D. Thesis. Twente University 1988.
[25] B. S. Yoon, B. S. Shanthikumar: Bounds and approximations for the transient behaviour of continuous-time Markov chains. Probab. in Engng. Inform. Sci. 3 (1989), 175-109. · Zbl 1134.60366
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.