Definition of QBD process

In general, a QBD process is a Markov chain on the state space $\{ (i,\ell) \vert 1\leq i \leq n_\ell, \ell\geq 0\}$, where the state space can be divided into levels, and level $\ell$ has $n_\ell$ states (phases) for each $\ell$^3.2. For example, in Figure 3.8(b), $n_0=1$ and $n_\ell=2$ for $\ell\geq 1$. In a QBD process, transitions are allowed only to the neighboring levels or within the same level. Thus, a QBD process has a generator matrix of the form:

$$\mathbf{Q} = \left(\begin{array}{lllll} \mathbf{L}^{(0)}& \m... ...}^{(2)}& \\ & & \ddots & \ddots & \ddots \end{array}\right),$$ (3.2)

where submatrix $\mathbf{F}^{(\ell)}$ encodes (forward) transitions from level (column) $\ell$ to level $\ell+1$ for $\ell\geq 0$, submatrix $\mathbf{B}^{(\ell)}$ encodes (backward) transitions from level $\ell$ to level $\ell-1$ for $\ell\geq 1$, and submatrix $\mathbf{L}^{(\ell)}$ encodes (local) transitions within level $\ell$ for $\ell\geq 0$. Specifically, ($i,j$) element of $\mathbf{F}^{(\ell)}$ is the transition rate from state $(i,\ell)$, i.e. phase $i$ of level $\ell$, to state $(j,\ell+1)$ for all $i,j$; ($i,j$) element of $\mathbf{B}^{(\ell)}$ is the transition rate from state $(i,\ell)$ to state $(j,\ell-1)$ for all $i,j$; ($i,j$) element of $\mathbf{L}^{(\ell)}$ is the transition rate from state $(i,\ell)$ to state $(j,\ell)$ for $i\neq j$.

For example, in Figure 3.8(b),

$$\begin{eqnarray*} \mathbf{F}^{(0)} & = & \left(\begin{array}{cc} \lambda & 0 \... ...-(\mu+\lambda) \end{array}\right) \quad\mbox{for } \ell\geq 1. \end{eqnarray*}$$