A combinatorial approach to the conditioning of a single entry in the stationary distribution for a Markov chain

Abstract

For an irreducible stochastic matrix T of order n, a certain condition number K_j(T) that measures the sensitivity of the j-th entry of the corresponding stationary distribution under perturbation of T is considered. A lower bound on K_j is produced in terms of the directed graph of T, and the case of equality is characterized in that lower bound. Also all of the directed graphs D are characterized such that K_j(T) is bounded from above as T ranges over the set of irreducible stochastic matrices having directed graph D. For those D which K_j is bounded, a tight upper bound is given on K_j in terms of information contained in D.