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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Algorithms for finding steady state probabilities for some special classes of finite state Markov chains
scientific article

    Statements

    Algorithms for finding steady state probabilities for some special classes of finite state Markov chains (English)
    0 references
    0 references
    0 references
    1986
    0 references
    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.
    0 references
    Gaussian elimination method
    0 references
    algorithmic methods
    0 references
    irreducible, aperiodic, positive recurrent finite Markov chains
    0 references
    steady state probability vector
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references