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=\left(\begin{array}{cc}{B}_{00}& B_{01}\\ B_{10}& 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{array}\right)$

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{array}{rl}{\pi }_0{B}_{00}+{\pi }_1{B}_{10}& =0\\ {\pi }_0{B}_{01}+{\pi }_1{A}_1+{\pi }_2{A}_0& =0\\ {\pi }_1{A}_2+{\pi }_2{A}_1+{\pi }_3{A}_0& =0\\ & ⋮\\ {\pi }_{i-1}{A}_2+{\pi }_i{A}_1+{\pi }_{i+1}{A}_0& =0\\ & ⋮\\ \end{array}$

Observe that the relationship

${\pi }_i={\pi }_1{R}^{i-1}$

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

$\begin{array}{r}\left(\begin{array}{cc}{\pi }_0& {\pi }_1\end{array}\right)\left(\begin{array}{cc}{B}_{00}& B_{01}\\ B_{10}& A_1+R{A}_0\end{array}\right)=\left(\begin{array}{cc}0& 0\end{array}\right)\end{array}$

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