gth_solve¶
Routine to compute the stationary distribution of an irreducible Markov chain by the Grassmann-Taksar-Heyman (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 off-diagonal 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 1-norm equals one. This routine implements the Grassmann-Taksar-Heyman (GTH) algorithm [1], a numerically stable variant of Gaussian elimination, where only the off-diagonal entries of A are used as the input data. For a nice exposition of the algorithm, see Stewart [2], Chapter 10.
- Parameters:
- Aarray_like(float, ndim=2)
Stochastic matrix or generator matrix. Must be of shape n x n.
- Returns:
- xnumpy.ndarray(float, ndim=1)
Stationary distribution of A.
- overwritebool, optional(default=False)
Whether to overwrite A.
References