eCite Digital Repository

Construction of algorithms for discrete-time quasi-birth-and-death processes through physical interpretation


Samuelson, A and O'Reilly, MM and Bean, NG, Construction of algorithms for discrete-time quasi-birth-and-death processes through physical interpretation, Stochastic Models pp. 1-30. ISSN 1532-6349 (2020) [Refereed Article]

Copyright Statement

Copyright 2020 Taylor & Francis Group, LLC

DOI: doi:10.1080/15326349.2020.1744451


We apply physical interpretations to construct algorithms for the key matrix G of discrete-time quasi-birth-and-death (dtQBD) processes which records the probability of the process reaching level (n-1) for the first time given the process starts in level n. The construction of G and its z-transform 𝐆(𝓏) was motivated by the work on stochastic fluid models (SFMs). In this methodology, we first write a summation expression for 𝐆(𝓏) by considering a physical interpretation similar to that of an algorithm. Next, we construct the corresponding iterative scheme, and prove its convergence to 𝐆(𝓏).

We construct in detail two algorithms for G(𝓏) one of which we show is Newton's Method. We then generate a comprehensive set of algorithms, an additional one of which is quadratically convergent and has not been seen in the literature before. Using symmetry arguments, we generate analogous algorithms for 𝐑(𝓏) and again find that two are quadratically convergent. One of these can be seen to be equivalent to applying Newton's Method to evaluate 𝐑(𝓏) and the other is again novel.

Item Details

Item Type:Refereed Article
Keywords:matrix analytic methods, quasi-birth-and-death processes, matrix G, algorithms, discrete-time quasi-birth-and-death, physical interpretation
Research Division:Mathematical Sciences
Research Group:Statistics
Research Field:Stochastic analysis and modelling
Objective Division:Expanding Knowledge
Objective Group:Expanding knowledge
Objective Field:Expanding knowledge in the mathematical sciences
UTAS Author:Samuelson, A (Ms Aviva Samuelson)
UTAS Author:O'Reilly, MM (Associate Professor Malgorzata O'Reilly)
ID Code:138392
Year Published:2020
Funding Support:Australian Research Council (LP140100152)
Deposited By:Mathematics
Deposited On:2020-04-06
Last Modified:2020-07-09

Repository Staff Only: item control page