Solving \(\text{M/G/}1\) type Markov chains: Recent advances and applications. (English) Zbl 0934.60086

Summary: A survey on numerical methods, based on Toeplitz matrix computation, for the solution of M/G/1 type Markov chains is presented together with some new advances. We show how the block Toeplitz structure, shared by the transition matrices associated with M/G/1 type Markov chains, can be exploited as the basis for devising fast and numerically stable algorithms, for the computation of the probability invariant vector and for the solution of the nonlinear matrix equation \(X= \sum^{+\infty}_{i=0} A_iX^i\).


60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
Full Text: DOI