3.6 Generalization: derivation of Ramaswami's recursive formula

In this section, we investigate the relation between $\mbox{\boldmath {$\pi$}}^{(i)}$ for $i > 1$ and $\mbox{\boldmath {$\pi$}}^{(j)}$ for $0 \leq j < i$ for the general case in the same spirit as [93]. We construct the stochastic complementation of the states in ${\cal{A}}= \cup_{j=0}^i {\cal{S}}^{(j)}$ ( $\overline{{\cal{A}}}={\cal{S}}- {\cal{A}}$). We obtain

$$\begin{array}{c c} {\mathbf{Q}}[{\cal{A}}, {\cal{A}}] = \lef... ...ots & \vdots & \vdots & \ddots \end{array}\right]. \end{array}$$

The stochastic complement for states in ${\cal{A}}$ has an infinitesimal generator defined as follows

$$\overline{{\mathbf{Q}}} = {\mathbf{Q}}[{\cal{A}}, {\cal{A}}]... ...])^{-1} \cdot {\mathbf{Q}}[\overline{{\cal{A}}},{\cal{A}}] .$$

Observe that ${\mathbf{Q}}[\overline{{\cal{A}}}, \overline{{\cal{A}}}]$ is the same matrix for any $i \geq 1$. We define its inverse to be as follows

$$(- {\mathbf{Q}}[\overline{{\cal{A}}}, \overline{{\cal{A}}}])... ...dots & \vdots & \vdots & \vdots & \vdots \end{array}\right] .$$ (3.19)

From the special structure of ${\mathbf{Q}}[\overline{{\cal{A}}}, {\cal{A}}]$, we conclude that the second term of the above summation is a matrix with all block entries equal to zero except the very last block column, whose block entries ${\mathbf{X}}_{j}$ are of the form:

$${\mathbf{X}}_{i} = \sum_{k=0}^{\infty} \widehat{{\mathbf{F}}}^{(i+1+k)} \cdot {\mathbf{A}}_{k,0} \cdot {\mathbf{B}}$$

and

$${\mathbf{X}}_{j} = \sum_{k=0}^{\infty} {\mathbf{F}}^{(j+1+k)} \cdot {\mathbf{A}}_{k,0} \cdot {\mathbf{B}}, ~~0 \leq j < i.$$

The infinitesimal generator $\overline{{\mathbf{Q}}}$ of the stochastic complement of states in ${\cal{A}}$ is determined as

$$\begin{array}{c c} \overline{{\mathbf{Q}}}= \left[ \begin{ar... ...thbf{B}}& \L + {\mathbf{X}}_{0} \end{array}\right]. \end{array}$$ (3.20)

We define $\overline{\mbox{\boldmath {$\pi$}}}$ to be the steady-state probability vector of the CTMC with infinitesimal generator $\overline{{\mathbf{Q}}}$ and $\mbox{\boldmath {$\pi$}}_{{\cal{A}}}$ the steady-state probability vector of the CTMC with infinitesimal generator ${\mathbf{Q}}_{M/G/1}$ corresponding to the states in ${\cal{A}}$. There is a linear relation between $\overline{\mbox{\boldmath {$\pi$}}}$ and $\mbox{\boldmath {$\pi$}}_{{\cal{A}}}$:

$$\overline{\mbox{\boldmath {$\pi$}}} = \frac{\mbox{\boldmath ... ...}}}}{\mbox{\boldmath {$\pi$}}_{{\cal{A}}}\cdot{\mathbf{1}}^T}.$$ (3.21)

From the relation $\overline{\mbox{\boldmath {$\pi$}}}\overline{{\mathbf{Q}}} = {\mathbf{0}}$, it follows that

$$\overline{\mbox{\boldmath {$\pi$}}}^{(i)} \cdot (\L + {\math... ...mathbf{F}}^{(i-j)} + {\mathbf{X}}_{i-j})) ~~~~\forall i \geq 1$$

and

$$\mbox{\boldmath {$\pi$}}^{(i)} \cdot (\L + {\mathbf{X}}_{0})... ...athbf{F}}^{(i-j)} + {\mathbf{X}}_{i-j})) ~~~~\forall i \geq 1.$$ (3.22)

The above equation shows that there in no geometric relation between vectors $\mbox{\boldmath {$\pi$}}^{(i)}$ for $i \geq 1$, however it provides a recursive relation for the computation of the steady-state probability vector for M/G/1 Markov chains. In the following, we further work on simplifying the expression of matrices ${\mathbf{X}}_{j}$ for $0 \leq j \leq i$.

From the definition of the stochastic complementation (see Subsection 2.8.2), we know that an entry $[r,c]$ in $(-{\mathbf{Q}}[\overline{{\cal{A}}},\overline{{\cal{A}}}]^{-1}\cdot {\mathbf{Q}}[\overline{{\cal{A}}},{\cal{A}}])$^3.4represents the probability that starting from state $r \in \overline{{\cal{A}}}$ the process enters ${\cal{A}}$ through state $c$. Since ${\cal{A}}$ is entered from $\overline{{\cal{A}}}$ only through states in ${\cal{S}}^{(i)}$, we can use the probabilistic interpretation of matrix ${\mathbf{G}}$ to figure out the entries in $(-{\mathbf{Q}}[\overline{{\cal{A}}},\overline{{\cal{A}}}]^{-1})\cdot {\mathbf{Q}}[\overline{{\cal{A}}},{\cal{A}}]$. An entry $[r,c]$ in ${\mathbf{G}}^{j}$ for $j > 0$ represents the probability that starting from state $r \in {\cal{S}}^{(i+j)}$ for $i > 0$ the process enters set ${\cal{S}}^{(i)}$ through state $c$. It is straightforward now to define

$$(-{\mathbf{Q}}[\overline{{\cal{A}}},\overline{{\cal{A}}}]^{-... ...vdots & \vdots & \vdots & \vdots & \vdots \end{array}\right].$$ (3.23)

The above result simplifies the expression of ${\mathbf{X}}_{j}$ as follows

$${\mathbf{X}}_{i} = \sum_{k=1}^{\infty} \widehat{{\mathbf{F}}... ... {\mathbf{F}}^{(j+k)} \cdot {\mathbf{G}}^{k}, ~~ 0 \leq j < i.$$ (3.24)

This is in essence Ramaswami's recursive formula. We will return to this in the following section after we elaborate on matrix ${\mathbf{G}}$, its implications, and its probabilistic interpretation.