# 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.[1] The method was developed "largely by Marcel F. Neuts and his students starting around 1975."[2]

## Method description

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

$Q=\begin{pmatrix} 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{pmatrix}$

where each of B00, B01, B10, A0, A1 and A2 are matrices. To compute the stationary distribution π writing π Q = 0 the balance equations are considered for sub-vectors πi

\begin{align} \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 \\ & \vdots \\ \pi_{i-1} A_2 + \pi_i A_1 + \pi_{i+1} A_0 &= 0\\ & \vdots \\ \end{align}

Observe that the relationship

$\pi_i = \pi_1 R^{i-1}$

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

\begin{align} \begin{pmatrix}\pi_0 & \pi_1 \end{pmatrix} \begin{pmatrix}B_{00} & B_{01} \\ B_{10} & A_1 + RA_0 \end{pmatrix} = \begin{pmatrix} 0 & 0 \end{pmatrix} \end{align}

which can be solve to find π0 and π1 and therefore iteratively all the πi.

## Computation of R

The matrix R can be computed using cyclic reduction[4] or logarithmic reduction.[5][6]

## 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.[7] Such models are harder because no relationship like πi = π1 Ri – 1 used above holds.[8]