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 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.