Reflections on the Numerical Solution of Markov Chains
William J. Stewart · 2010
It has been 45 years since Vic Wallace introduced RQA1, the first software system to generate and then compute the stationary distribution of Markov chains. RQA1 proved successful for a period of time but eventually hit upon a type of problem that it just could not solve, namely a nearly-completely-decomposable (NCD) Markov chain. In the intervening years our understanding of NCD systems has grown immensely which in turn has lead to the development of numerical techniques specifically designed for, and very effective at, solving such problems. An examination of the history of solving Markov chains over the years since shows that this phenomenon continues to this day. Problems that are not amenable to resolution by existing methods arise often unexpectedly; they are subsequently analyzed and give rise to the development of novel solution procedures. The application of Markov chains to model and analyze emerging technology - the development of search engines such as Google comes to mind - is particularly prone to creating such problems/opportunities. The paper examines how problems concerning generating state spaces, storing huge matrices and analyzing their composition have lead to important theoretical and practical results.