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

<p>We apply physical interpretations to construct algorithms for the key matrix <strong>G</strong> 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 <strong>G</strong> and its <i>z</i>-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 ��(��).</p> <p>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.</p>