Next: Dimensionality reduction with complete Up: Approximations of dimensionality reduction Previous: Approximations of dimensionality reduction   Contents

## Dimensionality reduction with partial independence assumption

DR-PI (DR with partial independence assumption) ignores the dependency that the sojourn time in levels has on how the Markov chain enters levels (from level ). Specifically, we assume that is independent of . Let for all for each , and let denote the process that is the same as except that is replaced by for all for each . Figure 3.27(a) shows the Markov chain for the high priority jobs (background process) that we obtain via DR-PI in the analysis of an M/PH/2 queue with two priority classes. (Recall the Markov chain that we obtain via DR, Figure 3.5 in Section 3.1, where the four types of busy periods are approximated by four PH distributions, respectively.) In DR-PI, the four types of busy periods are represented by two PH distributions, ignoring the dependency that the duration of the busy period has on the phase of the job in service at the beginning of the busy period.

Figure 3.27: Background processes on a finite state space, obtained via (a) DR-PI and (b) DR-CI. Labels on the transitions in the busy periods are omitted for clarity.
 (a)
 (b)

In general, we require that process has the following two key properties:

• The probability of event in is the same as that in (and that in as well).
• We choose such that the marginal distribution of the sojourn time in levels in well-represents that in (and hence in as well).
Hence, and would have stochastically the same total sojourn time in levels in the long run if the second property did not involve the approximation (i.e., if the marginal distribution is fitted exactly). However, and have different autocorrelation in the sequence of the sojourn times in levels .

More formally, the generator matrix of , , is determined as follows. Let be the -th moment of for for each . We determine so that and have the same marginal -th moment of the sojourn time in levels :

where denotes the stationary probability vector that is in level , which can be calculated via matrix analytic methods as in Section 3.2. We approximate by a PH distribution, , matching the first three moments of , . Let as before. Generator matrix is then defined by

where , , and are submatrices of as defined in Section 3.5.2,

Observe that the number of PH distributions used to approximate the sojourn time distributions in levels is reduced from , in , to , in . The next approximation, DR-CI, uses only one PH distribution.

Next: Dimensionality reduction with complete Up: Approximations of dimensionality reduction Previous: Approximations of dimensionality reduction   Contents
Takayuki Osogami 2005-07-19