×

On optimal condition numbers for Markov chains. (English) Zbl 1160.60022

The authors consider the sensitivity of the stationary distribution of finite homogeneous ergodic Markov chain to perturbations in its transition matrix. Let \(T\) and \({\tilde T} = T - E\) be arbitrary nonnegative, irreducible, stochastic matrices corresponding to two ergodic Markov chains on \(n\) states. A function \(\kappa(T)\) is called a condition number for Markov chains with respect to the \((\alpha,\beta)\)-norm pair if \(\|\pi- \tilde{\pi}\|_\alpha \leq \kappa(T)\|E\|_\beta\). Here \(\pi\) and \({\tilde \pi}\) are the stationary distribution vectors of the two chains, respectively, \(E\) is the perturbation in transition matrix. Various condition numbers, particularly with respect to the \((1, \infty)\) and \((\infty, \infty)\)-norm pairs have been suggested in the literature. They were ranked according to their size by G. E. Cho and C. D. Meyer [Linear Algebra Appl. 335, 137–150 (2001; Zbl 0983.60062)].
In this paper it is shown that the generalized ergodicity coefficient \[ \tau_p(A^{\#}) = \sup_{y^te=0} \frac {\| y^t A^{\#} \|_p} {\|y\|_1}, \] where \(e\) is the \(n\)-vector of all 1’s and \(A^{\#}\) is the group generalized inverse of \(A = I - T\), is the smallest condition number of Markov chains with respect to the \((p, \infty)\)-norm pair. This result is used to identify the smallest condition number of Markov chains among the \((\infty, \infty)\) and \((1, \infty)\)-norm pairs. These are, respectively, \(\kappa_3\) and \(\kappa_6\) in the Cho-Meyer list of 8 condition numbers. Kirkland has shown that \(\kappa_3(T)\geq (n-1)/(2n)\) and he has characterized transition matrices for which equality holds. In the paper it is proved again that \(2\kappa_3(T)\leq \kappa_6(T)\) which appears in the Cho-Meyer paper. Transition matrices \(T\) for which \(\kappa_6(T)= (n-1)/n\) are characterized. There is actually only one such matrix: \(T = (J_n - I)/(n - 1)\), where \(J_n\) is the \(n \times n\) matrix of all 1 ’s.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
15B51 Stochastic matrices
15A12 Conditioning of matrices

Citations:

Zbl 0983.60062
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anstreicher, K.; Rothblum, U., Using Gauss-Jordan elimination to compute the index, generalized nullspace, and Drazin inverse, Lin. Alg. Appl., 85, 221-239 (1987) · Zbl 0613.65028 · doi:10.1016/0024-3795(87)90219-9
[2] Ben-Israel, A.; Greville, T. N.E., Generalized Inverses: Theory and Applications, 2nd edn (2003), New York: Springer, New York · Zbl 1026.15004
[3] Berman, A.; Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences (1994), Philadelphia: SIAM Publications, Philadelphia · Zbl 0815.15016
[4] Campbell, S. L.; Meyer, C. D., Generalized Inverses of Linear Transformations (1991), New York: Dover Publications, New York · Zbl 0732.15003
[5] Cho, G. E.; Meyer, C. D., Markov chain sensitivity measured by mean first passage times, Lin. Alg. Appl., 316, 21-28 (2000) · Zbl 0968.60066 · doi:10.1016/S0024-3795(99)00263-3
[6] Cho, G. E.; Meyer, C. D., Comparison of perturbation bounds for the stationary distribution of a Markov chain, Lin. Alg. Appl., 335, 137-150 (2001) · Zbl 0983.60062 · doi:10.1016/S0024-3795(01)00320-2
[7] Dobrushin, R. L., Central limit theorem for non-stationary Markov chains, I, II. Theory Probab, Appl., 1, 65-80 (1956)
[8] Feller, W., An Introduction to Probability Theory and its Applications, vol. I (1960), New York: Wiley, New York · Zbl 0138.10207
[9] Funderlic, R.; Meyer, C., Sensitivity of the stationary distribution vector for an ergodic Markov chain, Lin. Alg. Appl., 76, 1-17 (1986) · Zbl 0583.60064 · doi:10.1016/0024-3795(86)90210-7
[10] Golub, G. H.; Meyer, C. D., Using the QR-factorization and group inversion to compute, differentiate, and estimate the sensitivity of stationary probabilities for Markov chains, SIAM J. Alg. Discrete Meth., 7, 273-281 (1986) · Zbl 0594.60072 · doi:10.1137/0607031
[11] Hartfiel, D. J.; Meyer, C. D., On the structure of stochastic matrices with a subdominant eigenvalue near 1, Lin. Alg. Appl., 272, 193-203 (1998) · Zbl 0892.15017 · doi:10.1016/S0024-3795(97)00333-9
[12] Hartwig, R., A method for calculating A^d, Math. Japon., 26, 37-43 (1981) · Zbl 0458.15002
[13] Haviv, M.; Vander Heyden, L., Perturbation bounds for the stationary probabilities of a finite Markov chain, Adv. Appl. Prob., 16, 804-818 (1984) · Zbl 0559.60055 · doi:10.2307/1427341
[14] Higham, N. J.; Night, P. A., Componentwise error analysis for stationary iterative methods, in Linear algebra, Markov chains, and queueing models, Inst. Math. Appl. Minnieap., 48, 29-46 (1993) · Zbl 0794.65034
[15] Ipsen, I.; Meyer, C., Uniform stability of Markov chains, SIAM J. Matrix Anal. Appl., 15, 1061-1074 (1994) · Zbl 0809.65144 · doi:10.1137/S0895479892237562
[16] Kemeny, J. G.; Snell, J. L., Finite Markov Chains (1960), Princeton: Van Nostrand, Princeton · Zbl 0089.13704
[17] Kirkland, S. J., On a question concerning condition numbers for Markov chains, SIAM J. Matrix Anal. Appl., 23, 1109-1119 (2002) · Zbl 1013.15005 · doi:10.1137/S0895479801390947
[18] Kirkland, S.J., Neumann, M.: The case of equality in the Dobrushin-Deutsch-Zenger bound. Lin. Alg. Appl. (2008) (submitted) · Zbl 1181.15025
[19] Kirkland, S.; Neumann, M.; Shader, B., Applications of Pazs inequality to perturbation bounds for Markov chains, Lin. Alg. Appl., 268, 183-196 (1998) · Zbl 0891.65147 · doi:10.1016/S0024-3795(97)00042-6
[20] Kirkland, S.; Neumann, M.; Xu, J., Transition matrices for well-conditioned Markov chains, Lin. Alg. Appl., 424, 118-131 (2007) · Zbl 1120.15017 · doi:10.1016/j.laa.2006.06.003
[21] Meyer, C. D., The role of the group generalized inverse in the theory of finite Markov chains, SIAM Rev., 17, 443-464 (1975) · Zbl 0313.60044 · doi:10.1137/1017044
[22] Meyer, C. D., The condition of a finite Markov chain and perturbation bounds for the limiting probabilities, SIAM J. Alg. Discrete Meth., 1, 273-283 (1980) · Zbl 0498.60071 · doi:10.1137/0601031
[23] Meyer, C. D., Sensitivity of the stationary distribution of a Markov chain, SIAM J. Matrix Anal. Appl., 15, 715-728 (1994) · Zbl 0809.65143 · doi:10.1137/S0895479892228900
[24] Meyer, C. D., Matrix Analysis and Applied Linear Algebra (2000), Philadelphia: SIAM Publications, Philadelphia · Zbl 0962.15001
[25] Meyer, C. D.; Shoaf, J. M., Updating finite Markov chains by using techniques of group matrix inversion, J. Stat. Comput. Simul., 11, 163-181 (1980) · Zbl 0464.60075 · doi:10.1080/00949658008810405
[26] Rothblum, U.; Tan, C.-P., Upper bounds on the maximum modulus of subdominant eigenvlaues. of nonnegative matrices, Lin. Alg. Appl., 66, 45-86 (1985) · Zbl 0568.15013 · doi:10.1016/0024-3795(85)90125-9
[27] Schweitzer, P., Perturbation theory and finite Markov chains, J. Appl. Probab., 5, 410-413 (1968) · Zbl 0196.19803 · doi:10.2307/3212261
[28] Seneta, E., Non-Negative Matrices and Markov Chains (1981), New York: Springer, New York · Zbl 0471.60001
[29] Seneta, E., Perturbation of the stationary distribution measured by ergodicity coefficients, Adv. Appl. Probab., 20, 228-230 (1988) · Zbl 0645.60070 · doi:10.2307/1427277
[30] Seneta, E.; Stewart, W. J., Sensitivity analysis, ergodicity coefficients, and rank-one updates for finite Markov chains, Numerical Solution of Markov Chains (1991), New York: Marcel Dekker, New York · Zbl 0744.60078
[31] Stewart, G. W., Gaussian elimination, perturbation theory, and Markov chains, in Linear algebra, Markov chains, and queueing models, Inst. Math. Appl. Minneap., 48, 59-69 (1993) · Zbl 0789.65102
[32] Varga, R. S., Matrix Iterative Analysis, Second Revised and Expanded Edition (2000), Heidelberg: Springer, Heidelberg · Zbl 0998.65505
[33] Wilkinson, J. H., Note on the practical significance of the Drazin inverse, in Recent applications of generalized inverses, Res. Notes Math., 66, 82-99 (1982) · Zbl 0491.65025
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.