Other approaches

Other analytic solution methods for multidimensional Markov chains can be classified into two approaches: the direct approach and the approach via generating functions. The direct approach solves the equilibrium equations directly (without transforming them). This includes power series methods, product form methods, and compensation methods. On the other hand, the approach via generating functions solves the functional equation for the generating function of the stationary probabilities. This includes uniformization methods and boundary value methods.

Power series methods express the stationary probability as a power series of a certain parameter such as system load [21,75,104]. Power series methods can, in theory, be applied to any Markov chain. However, the application of power series methods is often limited to simple Markov chains on low dimensional state spaces due to its computational complexity. For example, Kao and Wilson [95] analyze the nonpreemptive multiserver priority queue with two priority classes by power series methods. They report that power series methods experience more inaccuracy as compared to matrix analytic methods with state space truncation. Note that the nonpreemptive multiserver priority queue with two priority classes can be modeled as a GFB process (see Section 3.4), and hence can be analyzed via DR.

Product form methods express the stationary probability as a product of stationary probabilities for respective dimensions (see e.g. [16,97,195]). Product form methods have been developed mainly for the analysis of networks of queues, and the class of Markov chains that have product form solutions is limited. In general, the RFB and GFB processes do not appear to have product form solutions.

Compensation methods express the stationary probability as a sum of an infinite number of product forms [1,2,3]. Compensation methods apply to a large class of Markov chains on a two dimensional grid of the first (positive) quadrant. However, an essential limitation of compensation methods is that transitions to the ``north,'' ``north-east,'' and ``east'' are prohibited. Therefore, compensation methods do not apply to RFB and GFB processes in general. It is possible to extend compensation methods to higher dimensions, but the limitation becomes more severe in higher dimensions [196].

Approaches via generating functions solve the functional equation for the generating function of the stationary probabilities by uniformization [43,100] or by reducing the functional equation to a boundary value problem [44,42]. Although approaches via generating functions apply to a broad class of Markov chains on a two dimensional state space, they do not appear to be applicable to the case of higher dimensions. For example, the FB process can, in theory, be reduced to a boundary value problem if the foreground process repeats after a certain level. However, an RFB process with $m>2$ processes does not appear to be solvable via generating functions. Also, approaches via generating functions often experience numerical instability. For example, Fayolle and Iasnogorodski [51] and Konheim, Meilijson and Melkman [103] reduce the 2D Markov chain for the coupled processor models to (Dirichlet or Riemann-Hilbert) boundary value problems, assuming that service demands have exponential distributions. Due to complexity in the expressions, they were not evaluated in either work. (DR does not appear to be applicable to the 2D Markov chain for the coupled processor model, either.)

In the case of an M/M/$k$ queue with two priority classes (preemptive or nonpreemptive), exact solution methods have been proposed utilizing the spacial structure of this model [127]; for example, in the case of a preemptive priority queue, there is no service completion of lower priority jobs when there are $\geq k$ high priority jobs (there are no backward transitions in the foreground process while the background process is in levels $\geq k$; see Figure 3.1(b)). However, these approaches do not apply to the RFB and GFB processes in general. Very recently, these exact solution methods are extended to non-exponential service times by Sleptchenko [177] (not yet published) and Sleptchenko et. al. [178] (not yet published). The Markov chain is analyzed via a combination of generating functions and matrix analytic methods. In theory, their technique can be generalized to PH distributions, though they evaluate only hyperexponential distributions due to the increased complexity when using more general PH distributions.