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.[1][2]:118 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.

## Contents

* 1 Discrete time
* 2 Continuous time
* 2.1 Stationary distribution
* 3 References

## Discrete time

The stochastic matrix describing the Markov chain has block structure[3]

[math]\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} }[/math]

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]

## Continuous time

The transition rate matrix for a quasi-birth-death process has a tridiagonal block structure

[math]\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} }[/math]

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.[6][7]

### Stationary distribution

The stationary distribution of a quasi-birth-death process can be computed using the matrix geometric method.

## References

1. ↑ Latouche, G. (2011). "Level-Independent Quasi-Birth-and-Death Processes". Wiley Encyclopedia of Operations Research and Management Science. doi:10.1002/9780470400531.eorms0461. ISBN 9780470400531.
2. ↑ Gautam, Natarajan (2012). Analysis of Queues: Methods and Applications. CRC Press. ISBN 9781439806586.
3. ↑ Latouche, G.; Pearce, C. E. M.; Taylor, P. G. (1998). "Invariant measures for quasi-birth-and-death processes". Communications in Statistics. Stochastic Models 14: 443. doi:10.1080/15326349808807481.
4. ↑ Palugya, S. N.; Csorba, M. T. J. (2005). "Modeling Access Control Lists with Discrete-Time Quasi Birth-Death Processes". Computer and Information Sciences - ISCIS 2005. Lecture Notes in Computer Science. 3733. pp. 234. doi:10.1007/11569596_26. ISBN 978-3-540-29414-6.
5. ↑ Asmussen, S. R. (2003). "Markov Additive Models". Applied Probability and Queues. Stochastic Modelling and Applied Probability. 51. pp. 302–339. doi:10.1007/0-387-21525-5_11. ISBN 978-0-387-00211-8.
6. ↑ 6.0 6.1 Kroese, D. P.; Scheinhardt, W. R. W.; Taylor, P. G. (2004). "Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process". The Annals of Applied Probability 14 (4): 2057. doi:10.1214/105051604000000477.
7. ↑ Motyer, A. J.; Taylor, P. G. (2006). "Decay rates for quasi-birth-and-death processes with countably many phases and tridiagonal block generators". Advances in Applied Probability 38 (2): 522. doi:10.1239/aap/1151337083.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Quasi-birth–death process. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Quasi-birth–death_process&oldid=36385"