Matrix analytic method

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.^[1][2] Such models are often described as M/G/1 type Markov chains because they can describe transitions in an M/G/1 queue.^[3][4] The method is a more complicated version of the matrix geometric method and is the classical solution method for M/G/1 chains.^[5]

An M/G/1-type stochastic matrix is one of the form^[3]

${\displaystyle 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.^[6][7] If P is irreducible^{[broken anchor]} and positive recurrent then the stationary distribution is given by the solution to the equations^[3]

${\displaystyle 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^[3]

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

G is called the auxiliary matrix.^[8] Matrices are defined^[3]

${\displaystyle {\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^[3]

${\displaystyle {\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,^[3] a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988.^[9]

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

There are two popular iterative methods for computing G,^[10][11]

• functional iterations
• cyclic reduction.

• MAMSolver^[12]

• v
• t
• e

Queueing theory

Single queueing nodes

• D/M/1 queue
• M/D/1 queue
• M/D/c queue
• M/M/1 queue
  • Burke's theorem
• M/M/c queue
• M/M/∞ queue
• M/G/1 queue
  • Pollaczek–Khinchine formula
  • Matrix analytic method
• M/G/k queue
• G/M/1 queue
• G/G/1 queue
  • Kingman's formula
  • Lindley equation
• Fork–join queue
• Bulk queue

Arrival processes

• Poisson point process
• Markovian arrival process
• Rational arrival process

Queueing networks

• Jackson network
  • Traffic equations
• Gordon–Newell theorem
  • Mean value analysis
  • Buzen's algorithm
• Kelly network
• G-network
• BCMP network

Service policies

• FIFO
• LIFO
• Processor sharing
• Round-robin
• Shortest job next
• Shortest remaining time

Key concepts

• Continuous-time Markov chain
• Kendall's notation
• Little's law
• Product-form solution
  • Balance equation
  • Quasireversibility
  • Flow-equivalent server method
• Arrival theorem
• Decomposition method
• Beneš method

Limit theorems

• Fluid limit
• Mean-field theory
• Heavy traffic approximation
  • Reflected Brownian motion

Extensions

• Fluid queue
• Layered queueing network
• Polling system
• Adversarial queueing network
• Loss network
• Retrial queue

Information systems

• Data buffer
• Erlang (unit)
• Erlang distribution
• Flow control (data)
• Message queue
• Network congestion
• Network scheduler
• Pipeline (software)
• Quality of service
• Scheduling (computing)
• Teletraffic engineering

Category