Numerical Methods for Structured Markov Chains

Abstract The book deals with the numerical solution of structured Markov chains which include M/G/1 and G/M/1-type Markov chains, QBD processes, non-skip-free queues, and tree-like stochastic processes and has a wide applicability in queueing theory and stochastic modeling. It presents in a unified language the most up to date algorithms, which are so far scattered in diverse papers, written with different languages and notation. It contains a thorough treatment of numerical algorithms to solve these problems, from the simplest to the most advanced and most efficient. Nonlinear matrix equations are at the heart of the analysis of structured Markov chains, they are analysed both from the theoretical, from the probabilistic, and from the computational point of view. The set of methods for solution contains functional iterations, doubling methods, logarithmic reduction, cyclic reduction, and subspace iteration, all are described and analysed in detail. They are also adapted to interesting specific queueing models coming from applications. The book also offers a comprehensive and self-contained treatment of the structured matrix tools which are at the basis of the fastest algorithmic techniques for structured Markov chains. Results about Toeplitz matrices, displacement operators, and Wiener-Hopf factorizations are reported to the extent that they are useful for the numerical treatment of Markov chains. Every and all solution methods are reported in detailed algorithmic form so that they can be coded in a high-level language with minimum effort.