Generalization

So far, we have derived the first passage time from level $\ell$ to level $\ell-1$. In this section, we extend this to the first passage time from level $\ell$ to level $\ell-\psi$ for $1\leq \psi \leq\ell$. Let $T_{i,j}^{(\ell,\ell-\psi)}$ be the time to go from state $(i,\ell)$ to state $(j,\ell-\psi)$, and let $E_{i,j}^{(\ell,\ell-\psi)}$ be the event that state $(j,\ell-\psi)$ is the first state reached in level $\ell-\psi$ when starting in state $(i,\ell)$, for $1\leq \psi \leq\ell$. Observe that $T_{i,j}^{(\ell,\ell-1)}=T_{i,j}^{(\ell)}$ and $E_{i,j}^{(\ell,\ell-1)}=E_{i,j}^{(\ell)}$. Then, our goal is to derive the $n_\ell \times n_{\ell - \psi}$ matrix, ${\mathbf{Z}}^{(\ell,\ell-\psi)}_r$, where $({\mathbf{Z}}^{(\ell,\ell-\psi)}_r)_{i,j}$ is the $r$-th moment of $T^{(\ell,\ell-\psi)}_{i,j}$ given event $E^{(\ell,\ell-\psi)}_{i,j}$, for each $\ell$, $r=1,2,3$, and $1\leq \psi \leq\ell$. Notice that ${\mathbf{Z}}^{(\ell,\ell-1)}_r = \mathbf{Z}_r^{(\ell)}$.

Observe that

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

Hence, it suffices to derive two quantities:

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

for $1\leq \psi \leq\ell$.

Matrices $\mathbf{G}^{(\ell,\ell-\psi)}$ and $\mathbf{G}^{(\ell,\ell-\psi)}_r$ can be derived recursively from

$$\mathbf{G}^{(\ell,\ell-1)} = \mathbf{G}^{(\ell)} \quad\mbox{and}\quad \mathbf{G}^{(\ell,\ell-1)}_r = \mathbf{G}^{(\ell)}_r$$

via

$$\begin{eqnarray*} \mathbf{G}^{(\ell,\ell-\psi)} & = & \mathbf{G}^{(\ell)} \math... ...\psi)} + \mathbf{G}_3^{(\ell)} \mathbf{G}^{(\ell-1,\ell-\psi)}. \end{eqnarray*}$$

Finally, we mention some other generalizations that Neuts' algorithm allows. (i) We restricted ourselves to the first three moments, but this approach can be generalized to any higher moments. (ii) We restricted to QBD processes, but this can be generalized to M/G/1 type semi-Markov processes. (iii) We restricted ourselves to the moments of the distribution of the duration of busy periods, but this can be generalized to the moments of the joint distribution of the duration of a busy period and the number of transitions during the busy period.