On optimal condition numbers for Markov chains
type: Item
instance of: scholarly article
title: On optimal condition numbers for Markov chains
zbMATH Open document ID: 1160.60022
author: S. J. Kirkland
author: M. Neumann
author: Nung-Sing Sze
published in: Numerische Mathematik
publication date: 2008-12-01T00:00:00Z
review text: 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 \textit{G. E. Cho} and \textit{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.
reviewed by: Alex V. Kolnogorov
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 15B51
Mathematics Subject Classification ID: 15A12
zbMATH DE Number: 5376034
zbMATH Keywords: finite Markov chains
zbMATH Keywords: perturbation bounds
zbMATH Keywords: condition numbers
zbMATH Keywords: ergodicity coefficients
MaRDI profile type: Publication
full work available at URL: s00211-008-0172-8
OpenAlex ID: W2083936573
cites work: Using Gauss-Jordan elimination to compute the index, generalized nullspaces, and Drazin inverse
cites work: Generalized inverses. Theory and applications.
cites work: Q4326384
cites work: Q4002435
cites work: Markov chain sensitivity measured by mean first passage times
cites work: Comparison of perturbation bounds for the stationary distribution of a Markov chain
cites work: Q5512461
cites work: Sensitivity of the stationary distribution vector for an ergodic Markov chain
cites work: Using the QR Factorization and Group Inversion to Compute, Differentiate, and Estimate the Sensitivity of Stationary Probabilities for Markov Chains
cites work: On the structure of stochastic matrices with a subdominant eigenvalue near 1
cites work: Q3907685
cites work: Perturbation bounds for the stationary probabilities of a finite Markov chain
cites work: Q4281292
cites work: Uniform Stability of Markov Chains
cites work: Q3262596
cites work: On a question concerning condition numbers for Markov chains
cites work: The case of equality in the Dobrushin-Deutsch-Zenger bound
cites work: Applications of Paz's inequality to perturbation bounds for Markov chains
cites work: Transition matrices for well-conditioned Markov chains
cites work: The Role of the Group Generalized Inverse in the Theory of Finite Markov Chains
cites work: The Condition of a Finite Markov Chain and Perturbation Bounds for the Limiting Probabilities
cites work: Sensitivity of the Stationary Distribution of a Markov Chain
cites work: Q4485695
cites work: Updating finite markov chains by using techniques of group matrix inversion
cites work: Upper bounds on the maximum modulus of subdominant eigenvalues of nonnegative matrices
cites work: Perturbation theory and finite Markov chains
cites work: Non-negative matrices and Markov chains. 2nd ed
cites work: Perturbation of the stationary distribution measured by ergodicity coefficients
cites work: Q3976664
cites work: Q4281294
cites work: Q4947421
cites work: Q3953090
DOI: 10.1007/S00211-008-0172-8
Recommended article: On a question concerning condition numbers for Markov chains
Recommended article: Improved bounds for a condition number for Markov chains
Recommended article: Finding provably optimal Markov chains
Recommended article: On improved bounds and conditions for the convergence of Markov chains
Recommended article: Markov Chains and Optimality of the Hamiltonian Cycle
Recommended article: Q3990174
Recommended article: Q3363885
Recommended article: On transience conditions for Markov chains
Recommended article: Some bounds for Markov chains
description: scientific article; zbMATH DE number 5376034