Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-03T00:07:57.656Z Has data issue: false hasContentIssue false
  • English
  • Français

Operator-geometric stationary distributions for markov chains, with application to queueing models

Published online by Cambridge University Press:  01 July 2016

R. L. Tweedie
R. L. Tweedie*
Affiliation:
CSIRO Division of Mathematics and Statistics
*
∗Present address: SIROMATH Pty Ltd, 1 York St., Sydney, NSW 2000, Australia.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper considers a class of Markov chains on a bivariate state space , whose transition probabilities have a particular ‘block-partitioned' structure. Examples of such chains include those studied by Neuts [8] who took E to be finite; they also include chains studied in queueing theory, such as (Nn, Sn) where Nn is the number of customers in a GI/G/1 queue immediately before, and Sn the remaining service time immediately after, the nth arrival.

We show that the stationary distribution Πfor these chains has an ‘operator-geometric' nature, with , where the operator S is the minimal solution of a non-linear operator equation. Necessary and sufficient conditions for Πto exist are also found. In the case of the GI/G/1 queueing chain above these are exactly the usual stability conditions.

G1/G/1 QUEUE; PHASE-TYPE; INVARIANT MEASURE; FOSTER'S CONDITIONS

Type
Research Article
Information
Advances in Applied Probability , Volume 14 , Issue 2 , June 1982 , pp. 368 - 391
Copyright
Copyright © Applied Probability Trust 1982 

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] Chung, K. L. (1967) Markov Chains with Stationary Transition Probabilities, 2nd edn. Springer-Verlag, New York.Google Scholar
[2] Cogburn, R. (1975) A uniform theory for sums of Markov chain transition probabilities. Ann. Prob. 3, 191–214.Google Scholar
[3] Feller, W. (1971) An Introduction to Probability Theory and its Applications, volume II, 2nd edn. Wiley, New York.Google Scholar
[4] Finch, P. D. (1961) On the busy period in the queueing system GI/G/1. J. Austral. Math. Soc. 2, 217–228.Google Scholar
[5] Neuts, M. F. (1967) Two Markov chains arising from examples of queues with state dependent service times. Sankhya A 29, 255–264.Google Scholar
[6] Neuts, M. F. (1969) The queue with Poisson input and general service times, treated as a branching process. Duke Math. J. 36, 215–231.CrossRefGoogle Scholar
[7] Neuts, M. F. (1975) Probability distributions of phase type. In Liber Amicorum Professor Emeritus H. Florin, Department of Mathematics, University of Louvain, Belgium, 173–206.Google Scholar
[8] Neuts, M. F. (1978) Markov chains with applications in queueing theory, which have a matrix-geometric invariant probability vector. Adv. Appl. Prob. 10, 185–212.Google Scholar
[9] Neuts, M. F. (1980) The probabilistic significance of the rate matrix in matrix-geometric invariant vectors. J. Appl. Prob. 17, 291–296.CrossRefGoogle Scholar
[10] Neuts, M. F. (1981) Matrix-Geometric Solutions in Stochastic Models–An Algorithmic Approach. The Johns Hopkins University Press, Baltimore, MD.Google Scholar
[11] Orey, S. (1975) Lecture Notes on Limit Theorems for Markov Chain Transition Probabilities. Van Nostrand-Reinhold, London.Google Scholar
[12] Revuz, D. (1975) Markov Chains. North-Holland, Amsterdam.Google Scholar
[13] Tuominen, P. and Tweedie, R. L. (1979) The recurrence structure of general Markov processes. Proc. Lond. Math. Soc. (3) 39, 554–576.CrossRefGoogle Scholar
[14] Tweedie, R. L. (1976) Criteria for classifying general Markov chains. Adv. Appl. Prob. 8, 737–771.CrossRefGoogle Scholar
[15] Tweedie, R. L. (1974) R-theory for Markov chains on a general state space I. Ann. Prob. 2, 840–864.Google Scholar