3.7 General solution of M/G/1-type processes

For the solution of M/G/1-type processes, several algorithms exist [12,60,69]. These algorithms first compute matrix ${\mathbf{G}}$ as the solution of the following equation:

$${\mathbf{B}}+ \L {\mathbf{G}}+ \sum_{i=1}^{\infty} {\mathbf{F}}^{(i)}{\mathbf{G}}^{i+1} = {\mathbf{0}} .$$ (3.25)

The matrix ${\mathbf{G}}$ has an important probabilistic interpretation: an entry $(r,c)$ in ${\mathbf{G}}$ expresses the conditional probability of the process first entering ${\cal{S}}^{(i-1)}$ through state $c$, given that it starts from state $r$ of ${\cal{S}}^{(i)}$ [69, page 81]^3.5. Figure 3.5 illustrates the relation of entries in ${\mathbf{G}}$ for different paths of the process.

Figure: Probabilistic interpretation of ${\mathbf{G}}$.

From the probabilistic interpretation of ${\mathbf{G}}$ the following structural properties hold [69]

• if the M/G/1 process with infinitesimal generator ${\mathbf{Q}}_{M/G/1}$ is recurrent then ${\mathbf{G}}$ is row-stochastic,
• to any zero column in matrix ${\mathbf{B}}$ of the infinitesimal generator ${\mathbf{Q}}_{M/G/1}$, there is a corresponding zero column in matrix ${\mathbf{G}}$.

The ${\mathbf{G}}$ matrix is obtained by solving iteratively Eq.(3.25). However, recent advances show that the computation of ${\mathbf{G}}$ is more efficient when displacement structures are used based on the representation of M/G/1-type processes by means of QBD processes [60,12,11,47]. The most efficient algorithm for the computation of ${\mathbf{G}}$ is the cyclic reduction algorithm [12].