Moments of inter-level passage times in QBD processes

Neuts' algorithm [134,137] is an efficient algorithm that calculates the moments of various types of passage times in very general processes, i.e. M/G/1 type semi-Markov processes. Because of its generality, however, the description of the algorithm in [134,137] is sophisticated. The purpose of this section is to make Neuts' algorithm more accessible to general readers by re-describing his algorithm restricted to the first three moments of inter-level passage times in QBD processes. We omit all proofs, which are provided in detail in [134], and we instead focus on intuition and interpretation. We include everything needed to apply Neuts' algorithm within our solution framework, so that general readers can apply our methodology.

Specifically, we consider a QBD process on the state space $\{ (i,\ell) \vert 1\leq i \leq n_\ell, \ell\geq 0\}$, which has generator matrix $\mathbf{Q}$:

$$\mathbf{Q} = \left(\begin{array}{cccccc} \mathbf{L}^{(0)} & ... ... & \mathbf{F}^{(2)}\\ & & \ddots & \ddots \end{array}\right)$$

as defined in Section 3.2. We assume that the QBD process repeats after level $\hat\ell$; i.e. $\mathbf{B^{(\ell)}}=\mathbf{B}$, $\mathbf{L^{(\ell)}} = \mathbf{L}$, and $\mathbf{F^{(\ell)}} = \mathbf{F}$ for all $\ell\geq\hat\ell$.

Our goal can be roughly stated as deriving the passage time required to get from state $(i,\ell)$ to level $\ell-1$ conditioned on the particular state first reached in level $\ell-1$. To state our goal more precisely, let $E^{(\ell)}_{i,j}$ be the event that state $(j,\ell-1)$ is the first state reached in level $\ell-1$ when starting in $(i,\ell)$, and let $T^{(\ell)}_{i,j}$ be the time to go from state $(i,\ell)$ to state $(j,\ell-1)$. Then, our goal is to derive the $n_\ell \times n_{\ell - 1}$ matrix, ${\mathbf{Z}}^{(\ell)}_r$, where $({\mathbf{Z}}^{(\ell)}_r)_{i,j}$ is the $r$-th moment of $T^{(\ell)}_{i,j}$ given event $E^{(\ell)}_{i,j}$, for each $\ell$ and $r=1,2,3.$

Observe that

$$\begin{eqnarray*} ({\mathbf{Z}}^{(\ell)}_r)_{i,j} & = & \int_0^\infty x^r d\Pr\... ...} E^{(\ell)}_{i,j} \right)} {\Pr\left(E^{(\ell)}_{i,j}\right)}. \end{eqnarray*}$$

Hence, it suffices to derive two quantities:

$$\begin{eqnarray*} (\mathbf{G}^{(\ell)})_{i,j} & \equiv & \Pr\left(E^{(\ell)}_{i,... ...ft(T^{(\ell)}_{i,j} \leq x \mbox{ AND } E^{(\ell)}_{i,j} \right) \end{eqnarray*}$$

The rest of this section is organized as follows. In Section 3.7.1, we introduce some notations that we will need along the way. In Section 3.7.2, we derive $\mathbf{G}^{(\ell)}$ and $\mathbf{G}_r^{(\ell)}$ for each $\ell$ and $r=1,2,3$. (Matrix $\mathbf{G}^{(\ell)}$ can also be obtained by the algorithm in Figure 3.12.) In Section 3.7.3, we mention some generalizations that Neuts' algorithm allows. In particular, we show an extension to the passage time from level $\ell$ to level $\ell-\psi$ for $1\leq \psi \leq\ell$, which we will need in Section 3.8.