Digraph-based conditioning for Markov chains Original Research Article

For an irreducible stochastic matrix T, we consider a certain condition number c(T), which measures the stability of the corresponding stationary distribution when T is perturbed. We characterize the strongly connected directed graphs D such that c(T) is bounded as T ranges over image, the set of stochastic matrices whose directed graph is contained in D. For those digraphs D for which c(T) is bounded, we find the maximum value of c(T) as T ranges over image.