Introduction to the Numerical Solution of Markov Chains

It is often possible to represent the behavior of a physical system by describing all the different states it can occupy and by indicating how it moves from one state to another in time. If the future evolution depends only on its current state, the system may be represented by a Markov process. When the space is discrete, the term Markov chain is employed. In this book, the first to offer a systematic and detailed treatment of the numerical solution of Markov chains, William Stewart provides scientists on many levels with the power to put this theory to use in the actual world, where it has applications in areas as diverse as engineering, economics, and education. His efforts make for essential reading in a rapidly growing field.Here Stewart explores all aspects of numerically computing solutions of Markov chains, especially when the state is huge. He provides extensive background to both discrete-time and continuous-time Markov chains and examines many different numerical computing methods-direct, single- and multi-vector iterative, and projection methods. More specifically, he considers recursive methods often used when the structure of the Markov chain is upper Hessenberg, iterative aggregation/disaggregation methods that are particularly appropriate when it is NCD (nearly completely decomposable), and reduced schemes for cases in which the chain is periodic. There are chapters on methods for computing transient solutions, on stochastic automata networks, and, finally, on currently available software. Throughout Stewart draws on numerous examples and comparisons among the methods he so thoroughly explains.