Numerical Methods for Computing Stationary Distributions of Finite Irreducible Markov Chains

In this chapter our attention will be devoted to computational methods for computing stationary distributions of finite irreducible Markov chains. We let q _ij denote the rate at which an n-state Markov chain moves from state i to state j. The n × n matrix Q whose off-diagonal elements are q _ij and whose ith diagonal element is given by $$ - \sum\limits_{j = 1}^n , j \ne i$$ q _ij is called the infinitesimal generator of the Markov chain. It may be shown that the stationary probability vector π, a row vector whose k-th element denotes the stationary probability of being in state k, can be obtained by solving the homogeneous system of equations πQ = 0. Alternatively, the problem may be formulated as an eigenvalue problem πP = π, where P = QΔt+I is the stochastic matrix of transition probabilities, (Δt must be chosen sufficiently small so that the probability of two or more transitions occurring in time Δt is small, i.e., of order o(t)). Mathematically, the problem is therefore quite simple. Unfortunately, problems arise from the computational point of view because of the large number of states which many systems may occupy. As indicated in Chapters 1 and 2, it is not uncommon for thousands of states to be generated even for simple applications.