2000 | OriginalPaper | Chapter
Numerical Methods for Computing Stationary Distributions of Finite Irreducible Markov Chains
Author : William J. Stewart
Published in: Computational Probability
Publisher: Springer US
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.