Examples of QBD processes

We start by providing canonical examples of QBD processes. Here, we provide both pictorial explanation and more formal explanation. Pictorial explanation gives intuitive understanding of the QBD process, and more formal explanation allows us to get used to the notation that we use later.

First, a birth-and-death process is an example of a QBD process. Figure 3.8(a) shows an example of a birth-and-death process. This birth-and-death process models the number of jobs in an M/M/1 queue, where jobs arrive according to a Poisson process with rate $\lambda$, and the service demand has an exponential distribution with rate $\mu$. In general, a birth-and-death process is a Markov chain on the states $\{0,1,2,3,...\}$, where transitions are allowed only to the neighboring states. That is, from state $\ell$, there are transitions only to state $\ell-1$ and state $\ell+1$ for $\ell\geq 1$, and from state 0, there is a transition only to state 1. Thus, the generator matrix of a birth-and-death process is of the form:

$$\mathbf{Q} = \left(\begin{array}{cccc} -f_0 & f_0 & & \\ b_... ...b_2+f_2) & \ddots \\ & & \ddots & \ddots \end{array}\right),$$ (3.1)

where $f_\ell$ denotes the (foreword) transition from state $\ell$ to state $\ell+1$, and $b_\ell$ denotes the (backward) transition from state $\ell$ to state $\ell-1$. In Figure 3.8(a), $f_\ell = \lambda$ and $b_\ell=\mu$ for all $\ell$.

Figure 3.8: Examples of QBD processes.

(a) birth-and-death process

(b) QBD process

Figure 3.8(b) shows an example of a QBD process that is not a birth-and-death process. This QBD process models the number of jobs in a M/Er/1 queue, where jobs arrive according to a Poisson process with rate $\lambda$, and their service demand has an Erlang-2 distribution (as defined in Section 2.2), which has parameters

$$\Vec{\tau}=(1,0)\quad\mbox{and}\quad \mathbf{T} = \left(\begin{array}{cc} -\mu & \mu\\ 0 & -\mu \end{array}\right).$$

That is, a job is in phase 1 when it arrives. After a job in phase 1 receives service for a random time having an exponential distribution with rate $\mu$, the job transitions into phase 2. After a job in phase 2 receives service for a random time having an exponential distribution with rate $\mu$, the job is completed.