Autonomous Solution Methods for Large-Scale Markov Chains

W. S. Barge

Operations Research Program
North Carolina State University
Raleigh, NC 27695

W. J. Stewart

Department of Computer Science
North Carolina State University
Raleigh, NC 27695


Abstract

Since their introduction in the early 1900s, Markov chainshave been proposed as a means of modeling a v ariety of stochastic processes, including weather forecasting, voting patterns, and demographic trends. Markov chains have even been suggested as a model to predict and guide usage of the World Wide Web.

In his book, Modeling and Analysis of Stochastic Systems, Kulkarni provides some details on how applications in genetics, sociology, manpower planning, and telecommunications could be modeled as Markov chains. In most scenarios, the models are kept very small, usually less than several hundred states, in order to be kept tractable. Only in the areas of telecommunications and computer systems performance modeling have larger models been used successfully, and this because of the detailed knowledge of numerical solution algorithms possessed by the researchers working in these areas.

We are interested in autonomously choosing a method for computing the stationary distribution of finite, irreducible Markov chains.