ELA, Volume 11, pp. 168-179, July 2004, abstract.

A Combinatorial Approach to the Conditioning of a 
Single Entry in the Stationary Distribution for a 
Markov Chain

S. Kirkland

For an irreducible stochastic matrix T of order 
n, a certain condition number k_j(T) that 
measures the sensitivity of the jth 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 for which k_j is bounded, a tight upper 
bound is given on k_j in terms of information 
contained in D.