Error bounds for arbitrary approximations of “nearly reversible” Markov chains and a communications example

Nico M. van Dijk

Kybernetika (1997)

  • Volume: 33, Issue: 2, page 171-184
  • ISSN: 0023-5954

How to cite


Dijk, Nico M. van. "Error bounds for arbitrary approximations of “nearly reversible” Markov chains and a communications example." Kybernetika 33.2 (1997): 171-184. <>.

author = {Dijk, Nico M. van},
journal = {Kybernetika},
keywords = {steady state approximation; Möbius-function; Markov reward equation},
language = {eng},
number = {2},
pages = {171-184},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Error bounds for arbitrary approximations of “nearly reversible” Markov chains and a communications example},
url = {},
volume = {33},
year = {1997},

AU - Dijk, Nico M. van
TI - Error bounds for arbitrary approximations of “nearly reversible” Markov chains and a communications example
JO - Kybernetika
PY - 1997
PB - Institute of Information Theory and Automation AS CR
VL - 33
IS - 2
SP - 171
EP - 184
LA - eng
KW - steady state approximation; Möbius-function; Markov reward equation
UR -
ER -


  1. T. Altiok, H. G. Perros, Queueing Networks with Blocking, North Holland, Amsterdam 1989. (1989) Zbl0699.68010MR1048619
  2. V. E. Beneš, A thermodynamic theory of traffic in connecting network, Bell System Technical Journal VLII (1963), 3, 567-607. (1963) MR0149572
  3. V. E. Beneš, Mathematical Theory of Connecting Networks and Telephone Traffic, Academic Press, New York 1965. (1965) MR0210516
  4. P. J. Curtois, Decomposability: Queueing and Computer System Application, Academic Press, New York 1977. (1977) MR0479702
  5. P. J. Curtois, P. Semal, Bounds and conditional steady-state distribution in large Markovian and queueing models, In: Teletraffic Analalysis and Computer Performance Evaluation (O. J. Boxma, J. W. Cohen and H. C. Tijms, eds.), North Holland, Amsterdam 1986. (1986) 
  6. A. Hordijk, A. Ridder, Insensitive bounds for the stationary distribution on nonreversible Markov chains, J. Appl. Probab. 25 (1988), 9-20. (1988) MR0929500
  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. (1983) 
  8. F. P. Kelly, Reversibility and Stochastic Networks, Wiley, New York 1979. (1979) Zbl0422.60001MR0554920
  9. J. G. Kemeny J. L. Snell, A. W. Knapp, Denumerable Markov Chains, Van Nostrand, Princeton N. J. 1966. (1966) MR0207042
  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. (1980) MR0586154
  11. R. R. Muntz E. De Souza e Silva, A. Goyal, Bounding availability of repairable computer systems, Performance Evaluation 17 (1989), 29-38. (1989) MR1031590
  12. J. K. Muppala, K. S. Trivedi, Numerical Transient Solution of Finite Markovian Systems, Research Report, Duke University 1990. (1990) 
  13. R. Nelson, L. Kleinrock, Rude--CSMA: A multihop channel access protocol, IEEE Trans. Comm. COM 33 (1985), 8, 785-791. (1985) Zbl0572.94004MR0895048
  14. E. Pinsky, Y. Yemini, A statistical mechanics of some interconnection networks, In: Performance'84, Elsevier, North Holland, Amsterdam 1984. (1984) MR0822805
  15. P. J. Schweitzer, Perturbation theory and undiscounted Markov renewal programming, Oper. Res. 17 (1969), 716-727. (1969) Zbl0176.50003MR0256721
  16. E. Seneta, Sensitivity to perturbation of the stationary distribution: Some refinements, Linear Algebra Appl. 108 (1988), 121-126. (1988) Zbl0657.60096MR0959699
  17. W. J. Stewart (ed.), Numerical Solutions of Markov Chains, Marcel Dekker, New York 1990. (1990) MR1142108
  18. H. C. Tijms, Stochastic Modelling and Analysis, Wiley, New York 1986. (1986) MR0847718
  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. (1987) Zbl1133.60330
  20. N. M. van Dijk, On the importance of bias terms for error bounds and comparison results, In: Numerical Solutions of Markov Chains (W. J. Stewart, ed.), Marcel Dekker, New York 1991, pp. 618-647. (1991) MR1142133
  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. (1992) Zbl0753.60066MR1158030
  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. (1988) Zbl0642.60100MR0932536
  23. N. M. van Dijk, J. P. Veltkamp, Product form for stochastic interference systems, Probab. in Engng. Inform. Sci. 2 (1988), 355-376. (1988) 
  24. J. P. Veltkamp, Cost Functions for Interference Systems and VLSI High-level Synthesis, Ph. D. Thesis. Twente University 1988. (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. (1989) 

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.