On optimal condition numbers for Markov chains

Let T and be arbitrary nonnegative, irreducible, stochastic matrices corresponding to two ergodic Markov chains on n states. A function κ is called a condition number for Markov chains with respect to the (α, β)–norm pair if . Here π and are the stationary distribution vectors of the two chains, respectively. Various condition numbers, particularly with respect to the (1, ∞) and (∞, ∞)-norm pairs have been suggested in the literature. They were ranked according to their size by Cho and Meyer in a paper from 2001. In this paper we first of all show that what we call the generalized ergodicity coefficient , 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, ∞)-norm pair. We use this result to identify the smallest condition number of Markov chains among the (∞, ∞) and (1, ∞)-norm pairs. These are, respectively, κ ₃ and κ ₆ in the Cho–Meyer list of 8 condition numbers. Kirkland has studied κ ₃(T). He has shown that and he has characterized transition matrices for which equality holds. We prove here again that 2κ ₃(T) ≤ κ(6) which appears in the Cho–Meyer paper and we characterize the transition matrices T for which . There is actually only one such matrix: T = (J _n  − I)/(n − 1), where J _n is the n × n matrix of all 1’s. This research was supported in part by NSERC under Grant OGP0138251 and NSA Grant No. 06G–232.