Analysis of the FB process

In this section, we extend the analysis in Section 3.5.1 to the general FB process. As in Section 3.5.1, once the background process is approximated by a Markov chain on a finite state space, it is straightforward to reduce the FB process to a 1D Markov chain. Hence, in this section, we limit our focus on approximating the background process by a Markov chain on a finite state space; for completeness, we formally describe the construction of the 1D Markov chain using the approximated background process in Appendix 3.5.5. We will see that, in general, a collection of PH distributions is needed in the approximate background process, $\widetilde B$, (e.g. recall Section 3.1.2) to capture the dependency in the sequence of sojourn times in levels $\geq\kappa$ that $B$ has. This is in contrast to the case when the background process is a birth-and-death process, which required only a single PH distribution in the approximate background process, since the sojourn times in levels $\geq\kappa$ are i.i.d. in this case. Below, we use $\mathbf{Q}_b$ to denote the generator matrix of $B$, and use $\mathbf{B}_b^{(\ell)}$, $\mathbf{L}_b^{(\ell)}$, and $\mathbf{F}_b^{(\ell)}$ to denote the submatrices of $\mathbf{Q}_b$, following the convention introduced in Section 3.4

We start by specifying the properties that $\widetilde B$ should have. Let $E_{i,j}$ be the event that the first state that we visit in level $\kappa-1$ is in phase $j$ given that we transitioned from phase $i$ in level $\kappa-1$ to any state in level $\kappa$. (Notice that in the analysis of the M/PH/2 queue with two priority classes in Section 3.1, each event $E_{i,j}$ corresponds to the event that the phase of the job in service immediately before a busy period starts is $i$ and the phase of the job in service immediately after the busy period is $j$.) We require that $\widetilde B$ has the following key properties:

• The probability of event $E_{i,j}$ in $\widetilde B$ is the same as that in $B$ for each $i$ and $j$.
• The distribution of the sojourn time in levels $\geq\kappa$ given event $E_{i,j}$ in $\widetilde B$ well-represents that in $B$ (i.e. the first three moments of the two distributions agree) for each $i$ and $j$.

Observe that if the second property did not involve the approximation, then the foreground process that depends on background process $B$ and the foreground process that depends on background process $\widetilde B$ would be stochastically equivalent. This is because the sequence of the sojourn times between changing levels (0, 1, ..., $\kappa-1$, and $\geq\kappa$) in $B$ and that in $\widetilde B$ would be stochastically equivalent.

To construct $\widetilde B$, we first analyze the probability of event $E_{i,j}$ and (the moments of) the distribution of the sojourn time in levels $\geq\kappa$ given event $E_{i,j}$ (we denote this distribution as $D_{i,j}$) for each $i$ and $j$. (Notice that in the analysis of the M/PH/2 queue with two priority classes in Section 3.1, $D_{i,j}$ corresponds to the distribution of the busy period duration given that the phase of the job in service immediately before a busy period starts is $i$ and the phase of the job in service immediately after the busy period is $j$.) Let $\xi$ be the number of phases in level $\kappa-1$ of $B$ (and $\widetilde B$). Then, there are $\xi^2$ types of events $E_{i,j}$.

The probability of event $E_{i,j}$ is relatively easy to analyze. Let $\mathbf{P}$ be a matrix of order $\xi\times \xi$ whose $(i,j)$ element is the probability of event $E_{i,j}$. Let $E_{i,h}^{(+)}$ be the event that $B$ transitions to state $(h,\kappa)$ given that the transition is from state $(i,\kappa-1)$ to any state in level $\kappa$. Also, let $E_{h,j}^{(-)}$ be the event that state $(j,\kappa-1)$ is the first state that $B$ hits in level $\kappa-1$ given that $B$ starts in state $(h,\kappa)$. Then,

$$(\mathbf{P})_{i,j} = \sum_h {\rm Pr}\left(E_{i,h}^{(+)}\right) {\rm Pr}\left(E_{h,j}^{(-)}\right).$$

Thus, all that remains is to derive ${\rm Pr}\left(E_{i,h}^{(+)}\right)$ and ${\rm Pr}\left(E_{h,j}^{(-)}\right)$. The first quantity is derived via $\mathbf{F}_b^{(\kappa-1)}$ as follows:

$${\rm Pr}\left(E_{i,h}^{(+)}\right) = \frac{(\mathbf{F}_b^{(\... ...1)})_{i,h}}{\sum_{j=1}^\xi (\mathbf{F}_b^{(\kappa-1)})_{i,j}},$$

where $\frac{0}{0}$ is defined as 0. Let $\mathbf{G}^{(\kappa)}$ be a matrix whose $(h,j)$ element is ${\rm Pr}\left(E_{h,j}^{(-)}\right)$. Then, matrix $\mathbf{G}^{(\kappa)}$ is obtained by the algorithm in Figure 3.12 (see Section 3.7 for an alternative algorithm and intuition). More formally, let Let $\mathbf{H}^{(\kappa-1)}$ be a matrix whose $(i,h)$ element is ${\rm Pr}\left(E_{i,h}^{(+)}\right)$. Then, matrix $\mathbf{P}$ is given by

$$\mathbf{P} = \mathbf{H}^{(\kappa-1)} \mathbf{G}^{(\kappa)}.$$

Next, we analyze the moments of $D_{i,j}$. Let $\mathbf{M}_r$ be a matrix of order $\xi\times \xi$ whose $(i,j)$ element is the $r$-th moment of $D_{i,j}$ for $r\geq 1$. Note that $D_{i,j}$ is a mixture of distributions of various conditional passage times from level $\kappa$ to level $\kappa-1$. Specifically, let $T^{(\kappa)}_{i,j}$ be the time to go from state $(i, \kappa)$ to state $(j,\kappa-1)$. Then, the distribution function of $D_{i,j}$ is given by

$$\sum_h {\rm Pr}\left(E_{i,h}^{(+)}\right) {\rm Pr}\left(E_{h... ...rm Pr}\left(T^{(\kappa)}_{h,j}\leq x\mid E_{h,j}^{(-)}\right).$$

Now, let $\mathbf{Z}^{(\kappa)}_r$ be a matrix whose $(h,j)$ element is the $r$-th moment of $T^{(\kappa)}_{h,j}$ given event $E^{(\kappa)}_{h,j}$, i.e.

$$(\mathbf{Z}^{(\kappa)}_r)_{h,j} = \int_0^\infty x^r d\Pr\left(T^{(\kappa)}_{h,j} \leq x \mid E^{(-)}_{h,j} \right)$$

for $r=1,2,3$. Then,

$$(\mathbf{M}_r)_{i,j} = \sum_h {\rm Pr}\left(E_{i,h}^{(+)}\ri... ...Pr}\left(E_{h,j}^{(-)}\right) (\mathbf{Z}^{(\kappa)}_r)_{h,j}.$$

More formally, let $\mathbf{G}_r$ be a matrix whose $(h,j)$ element is

$$(\mathbf{G}_r)_{h,j} = {\rm Pr}\left(E_{h,j}^{(-)}\right) (\... ...r)_{h,j} = (\mathbf{G})_{h,j}(\mathbf{Z}^{(\kappa)}_r)_{h,j}.$$

Then,

$$\mathbf{M} = \mathbf{H} \mathbf{G}_r.$$

Thus, all that remains is to derive $\mathbf{Z}^{(\kappa)}_r$. We can calculate $\mathbf{Z}_r^{(\kappa)}$ by a trivial extension of Neuts' algorithm [134] for any $r$; we postpone this extension to Section 3.7.

We are now ready to construct $\widetilde B$. We use the moment matching algorithm developed in Chapter 2 to approximate $D_{i,j}$ by a PH distribution, $(\Vec{\tau_{i,j}},\mathbf{T}_{i,j})$, matching the first three moments of $D_{i,j}$, $((\mathbf{M}_1)_{i,j},(\mathbf{M}_2)_{i,j},(\mathbf{M}_3)_{i,j})$, for all $i$ and $j$. Let $\Vec{t_{i,j}} = - \mathbf{T}_{i,j} \vec{1}$, where $\vec{1}$ is a column vector with all elements 1 and has order equal to the number of columns in $\mathbf{T}_{i,j}$.

Using $\mathbf{P}$ and $(\Vec{\tau_{i,j}},\mathbf{T}_{i,j})$ defined above, the generator matrix of $\widetilde B$ is defined as

$$\mathbf{Q}_{\widetilde B} = \left(\begin{array}{cccl\vert cc... ...thbf{t}_{\xi} & & & &\mathbf{T}_{\xi} \\ \end{array}\right),$$

where $\vec\lambda = \mathbf{F}_b^{(\kappa-1)} \vec{1}$,

$$\begin{eqnarray*} \mathbf{T}_i & = & \left(\begin{array}{lll} \mathbf{T}_{i,1}&... ...au_{i,\xi}} \\ & \mathbf{O}_{\xi-i,\xi} & \end{array}\right) \end{eqnarray*}$$

for $i=1,...,\xi$. Here, $\vec{1}$ is a column vector with all elements 1 and has order equal to the number of columns in $\mathbf{F}_b^{(\kappa-1)}$, and $\mathbf{O}_{s,t}$ denotes a zero matrix of order $s\times t$. Recall that $\xi$ is the number of phases in level $\kappa-1$ of $B$ (and $\widetilde B$).