×

zbMATH — the first resource for mathematics

On the stability of the computation of the stationary probabilities of Markov chains using Perron complements. (English) Zbl 1071.65504
Summary: For an \(n\)-state ergodic homogeneous Markov chain whose transition matrix is \(T \in \mathbb R^{n,n}\), it has been shown by C. D. Meyer on the one hand and by S. J. Kirkland, M. Neumann and J. Xu on the other hand that the stationary distribution vector and that the mean first passage matrix, respectively, can be computed by a divide and conquer parallel method from the Perron complements of \(T\). This is possible due to the facts, that the Perron complements of \(T\) are themselves transition matrices for finite ergodic homogeneous Markov chains with fewer states and that their stationary distribution vectors are multiples of the corresponding subvectors of the stationary distribution vector of the entire chain.
Here we examine various questions concerning the stability of computing the stationary distribution vectors of the Perron complements and compare them with the stability of computing the stationary distribution vector for the entire chain. In particular, we obtain that condition numbers which are related to the coefficients of ergodicity improve as we pass from the entire chain to the chains associated with its Perron complements.

MSC:
65C40 Numerical analysis or methods applied to Markov chains
65F35 Numerical computation of matrix norms, conditioning, scaling
PDF BibTeX Cite
Full Text: DOI
References:
[1] Finite Markov Chains. Van Nostrand: New York, 1960. · Zbl 0089.13704
[2] Meyer, SIAM Review 17 pp 443– (1975)
[3] Generalized Inverses: Theory and Applications. Academic Press: New York, 1973.
[4] Generalized Inverses of Linear Transformations. Dover: New York, 1991. · Zbl 0732.15003
[5] Meyer, Linear Algebra and Its Applications 114/115 pp 69– (1989)
[6] Meyer, SIAM Review 31 pp 240– (1989)
[7] Courtois, Linear Algebra and Its Applications 76 pp 59– (1986) · Zbl 0588.53030
[8] Marek, Linear Algebra and Its Applications 363 pp 177– (2003)
[9] Kirkland, Numerical Linear Algebra with Applications 8 pp 287– (2001) · Zbl 0984.05057
[10] Fallat, Linear Algebra and Its Applications 327 pp 85– (2001)
[11] Meyer, SIAM Journal on Algebraic and Discrete Methods 1 pp 273– (1980)
[12] Bauer, Linear Algebra and Its Applications 2 pp 275– (1969)
[13] Deutsch, Numerische Mathematik 18 pp 182– (1971)
[14] Non-negative Matrices and Markov Chains (2nd edn). Springer: New York, 1981. · Zbl 1099.60004
[15] Hunter, Linear Algebra and Its Applications 102 pp 121– (1988)
[16] Cho, Linear Algebra and Its Applications 335 pp 137– (2001)
[17] Seneta, Advances Applied Probability 20 pp 228– (1988)
[18] Sensitivity analysis, ergodicity coefficients, and rank-one updates for finite Markov chains. In Numerical Solution of Markov Chains, (ed.). Marcel Dekker: New York, 1991; 121-129. · Zbl 0744.60078
[19] Cho, Linear Algebra and Its Applications 316 pp 21– (2000)
[20] Metzler, Journal of Political Economics 59 pp 14– (1945)
[21] Metzler, The Quarterly Journal of Economics 65 pp 433– (1951)
[22] Meyer, SIAM Journal on Matrix Analysis and Applications 15 pp 715– (1994)
[23] Entrywise relative perturbation theory for nonsingular M-matrices. BIT, 1995; 417-427. · Zbl 0837.65016
[24] Funderlic, Linear Algebra and Its Applications 76 pp 1– (1986)
[25] Ipsen, SIAM Journal on Matrix Analysis and Applications 15 pp 1061– (1994)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.