In queueing models, a discipline within the mathematical theory of probability, the quasi-birth–death process describes a generalisation of the birth–death process.[1] [2] As with the birth-death process it moves up and down between levels one at a time, but the time between these transitions can have a more complicated distribution encoded in the blocks.
The stochastic matrix describing the Markov chain has block structure[3]
| \ast | |
| P=\begin{pmatrix} A | |
| 1 |
&
| \ast | |
| A | |
| 2 |
| \ast | |
| \\ A | |
| 0 |
&A1&A2\\ &A0&A1&A2\\ &&A0&A1&A2\\ &&&\ddots&\ddots&\ddots \end{pmatrix}
where each of A0, A1 and A2 are matrices and A*0, A*1 and A*2 are irregular matrices for the first and second levels.[4]
The transition rate matrix for a quasi-birth-death process has a tridiagonal block structure
Q=\begin{pmatrix} B00&B01\\ B10&A1&A2\\ &A0&A1&A2\\ &&A0&A1&A2\\ &&&A0&A1&A2\\ &&&&\ddots&\ddots&\ddots \end{pmatrix}
where each of B00, B01, B10, A0, A1 and A2 are matrices.[5] The process can be viewed as a two dimensional chain where the block structure are called levels and the intra-block structure phases.[6] When describing the process by both level and phase it is a continuous-time Markov chain, but when considering levels only it is a semi-Markov process (as transition times are then not exponentially distributed).
Usually the blocks have finitely many phases, but models like the Jackson network can be considered as quasi-birth-death processes with infinitely (but countably) many phases.[7]
The stationary distribution of a quasi-birth-death process can be computed using the matrix geometric method.