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.