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

Abstract

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 $\mathbf{G}(z)$ was motivated by the work on stochastic fluid models (SFMs). In this methodology, we first write a summation expression for $\mathbf{G}(z)$ by considering a physical interpretation similar to that of an algorithm. Next, we construct the corresponding iterative scheme, and prove its convergence to $\mathbf{G}(z).$

We construct in detail two algorithms for $\mathbf{G}(z),$ 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 $\mathbf{R}(z)$ and again find that two are quadratically convergent. One of these can be seen to be equivalent to applying Newton’s Method to evaluate $\mathbf{R}(z),$ and the other is again novel.

Keywords:

• Matrix analytic methods
• quasi-birth-and-death processes
• matrix G

Additional information

Funding

The second author would like to thank the Australian Research Council for funding this research through Linkage Project LP140100152.