On optimal condition numbers for markov chains

Let T and T̃ = T-E 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 Mathematc expression. 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 τp(A#) = sup Mathematic expression, 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, κ 3 and κ 6 in the Cho-Meyer list of 8 condition numbers. Kirkland has studied κ 3(T). He has shown that Mathematic expression and he has characterized transition matrices for which equality holds. We prove here again that 2κ 3(T) ≥ κ(6) which appears in the Cho-Meyer paper and we characterize the transition matrices T for which Mathematic expression. 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.