In queueing models, a discipline within the mathematical theory of probability, the quasi-birth–death process describes a generalisation of the birth–death process. 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.
Discrete time The stochastic matrix describing the Markov chain has block structure
P = ( A 1 ∗ A 2 ∗ A 0 ∗ A 1 A 2 A 0 A 1 A 2 A 0 A 1 A 2 ⋱ ⋱ ⋱ ) {\displaystyle P={\begin{pmatrix}A_{1}^{\ast }&A_{2}^{\ast }\\A_{0}^{\ast }&A_{1}&A_{2}\\&A_{0}&A_{1}&A_{2}\\&&A_{0}&A_{1}&A_{2}\\&&&\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.
Continuous time The transition rate matrix for a quasi-birth-death process has a tridiagonal block structure
Q = ( B 00 B 01 B 10 A 1 A 2 A 0 A 1 A 2 A 0 A 1 A 2 A 0 A 1 A 2 ⋱ ⋱ ⋱ ) {\displaystyle Q={\begin{pmatrix}B_{00}&B_{01}\\B_{10}&A_{1}&A_{2}\\&A_{0}&A_{1}&A_{2}\\&&A_{0}&A_{1}&A_{2}\\&&&A_{0}&A_{1}&A_{2}\\&&&&\ddots &\ddots &\ddots \end{pmatrix}}}
where each of B00, B01, B10, A0, A1 and A2 are matrices. The process can be viewed as a two dimensional chain where the block structure are called levels and the intra-block structure phases. 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.
Stationary distribution The stationary distribution of a quasi-birth-death process can be computed using the matrix geometric method.
References