Transition matrices for well-conditioned Markov chains

Let T is an element of R-n x n bean irreducible stochastic matrix with stationary distribution vector pi. Set A = 1 - T, and define the quantity kappa(3)(T) = 1/2 max(j=1......n) pi(j)parallel to A(j)(-1)parallel to(infinity), where A(j), j = 1,...,n, are the (n - 1) x (n - 1) principal submatrices of A obtained by deleting the jth row and column of A. Results of Cho and Meyer, and of Kirkland show that kappa(3) provides a sensitive measure of the conditioning of 7 under perturbation of T. Moreover, it is known that kappa(3) (T) >= n-1/2n. In this paper, we investigate the class of irreducible stochastic matrices T of order it such that K3 (T) n-1/2n, for such matrices correspond to Markov chains with desirable conditioning properties. We identify some restrictions on the zero-nonzero patterns of such matrices, and construct several infinite classes of matrices for which kappa(3) is as small as possible. (C) 2006 Elsevier Inc. All rights reserved.