gth_solve¶
Filename: gth_solve.py
Author: Daisuke Oyama
Routine to compute the stationary distribution of an irreducible Markov chain by the GrassmannTaksarHeyman (GTH) algorithm.

quantecon.markov.gth_solve.
gth_solve
(A, overwrite=False, use_jit=True)[source]¶ This routine computes the stationary distribution of an irreducible Markov transition matrix (stochastic matrix) or transition rate matrix (generator matrix) A.
More generally, given a Metzler matrix (square matrix whose offdiagonal entries are all nonnegative) A, this routine solves for a nonzero solution x to x (A  D) = 0, where D is the diagonal matrix for which the rows of A  D sum to zero (i.e., \(D_{ii} = \sum_j A_{ij}\) for all \(i\)). One (and only one, up to normalization) nonzero solution exists corresponding to each reccurent class of A, and in particular, if A is irreducible, there is a unique solution; when there are more than one solution, the routine returns the solution that contains in its support the first index i such that no path connects i to any index larger than i. The solution is normalized so that its 1norm equals one. This routine implements the GrassmannTaksarHeyman (GTH) algorithm [R7], a numerically stable variant of Gaussian elimination, where only the offdiagonal entries of A are used as the input data. For a nice exposition of the algorithm, see Stewart [R8], Chapter 10.
Parameters: A : array_like(float, ndim=2)
Stochastic matrix or generator matrix. Must be of shape n x n.
Returns: x : numpy.ndarray(float, ndim=1)
Stationary distribution of A.
overwrite : bool, optional(default=False)
Whether to overwrite A.
References
[R7] (1, 2) W. K. Grassmann, M. I. Taksar and D. P. Heyman, “Regenerative Analysis and Steady State Distributions for Markov Chains,” Operations Research (1985), 11071116. [R8] (1, 2) W. J. Stewart, Probability, Markov Chains, Queues, and Simulation, Princeton University Press, 2009.