Quasi-birth–death Process

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=\begin 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$

where each of ''A''₀, ''A''₁ and ''A''₂ are matrices and ''A''*₀, ''A''*₁ and ''A''*₂ 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=\begin B_ & B_ \\ B_ & 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$

where each of ''B''₀₀, ''B''₀₁, ''B''₁₀, ''A''₀, ''A''₁ and ''A''₂ 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

Queueing theory
Markov processes

{{probability-stub