The State Reduction and Related Algorithms and Their Applications to the Study of Markov Chains, Graph Theory, and the Optimal Stopping Problem

AbstractWe discuss the State Reduction/GTH (Grassmann, Taksar, Heyman) algorithm for recursively finding invariant measure. We demonstrate the relationship between this algorithm and the Freidlin–Wentzell “tree decomposition” approach to study the characteristics of Markov chains. The structure of the State Reduction/GTH algorithm suggests the natural idea for finding the distribution of a Markov chain at the moment of first visit to a given set, and some similar characteristics. We study the possible range of such algorithms. We also present a new algorithm for solving the classical problem of optimal stopping of a Markov chain based on a similar idea of sequential elimination of some states. We give shorter and more transparent proofs of some previously known results, and improve the bounds of Freidlin–Wentzell in the perturbation theory of Markov chains. Some applications to graph theory are also discussed