Matrix analytic method
In
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
An M/G/1-type stochastic matrix is one of the form[3]
where Bi and Ai are k × k matrices. (Note that unmarked matrix entries represent zeroes.) Such a matrix describes the
positive recurrent then the stationary distribution is given by the solution to the equations[3]
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 is called the auxiliary matrix.[8] Matrices are defined[3]
then π0 is found by solving[3]
and the πi are given by Ramaswami's formula,[3] a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988.[9]
Computation of G
There are two popular iterative methods for computing G,[10][11]
- functional iterations
- cyclic reduction.
Tools
References
- ISBN 9781139226424.
- .
- ^ .
- .
- ISBN 978-3-540-44252-3.
- ISBN 978-0471565253.
- ISBN 978-3-540-78724-2.
- .
- .
- ISBN 9780198527688.
- .
- ISBN 978-3-540-43539-6.