Matrix analytic method

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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]

Method description[edit]

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

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 Bi and Ai 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 and positive recurrent then the stationary distribution is given by the solution to the equations[3]

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 π1, π2, π3, …. To compute these probabilities the column stochastic matrix G is computed such that[3]

 G = \sum_{i=0}^\infty G^i A_i.

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

\begin{align}
\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{align}

then π0 is found by solving[3]

\begin{align}
\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{align}

and the πi are given by Ramaswami's formula,[3] a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988.[9]

\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[edit]

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

Tools[edit]

References[edit]

  1. ^ Harchol-Balter, M. (2012). "Phase-Type Distributions and Matrix-Analytic Methods". Performance Modeling and Design of Computer Systems. p. 359. doi:10.1017/CBO9781139226424.028. ISBN 9781139226424.  edit
  2. ^ Neuts, M. F. (1984). "Matrix-analytic methods in queuing theory". European Journal of Operational Research 15: 2–0. doi:10.1016/0377-2217(84)90034-1.  edit
  3. ^ a b c d e f g Meini, B. (1997). "An improved FFT-based version of Ramaswami's formula". Communications in Statistics. Stochastic Models 13 (2): 223–238. doi:10.1080/15326349708807423.  edit
  4. ^ Stathopoulos, A.; Riska, A.; Hua, Z.; Smirni, E. (2005). "Bridging ETAQA and Ramaswami's formula for the solution of M/G/1-type processes". Performance Evaluation 62: 331. doi:10.1016/j.peva.2005.07.003.  edit
  5. ^ Riska, A.; Smirni, E. (2002). "M/G/1-Type Markov Processes: A Tutorial". Performance Evaluation of Complex Systems: Techniques and Tools. Lecture Notes in Computer Science 2459. p. 36. doi:10.1007/3-540-45798-4_3. ISBN 978-3-540-44252-3.  edit
  6. ^ Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Shridharbhai Trivedi, Kishor (2006). Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2 ed.). John Wiley & Sons, Inc. p. 250. ISBN 0471565253. 
  7. ^ Artalejo, Jesús R.; Gómez-Corral, Antonio (2008). "The Matrix-Analytic Formalism". Retrial Queueing Systems. pp. 187–205. doi:10.1007/978-3-540-78725-9_7. ISBN 978-3-540-78724-2.  edit
  8. ^ Riska, A.; Smirni, E. (2002). "Exact aggregate solutions for M/G/1-type Markov processes". ACM SIGMETRICS Performance Evaluation Review 30: 86. doi:10.1145/511399.511346.  edit
  9. ^ Ramaswami, V. (1988). "A stable recursion for the steady state vector in markov chains of m/g/1 type". Communications in Statistics. Stochastic Models 4: 183–188. doi:10.1080/15326348808807077.  edit
  10. ^ Bini, D. A.; Latouche, G.; Meini, B. (2005). Numerical Methods for Structured Markov Chains. doi:10.1093/acprof:oso/9780198527688.001.0001. ISBN 9780198527688.  edit
  11. ^ Meini, B. (1998). "Solving m/g/l type markov chains: Recent advances and applications". Communications in Statistics. Stochastic Models 14: 479–496. doi:10.1080/15326349808807483.  edit
  12. ^ Riska, A.; Smirni, E. (2002). "MAMSolver: A Matrix Analytic Methods Tool". Computer Performance Evaluation: Modelling Techniques and Tools. Lecture Notes in Computer Science 2324. p. 205. doi:10.1007/3-540-46029-2_14. ISBN 978-3-540-43539-6.  edit