Algorithms for finding steady state probabilities for some special classes of finite state Markov chains (Q1091951)

This paper considers irreducible, aperiodic, positive recurrent finite Markov chains, with probability transitions matrices denoted by P, and the problem of computing the steady state probability vector i.e. the solution x to the equations \(xP=x\), \(xe=1\), \(x\geq 0\). Two special classes of matrix P are considered, viz. I.) In this case, with an appropriate permutation of the states, and by replacing the first equation of \(xP=x\) by \(xe=1\), the equations can be written in the form \(xZ=\delta_ n(1)\) where \(\delta_ n(1)\in R^ n\), and has a one in the first position, and zeros elsewhere and \[ Z= \left[\begin{matrix} Z_{11}& Z_{12}&...& Z_{1,k+1}& 0&...& 0 \\ Z_{21}& Z_{22}&...& Z_{2,k+1}& Z_{2,k+2}&...& 0 \\ \vdots & \vdots && \vdots & \vdots && \vdots \\ Z_{N-k,1}& Z_{N-k,2}&...& Z_{N-k,k+1}& Z_{N-k,k+2}&...& Z_{N-k,N} \\ \vdots & \vdots && \vdots & \vdots && \vdots \\ Z_{N,1}& Z_{N,2}& ...& Z_{N,k+1}& Z_{N,k+2}& ...& Z_{N,N} \end{matrix}\right] \] and where \(Z_{ij}\) are \(m\times m\) matrices, with \(Z_{i,k+i}\) \((i=1,2,...,N-K)\) being invertible. II) This is similar to I, being reducible to the form \(xZ=\delta_ n(\rho)\) but Z takes the form \(Z=L+U\), where L, U are respectively, lower and upper block triangular matrices, L has invertible diagonal block matrices, and L has all zero block columns, \(\delta_ n(\rho)\) has ones in specified places, and zeros elsewhere, and the zero block columns of U correspond to the ones on \(\delta_ n(p)\). Queueing examples are given which fit this situation. With an appropriate partition of x and Z in case I, the equations reduce to \(x_ 1A+ x_ 2C=\delta_{mk}(1)\) \((=(1,0,0,...,0))\) and \(x_ 1B+x_ 2D=0\). These have the solution \(x_ 1=-x_ 2DB^{-1}\), where \(x_ 2\) is the unique solution to \(x_ 2(C-DB^{- 1})=\delta_{mk}(1)\). A similar analysis is given for class II processes. Algorithms are given and their complexity compared with Gaussian elimination.