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

Main Article Content

Stephen J. Kirkland


For an irreducible stochastic matrix T of order n, a certain condition number Kj(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 Kj 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 Kj(T) is bounded from above as T ranges over the set of irreducible stochastic matrices having directed graph D. For those D which Kj is bounded, a tight upper bound is given on Kj in terms of information contained in D. 

Article Details