matrix geometric method

In probability theory, the matrix geometric method is a method for the analysis of quasi-birth–death processes, continuous-time Markov chain whose transition rate matrices with a repetitive block structure. The method was developed "largely by Marcel F. Neuts and his students starting around 1975."

Method description

The method requires a transition rate matrix with tridiagonal block structure as follows

::$Q=\begin B_ & B_ \\ B_ & A_1 & A_2 \\ & A_0 & A_1 & A_2 \\ && A_0 & A_1 & A_2 \\ &&& A_0 & A_1 & A_2 \\ &&&& \ddots & \ddots & \ddots \end$

where each of ''B''₀₀, ''B''₀₁, ''B''₁₀, ''A''₀, ''A''₁ and ''A''₂ are matrices. To compute the stationary distribution ''π'' writing ''π'' ''Q'' = 0 the balance equations are considered for sub-vectors ''π''_''i''

::$\begin \pi_0 B_ + \pi_1 B_ &= 0\\ \pi_0 B_ + \pi_1 A_1 + \pi_2 A_0 &= 0\\ \pi_1 A_2 + \pi_2 A_1 + \pi_3 A_0 &= 0 \\ & \vdots \\ \pi_ A_2 + \pi_i A_1 + \pi_ A_0 &= 0\\ & \vdots \\ \end$

Observe that the relationship

::$\pi_i = \pi_1 R^$

holds where ''R'' is the Neut's rate matrix, which can be computed numerically. Using this we write

::$\begin \begin\pi_0 & \pi_1 \end \beginB_ & B_ \\ B_ & A_1 + RA_0 \end = \begin 0 & 0 \end \end$

which can be solve to find ''π''₀ and ''π''₁ and therefore iteratively all the ''π''_''i''.

Computation of ''R''

The matrix ''R'' can be computed using cyclic reduction or logarithmic reduction.

Matrix analytic method

The matrix analytic method is a more complicated version of the matrix geometric solution method used to analyse models with block M/G/1 matrices. Such models are harder because no relationship like ''π''_''i'' = ''π''₁ R^{''i'' – 1} used above holds.

External links

Performance Modelling and Markov Chains (part 2)
by William J. Stewart at ''7th International School on Formal Methods for the Design of Computer, Communication and Software Systems: Performance Evaluation''

References

{{probability-stub
Queueing theory