``Introduction to the Numerical Solution of Markov Chains''

William J. Stewart

Billy's Home Page

Organization,   Acknowledgements
Table of Contents,   Ordering Information


The purpose of this book is to provide an introductory, yet systematic and detailed, treatment of the numerical solution of Markov chains. Markov chain modelling is used in many diverse areas, not only in computer science and engineering but also in other disciplines such as mathematics, probability and statistics, operations research, industrial engineering, electrical engineering, biology, genetics and agriculture, economics and demographics, education, and so on. Markov chains may be used to locate bottlenecks in communication networks; to assess the benefit of increasing the number of CPUs in multiprocessor systems; and to quantify the effect of scheduling algorithms on throughput. They may be used in reliability modelling to estimate the mean time to failure of components in systems as diverse as software systems and aerospace systems and to model the performance of fault-tolerant computers. Markov chains have also shown themselves to be a valuable analysis tool in a variety of economic models, from population forecasting to financial planning. They have been and continue to be the method of choice for modelling very many other systems. In view of the fact that computer technology has reached the point that numerical computation is now readily within the reach of everyone, and the fact that analytic solutions are simply not available for models that incorporate the characteristics modellers seek, we find ourselves in a phase of rapidly rising interest in solving Markov chains numerically. Since there is no other book currently available that treats this subject, this book seeks to fill that important gap.

It is often possible to represent the behavior of a physical system by describing all the different states that it can occupy and by indicating how it moves from one state to another in time. If the future evolution of the system depends only on its current state, the system may be represented by a Markov process. The term Markov chain is employed when the state space is discrete. The information that is most often sought from such a model is the probability of being in a given state or subset of states at a certain time after the system becomes operational. Often this time is taken to be sufficiently long that all influence of the initial starting state has been erased. The probabilities thus obtained are referred to as the long-run or stationary probabilities . Probabilities at a particular time $t$ are called transient probabilities . When the number of states is small, it is relatively easy to obtain transient and stationary solutions quickly and accurately and from these to predict the behavior of the system. However, as models become more complex --- and this is increasingly the trend --- the process of obtaining these solutions becomes much more difficult. It is to this aspect that the current text is geared. It is the purpose of Introduction to the Numerical Solution of Markov Chains to explore and explain all aspects of numerically computing solutions of Markov chains, especially when the state space is huge.

Billy's Home Page