On optimal condition numbers for Markov chains (Q957931)

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.