Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Matrix analytic method

From Wikipedia, the free encyclopedia
Computing technique in probability theory

Inprobability theory, thematrix analytic method is a technique to compute the stationaryprobability distribution of aMarkov 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 asM/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 thematrix 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=(B0B1B2B3⋯A0A1A2A3⋯A0A1A2⋯A0A1⋯⋮⋮⋮⋮⋱){\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}}}

whereBi andAi arek × k matrices. (Note that unmarked matrix entries represent zeroes.) Such a matrix describes theembedded Markov chain in an M/G/1 queue.[6][7] IfP isirreducible andpositive recurrent then the stationary distribution is given by the solution to the equations[3]

Pπ=π and eTπ=1{\displaystyle P\pi =\pi \quad {\text{ and }}\quad \mathbf {e} ^{\text{T}}\pi =1}

wheree represents a vector of suitable dimension with all values equal to 1. Matching the structure ofP,π is partitioned toπ1,π2,π3, …. To compute these probabilities the column stochastic matrixG is computed such that[3]

G=∑i=0∞GiAi.{\displaystyle G=\sum _{i=0}^{\infty }G^{i}A_{i}.}

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

A¯i+1=∑j=i+1∞Gj−i−1AjB¯i=∑j=i∞Gj−iBj{\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π0 is found by solving[3]

B¯0π0=π0(eT+eT(I−∑i=1∞A¯i)−1∑i=1∞B¯i)π0=1{\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 byRamaswami's formula,[3] a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988.[9]

πi=(I−A¯1)−1[B¯i+1π0+∑j=1i−1A¯i+1−jπj],i≥1.{\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.}

Computation ofG

[edit]

There are two populariterative methods for computingG,[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. 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. ^abcdefgMeini, 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.
  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.
  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.
Single queueing nodes
Arrival processes
Queueing networks
Service policies
Key concepts
Limit theorems
Extensions
Information systems
Retrieved from "https://en.wikipedia.org/w/index.php?title=Matrix_analytic_method&oldid=1283051879"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp