No label defined (Q4945340)

This is a survey on matrix analytic methods to find the equilibrium distribution of certain Markov chains. The transition matrices considered are lower and upper Hessenberg matrices with transition probabilities \(p_{ij}\) invariant to block shifting in South-East direction for large \(i\) and \(j\). They occur as transition matrices of the imbedded Markov chain of certain queueing systems that are related to the GI/M/1 or M/G/1 queue with phase type interarrival times or service times, respectively. The associated Markov processes therefore are called of GI/M/1 type or of M/G/1 type. They have been introduced by Neuts and intensively studied by many authors. A third kind of matrices investigated generalizes both and is called of GI/G/1 type. The clear and well-written article reports on the basic theoretical results on the matrix representation of the solution in special cases (Section 3) and on different algorithms for the numerical solution (Sections 4 and 5) in the general case. These include classical iteration, block elimination by censoring, and state reduction. Finally an example of application (a model for a biligual server) is numerically evaluated. For the entire collection see [Zbl 0929.00017].