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

We apply physical interpretations to construct algorithms for the key matrix 𝐆 in discrete-time quasi-birth-and-death (dtQBD) and its 𝓏-transform 𝐆(𝓏), motivated by the work on stochastic fluid models (SFMs) in [13]. In this methodology, we first write a summation expression for 𝐆(𝓏) by considering a physical interpretation similar to that of an algorithm in [13]. Next, we construct the corresponding iterative scheme, and prove its convergence to 𝐆(𝓏).

In particular, here we consider the physical interpretation of Algorithm 1 for 𝚿(𝑠) in [13], and use a similar physical interpretation for 𝐆(𝓏) partitioned into three sections, each expressed in terms of matrices analogous to block matrices in the fluid generator 𝐐(𝑠) in stochastic fluid models.