Hostname: page-component-76fb5796d-45l2p Total loading time: 0 Render date: 2024-04-27T03:46:56.822Z Has data issue: false hasContentIssue false
  • English
  • Français

Equilibrium distribution of block-structured Markov chains with repeating rows

Published online by Cambridge University Press:  14 July 2016

Winfried K. Grassmann  and
Daniel P. Heyman
Winfried K. Grassmann*
Affiliation:
University of Saskatchewan
Daniel P. Heyman*
Affiliation:
Bellcore
*
∗Postal address: Department of Computational Science, University of Saskatchewan, Saskatoon, Canada S7N 0W0.
∗∗Postal address: Room 3D-308, Bellcore, 331 Newman Springs Road, Red Bank, NJ 07701-7020, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we consider two-dimensional Markov chains with the property that, except for some boundary conditions, when the transition matrix is written in block form, the rows are identical except for a shift to the right. We provide a general theory for finding the equilibrium distribution for this class of chains. We illustrate theory by showing how our results unify the analysis of the M/G/1 and GI/M/1 paradigms introduced by M. F. Neuts.

Keywords

QUEUESMATRIX-GEOMETRIC SOLUTIONSWIENER–HOPF FACTORIZATIONGAUSSIAN ELIMINATIONALGORITHMS
Type
Research Papers
Information
Journal of Applied Probability , Volume 27 , Issue 3 , September 1990 , pp. 557 - 576
Copyright
Copyright © Applied Probability Trust 1990 

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

Feller, W. (1971) Introduction to Probability Theory and Its Applications, Vol. 2, 2nd edn. Wiley, New York.Google Scholar
Fryer, M. J. and Winsten, C. B. (1986) An algorithm to compute the equilibrium distribution of a one-dimensional bounded random walk. Operat. Res. 34, 449–454.CrossRefGoogle Scholar
Grassmann, W. K. (1985) The factorization of queueing equations and their interpretations. J. Opl. Res. Soc. 36, 1041–1050.CrossRefGoogle Scholar
Grassmann, W. K. (1986) The PHx/M/c queue. Selecta Statistica Canadiana 7, 25–52.Google Scholar
Grassmann, W. K. and Jain, J. L. (1989) Numerical solutions of the waiting time and idle time distribution of the arithmetic GI/G/1 queues. Operat. Res. 37, 141–150.CrossRefGoogle Scholar
Grassmann, W. K., Taksar, M. I. and Heyman, D. P. (1985) Regenerative analysis and steady state distributions for Markov chains. Operat. Res. 33, 1107–1116.CrossRefGoogle Scholar
Kemeny, J. G., Snell, J. L. and Knapp, A. W. (1966) Denumerable Markov Chains. Van Nostrand, Princeton, NJ.Google Scholar
Kumar, S., Grassmann, W. and Billinton, R. (1987) A stable algorithm to calculate steady-state probability and frequency of a Markov system. IEEE Trans. Reliability 36, 58–62.CrossRefGoogle Scholar
Lal, R. and Bhat, U. N. (1987) Reduced systems in Markov chains and their application in queueing theory. Queueing Systems 2, 147–172.CrossRefGoogle Scholar
Lal, R. and Bhat, U. N. (1988) Reduced system algorithms for Markov chains. Management Sci. 34, 1202–1220.CrossRefGoogle Scholar
Latouche, G. (1987) A note on two matrices occurring in the solution of quasi birth-and-death processes. Stochastic Models 3, 251–258.Google Scholar
Lucantoni, D. M. (1983) An Algorithmic Analysis of a Communication Model with Retransmission of Flawed Messages. Pitman, Boston.Google Scholar
Miller, D. R. (1981) Computation of steady-state probabilities for M/M/1 priority queues. Operat. Res. 29, 945–958.CrossRefGoogle Scholar
Neuts, M. F. (1979) Queues solvable without Rouché's theorem. Operat. Res. 27, 767–781.CrossRefGoogle Scholar
Neuts, M. F. (1981) Matrix-Geometric Solutions in Stochastic Models. The John Hopkins University Press, Baltimore.Google Scholar
Ramaswami, V. (1988) A stable recursion for the steady state vector in Markov chains of M/G/1 type. Stochastic Models 4, 183–188.CrossRefGoogle Scholar
Sheskin, T. J. (1985) A Markov partitioning algorithm for computing steady-state probabilities. Operat. Res. 33, 228–235.CrossRefGoogle Scholar
Wallace, V. L. (1969) The Solution of Quasi Birth and Death Processes Arising from Multiple Access Computer Systems. University of Michigan Systems Engineering Lab, Tech. Rep. No. 35.Google Scholar