BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//NA-M-85-32
       ENTRY:: January 28, 1996
ORGANIZATION:: Stanford University, Department of Computer Science, Numerical
               Analysis Project
       TITLE:: Simultaneous computation of stationary probabilities with
               estimates of their sensitivity
        TYPE:: Manuscript
      AUTHOR:: Golub, Gene H.
      AUTHOR:: Meyer, Carl D. Jr.
        DATE:: March 1985
       PAGES:: 30
    ABSTRACT:: For an n-state finite, homogeneous, ergodic Markov chain with
               transition matrix P = [$p_{ij}$], the stationary distribution
               is the unique row vector $\pi$ satisfying $\pi P = \pi , \sum
               {\pi}_i\ = 1$. Letting $A_{n\times n}$ and $e_{n\times 1}$
               denote the matrices A = I - P and e = ${[1, 1, ..., 1]}^T$,
               the stationary distribution $\pi$ can be characterized as the
               unique solution to the linear system of equations defined by
               $\pi$A = 0 and $\pi$e = 1.

               The theory of finite Markov chains has long been a
               fundamental tool in the analysis of social and biological
               phenomena. More recently the ideas embodied in Markov chain
               models along with the analysis of a stationary distribution
               have proven to be useful in applications which do not fall
               directly into the traditional Markov chain setting. Some of
               these applications include the analysis of queueing networks
               (Kaufman [1984]), the analysis of compartmental ecological
               models (Funderlic and Mankin [1981]), and least squares
               adjustment of geodedic networks (Brandt [1983]). Recently,
               the behavior of the numerical solution of systems of
               nonlinear reaction-diffusion equations has been analyzed by
               making use of the stationary distribution of a finite Markov
               chain in conjunction with the concept of group matrix
               inversion (Galeone [1983]).

               An ergodic chain manifests itself in the transition matrix P
               which must be row stochastic and irreducible. Of central
               importance is the sensitivity of the stationary distribution
               $\pi$ to perturbations in the transition probabilities in P.
               The sensitivity of $\pi$ is most easily gauged by considering
               the transition probabilities in P to be differentiable
               functions. One approach, adopted by Conlisk [preprint, 1983],
               Schweitzer [1968], and Funderlic and Heath [1971] is to
               examine partial derivatives $\delta\pi /\delta p_{ij}$. Our
               strategy is to consider the transition probabilities
               $p_{ij}$(t) as differentiable functions of a single parameter
               t and study the stationary distribution $\pi$(t) as a
               function of t. We present a new and very simple formulation
               for the derivative, d$\pi$(t)/dt, of the stationary
               distribution directly in terms of the derivatives
               d$p_{ij}$(t)/dt and entries from $\pi$(t) and a matrix
               $A^#$(t), called the group inverse of A(t) = I - P(t). After
               the derivative d$\pi$(t)/dt has been obtained, we demonstrate
               its applicability by using it to deduce the relative
               sensitivity of a discrete Markov chain. This is followed by a
               first order perturbation analysis. Finally, it is
               demonstrated how a QR factorization can be used to
               simultaneously compute $\pi$ along with estimates which gauge
               the sensitivity of $\pi$ to perturbations in P.
       NOTES:: [Adminitrivia V1/Prg/19960128]
         END:: STAN//NA-M-85-32