Encyclopedia

Matrix analytic method

Computing technique in probability theory

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated March 30, 2025

In probability theory, the matrix analytic method is a technique to compute the stationary probability distribution of a Markov chain which has a repeating structure (after some point) and a state space which grows unboundedly in no more than one dimension. Such models are often described as M/G/1 type Markov chains because they can describe transitions in an M/G/1 queue. The method is a more complicated version of the matrix geometric method and is the classical solution method for M/G/1 chains.

01Method description

An M/G/1-type stochastic matrix is one of the form

$P={\begin{pmatrix}B_{0}&B_{1}&B_{2}&B_{3}&\cdots \\A_{0}&A_{1}&A_{2}&A_{3}&\cdots \\&A_{0}&A_{1}&A_{2}&\cdots \\&&A_{0}&A_{1}&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{pmatrix}}$

where B_i and A_i are k × k matrices. (Note that unmarked matrix entries represent zeroes.) Such a matrix describes the embedded Markov chain in an M/G/1 queue. If P is irreducible and positive recurrent then the stationary distribution is given by the solution to the equations

$P\pi =\pi \quad {\text{ and }}\quad \mathbf {e} ^{\text{T}}\pi =1$

where e represents a vector of suitable dimension with all values equal to 1. Matching the structure of P, π is partitioned to π₁, π₂, π₃, …. To compute these probabilities the column stochastic matrix G is computed such that

$G=\sum _{i=0}^{\infty }G^{i}A_{i}.$

G is called the auxiliary matrix. Matrices are defined

${\begin{aligned}{\overline {A}}_{i+1}&=\sum _{j=i+1}^{\infty }G^{j-i-1}A_{j}\\{\overline {B}}_{i}&=\sum _{j=i}^{\infty }G^{j-i}B_{j}\end{aligned}}$

then π₀ is found by solving

${\begin{aligned}{\overline {B}}_{0}\pi _{0}&=\pi _{0}\\\quad \left(\mathbf {e} ^{\text{T}}+\mathbf {e} ^{\text{T}}\left(I-\sum _{i=1}^{\infty }{\overline {A}}_{i}\right)^{-1}\sum _{i=1}^{\infty }{\overline {B}}_{i}\right)\pi _{0}&=1\end{aligned}}$

and the π_i are given by Ramaswami's formula, a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988.

$\pi _{i}=(I-{\overline {A}}_{1})^{-1}\left[{\overline {B}}_{i+1}\pi _{0}+\sum _{j=1}^{i-1}{\overline {A}}_{i+1-j}\pi _{j}\right],i\geq 1.$

02Computation of G

There are two popular iterative methods for computing G,

functional iterations
cyclic reduction.

Watch videos about Matrix analytic methodExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Matrix analytic method”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.