Transition matrices for well-conditioned Markov chains

AbstractLet T∈Rn×n be an irreducible stochastic matrix with stationary distribution vector π. Set A=I−T, and define the quantity κ3(T)≡12maxj=1,…,nπj‖Aj-1‖∞, where Aj, j=1,…,n, are the (n−1)×(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 κ3 provides a sensitive measure of the conditioning of π under perturbation of T. Moreover, it is known that κ3(T)⩾n-12n.In this paper, we investigate the class of irreducible stochastic matrices T of order n such that κ3(T)=n-12n, 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 κ3 is as small as possible