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]

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

${\displaystyle 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}}}${\displaystyle 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 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

${\displaystyle {\begin{aligned}\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{aligned}}}${\displaystyle {\begin{aligned}\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{aligned}}}

Observe that the relationship

${\displaystyle \pi _{i}=\pi _{1}R^{i-1}}${\displaystyle \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

${\displaystyle {\begin{aligned}{\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{aligned}}}${\displaystyle {\begin{aligned}{\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{aligned}}}

which can be solve to find π₀ and π₁ and therefore iteratively all the π_i.

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

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 = π₁ R^i – 1 used above holds.^[8]

• 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

• Queueing theory
• 1975 introductions
• Probability stubs

• Articles with short description
• Short description matches Wikidata
• All stub articles