Matrix analytic method

In probability theory, Ramaswami's formula gives a numerically stable method to compute the stationary probability distribution of an M/G/1 type model, first published by V. Ramaswami in 1988. It is the classical solution method for M/G/1 chains.

Formula

An M/G/1-type stochastic matrix is 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 x k matrices. (Note that unmarked matrix entries represent zeroes.) 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}$

and 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

$\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.$

Computation of G

There are two popular iterative methods for computing G,

• functional iterations
• cyclic reduction.

If transitions up or down are restricted faster algorithms can take advantage of the simpler structure of the model.