gth_solve

Filename: gth_solve.py

Author: Daisuke Oyama

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 [R1112], 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 [R1212], 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

[R1112](1, 2) W. K. Grassmann, M. I. Taksar and D. P. Heyman, “Regenerative Analysis and Steady State Distributions for Markov Chains,” Operations Research (1985), 1107-1116.
[R1212](1, 2) W. J. Stewart, Probability, Markov Chains, Queues, and Simulation, Princeton University Press, 2009.