Next: 3.6 Generalization: derivation of Up: 3. Matrix-Analytic Methods Previous: 3.4 Why M/G/1 processes

# 3.5 Example: a queue

Figure 3.3 illustrates a Markov chain that models a queue. This chain is very similar with the one depicted in Figure 3.1, the only difference is that the new chain models bulk arrivals of unlimited size.
The infinitesimal generator of the process is block partitioned according to the partitioning of the state space of this CTMC into subsets and for . The definition of the component matrices of is as follows:

In the following, we derive the relation between for and the rest of vectors in using stochastic complementation, i.e., similarly to the approach described in Section 3.1. First we partition the state space into two partitions and and then we construct the stochastic complement of states in . The Markov chain of the stochastic complement of states in , (see Figure 3.4), illustrates how transitions from states and for and state to states and for are folded back to state , which is the single state to enter from states in . These back-folded'' transitions are marked by for and and represent the correction'' needed to make the stochastic complement of states in , a stand-alone process. Because of the single entry state in the stochastic complement of states in for this example can be explicitly derived (see Lemma on single entry state in Subsection 2.8.2) and the definition of rates is as follows:

The flow balance equations for states and for the stochastic complement of states in are:

and

In the above equalities, we group the elements of on the left and the rest of the terms on the right in order to express their relation in terms of the block matrices that describe the infinitesimal generator of the stochastic complement of states in . By rearranging the terms, the above equations can be re-written as:

and

We can now re-write the above equations in the following matrix equation form:

By substituting with and expressing the coefficient matrices in the above equation in terms of the component matrices of the infinitesimal generator of the stochastic complement of states in , we obtain3.3:

where is a matrix with the following structure:

Note that at this point, we have introduced a new matrix, , that has an important probabilistic interpretation. In this specific example, the matrix can be explicitly derived [77]. This is a direct outcome of the fact that all states in set for return to the same single state in set . Equivalently, the matrix of the infinitesimal generator has only a single column different from zero.

Next: 3.6 Generalization: derivation of Up: 3. Matrix-Analytic Methods Previous: 3.4 Why M/G/1 processes
Alma Riska 2003-01-13