A logarithmic reduction algorithm for quasi-birth-death processes. (English) Zbl 0789.60055

A QBD is a Markov chain with state space \(Z_ + \times \{1,2,\dots,m\}\), and transition matrix \(P\): \[ P((i,j);(h,k))=0,| i-h |>1;\qquad P((i,j);(h,k))=A_{i-h+1}(j;k),| h-k | \leq 1; \] with the exception \(P((0,j);(0,k))=C_ 1(j;k)\); \(Z=\{0,1,2,\dots\}.\) The analysis is facilitated by the matrices \(R,G,U\), the minimal nonnegative solutions of \[ \left( \begin{matrix} G= & A_ 2+A_ 1G+A_ 0G^ 2, \\ R= & A_ 0+RA_ 1+R^ 2A_ 2, \\ U= & A_ 1+A_ 0(1-U)^{-1}A_ 2. \end{matrix} \right) \] Based on their probabilistic meaning, the authors propose a new simple algorithm for these matrices and show the quadratic convergence. Numerical examples also support their claim that the algorithm provides extremely accurate and fast results even for almost unstable models.
Reviewer: W.-Z.Yang (Taipei)


60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
65C99 Probabilistic methods, stochastic differential equations
60J05 Discrete-time Markov processes on general state spaces
60K25 Queueing theory (aspects of probability theory)
Full Text: DOI