An iterative approximation scheme for repetitive Markov processes

Tufekci T., Gullu R.

JOURNAL OF APPLIED PROBABILITY, vol.36, no.3, pp.654-667, 1999 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 36 Issue: 3
  • Publication Date: 1999
  • Doi Number: 10.1239/jap/1032374624
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.654-667
  • Middle East Technical University Affiliated: No


Repetitive Markov processes form a class of processes where the generator matrix has a particular repeating form. Many queueing models fall in this category such as M/M/1 queues, quasi-birth-and-death processes, and processes with M/G/1 or GI/M/1 generator matrices. in this paper, a new iterative scheme is proposed for computing the stationary probabilities of such processes. An infinite state process is approximated by a finite state process by lumping an infinite number of states into a super-state. What we call the feedback rate, the conditional expected rate of flow from the super-state to the remaining states, given the process is in the super-state, is approximated simultaneously with the steady state probabilities. The method is theoretically developed and numerically tested for quasi-birth-and-death processes. It turns out that the new concept of the feedback rate can be effectively used in computing the stationary probabilities.