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

Method description

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

P=(B0B1B2B3⋯A0A1A2A3⋯A0A1A2⋯A0A1⋯⋮⋮⋮⋮⋱)

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. If P is irreducible and positive recurrent then the stationary distribution is given by the solution to the equations

Pπ=π and 𝐞Tπ=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

G=∑i=0∞GiAi.

G is called the auxiliary matrix. Matrices are defined

A‾i+1=∑j=i+1∞Gj−i−1AjB‾i=∑j=i∞Gj−iBj

then π0 is found by solving

B‾0π0=π0(𝐞T+𝐞T(I−∑i=1∞A‾i)−1∑i=1∞B‾i)π0=1

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

πi=(I−A‾1)−1[B‾i+1π0+∑j=1i−1A‾i+1−jπj],i≥1.

Computation of G

There are two popular iterative methods for computing G,

Tools

References

  1. ↑ Harchol-Balter, M. (2012). "Phase-Type Distributions and Matrix-Analytic Methods". Performance Modeling and Design of Computer Systems. pp. 359–379. doi:10.1017/CBO9781139226424.028. ISBN 9781139226424.
  2. ↑ Neuts, M. F. (1984). "Matrix-analytic methods in queuing theory". European Journal of Operational Research. 15: 2–12. doi:10.1016/0377-2217(84)90034-1.
  3. 1 2 3 4 5 6 7 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.
  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 (1–4): 331–348. CiteSeerX 10.1.1.80.9473. doi:10.1016/j.peva.2005.07.003. {{cite journal}}: Cite uses deprecated parameter |citeseerx= (help)
  5. ↑ Riska, A.; Smirni, E. (2002). "M/G/1-Type Markov Processes: A Tutorial" (PDF). Performance Evaluation of Complex Systems: Techniques and Tools. Lecture Notes in Computer Science. Vol. 2459. pp. 36. doi:10.1007/3-540-45798-4_3. ISBN 978-3-540-44252-3.
  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 978-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.
  8. ↑ Riska, A.; Smirni, E. (2002). "Exact aggregate solutions for M/G/1-type Markov processes". ACM SIGMETRICS Performance Evaluation Review. 30: 86. CiteSeerX 10.1.1.109.2225. doi:10.1145/511399.511346. {{cite journal}}: Cite uses deprecated parameter |citeseerx= (help)
  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.
  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.
  11. ↑ Meini, B. (1998). "Solving m/g/l type markov chains: Recent advances and applications". Communications in Statistics. Stochastic Models. 14 (1–2): 479–496. doi:10.1080/15326349808807483.
  12. ↑ Riska, A.; Smirni, E. (2002). "MAMSolver: A Matrix Analytic Methods Tool". Computer Performance Evaluation: Modelling Techniques and Tools. Lecture Notes in Computer Science. Vol. 2324. p. 205. CiteSeerX 10.1.1.146.2080. doi:10.1007/3-540-46029-2_14. ISBN 978-3-540-43539-6. {{cite book}}: Cite uses deprecated parameter |citeseerx= (help)