Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-26T04:12:49.439Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Problem of Establishing the Existence of Stationary Distributions for Continuous-Time Markov Chains

Published online by Cambridge University Press:  27 July 2009

P. K. Pollett  and
P. G. Taylor
P. K. Pollett
Affiliation:
Department of Mathematics, The University of Queensland, Queensland 4072, Australia
P. G. Taylor
Affiliation:
Department of Applied Mathematics, The University of Adelaide, G.P.O. Box 498, Adelaide, South Australia 5001, Australia
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the problem of establishing the existence of stationary distributions for continuous-time Markov chains directly from the transition rates Q. Given an invariant probability distribution m for Q, we show that a necessary and sufficient condition for m to be a stationary distribution for the minimal process is that Q be regular. We provide sufficient conditions for the regularity of Q that are simple to verify in practice, thus allowing one to easily identify stationary distributions for a variety of models. To illustrate our results, we shall consider three classes of multidimensional Markov chains, namely, networks of queues with batch movements, semireversible queues, and partially balanced Markov processes.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 7 , Issue 4 , October 1993 , pp. 529 - 543
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Anderson, W.J. (1991). Continuous-time Markov chains: An applications oriented approach. New York: Springer-Verlag.CrossRefGoogle Scholar
2.Bharath-Kumar, K. (1980). Discrete time queueing systems and their networks. IEEE Transactions on Communications 28: 260–263.CrossRefGoogle Scholar
3.Boucherie, R.J. & van Dijk, N.M. (1990). Spatial birth-death processes with multiple changes and applications to batch service queueing networks and clustering processes. Advances in Applied Probability 22: 433–455.CrossRefGoogle Scholar
4.Boucherie, R.J. & van Dijk, N.M. (1991). Product forms for queueing networks with state dependent multiple job transitions. Advances in Applied Probability 23: 152–187.CrossRefGoogle Scholar
5.Chung, K.L. (1967). Markov chains with stationary transition probabilities, 2nd ed.Berlin and New York: Springer-Verlag.Google Scholar
6.Coleman, J., Henderson, W., & Taylor, P.G. (1992). Product form equilibrium distributions and an algorithm for classes of batch movement queueing networks and stochastic Petri nets (to appear).Google Scholar
7.Dobrušin, R.L. (1957). Some classes of homogeneous denumerable Markov processes. Teoriya Veroyatnostei i Ee Primeneniya 2: 377–380.Google Scholar
8.Fakinos, D. (1990). Equilibrium queue size distributions for semi-reversible queues. Stochastic Processes and Their Applications 36: 331–337.CrossRefGoogle Scholar
9.Feller, W. (1968). An introduction to probability theory and its applications, Vol. 1, 3rd ed.New York: Wiley.Google Scholar
10.Gelenbe, E. (1991). Product form networks with negative and positive customers. Journal of Applied Probability 28: 656–663.CrossRefGoogle Scholar
11.Gelenbe, E., Glynn, P., & Sigman, K. (1991). Queues with negative arrivals. Journal of Applied Probability 28: 245–250.CrossRefGoogle Scholar
12.Henderson, W., Northcote, B.S., & Taylor, P.G. (1993). Geometric equilibrium distributions for queues with interactive batch departures. Annals of Operations Research (to appear).Google Scholar
13.Henderson, W. & Taylor, P.G. (1990). Product form in networks of queues with batch arrivals and batch services. Queueing Systems 6: 71–88.CrossRefGoogle Scholar
14.Hordijk, A. & van Dijk, N. (1983). Adjoint processes, job local balance and insensitivity for stochastic networks. Bulletin of the 44th Session of the International Statistics Institute 50: 776–788.Google Scholar
15.Hordijk, A. & van Dijk, N. (1983). Networks of queues. In Proceedings of the International Seminar on Modelling and Performance Evaluation Methodology, INRIA, Vol. 1. pp. 79–135.Google Scholar
16.Hsu, J. & Burke, P.J. (1976). Behaviour of tandem buffers with geometric input and Markovian output. IEEE Transactions on Communications 24: 358–360.CrossRefGoogle Scholar
17.Iglehart, D.L. (1964). Multivariate competition processes. Annals of Mathematical Statistics 35: 350–361.CrossRefGoogle Scholar
18.Jackson, J. (1957). Networks of waiting lines. Operations Research 5: 518–521.CrossRefGoogle Scholar
19.Kelly, F.P. (1983). Invariant measures and the g-matrix. In Kingman, J.F.C. & Reuter, G.E.H. (eds.), Probability, statistics and analysis. London Mathematical Society Lecture Notes Series, Vol. 79. Cambridge: Cambridge University Press, pp. 143–160.CrossRefGoogle Scholar
20.Kendall, D.G. & Reuter, G.E.H. (1957). The calculation of the ergodic projection for Markov chains and processes with a countable infinity of states. Acta Mathematica 97: 103–144.CrossRefGoogle Scholar
21.Kingman, J.F.C. (1969). Markov population processes. Journal of Applied Probability 6: 1–18.CrossRefGoogle Scholar
22.Miller, R.G. Jr. (1963). Stationary equations in continuous time Markov chains. Transactions of the American Mathematical Society 109: 35–44.Google Scholar
23.Pollett, P.K. (1987). Preserving partial balance in continuous-time Markov chains. Advances in Applied Probability 19: 431–453.CrossRefGoogle Scholar
24.Pollett, P.K. (1988). Reversibility, invariance and μ-invariance. Advances in Applied Probability 20: 600–621.CrossRefGoogle Scholar
25.Pujolle, G., Claude, J., & Seret, D. (1985). A discrete queueing system with a product form solution. Proceedings of the International Seminar on Performance of Distributed and Parallel Systems, Kyoto.Google Scholar
26.Reuter, G.E.H. (1957). Denumerable Markov processes and the associated contraction semigroups on l. Acta Mathematica 97: 1–46.CrossRefGoogle Scholar
27.Reuter, G.E.H. (1961). Competition processes. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability 2: 421–430.Google Scholar
28.Serfozo, R. (1988). Markovian network processes with system-dependent transition rates. Queueing Systems 5: 5–36.CrossRefGoogle Scholar
29.Sidi, M. & Segall, D. (1983). Structured priority queueing systems with applications to packet-radio networks. Performance Evaluation 3: 265–275.CrossRefGoogle Scholar
30.Walrand, J. (1983). A discrete-time queueing network. Journal of Applied Probability 20: 903–909.CrossRefGoogle Scholar
31.Whittle, P. (1968). Equilibrium distributions for an open migration process. Journal of Applied Probability 5: 567–571.CrossRefGoogle Scholar
32.Whittle, P. (1986). Systems in stochastic equilibrium. London: Wiley.Google Scholar
33.Wolff, R.W. (1989). Stochastic modeling and the theory of queues. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
34.Yan, S.J. & Chen, M.F. (1986). Multidimensional Q-processes. Chinese Annals of Mathematics 7: 90–110.Google Scholar