×

On the dual relationship between Markov chains of GI/M/1 and M/G/1 type. (English) Zbl 1202.60147

V. Ramaswami [Commun. Stat. Stoch. Models 6, No. 1, 151–161 (1990; Zbl 0699.60091)] proved that, given a Markov renewal process of M/G/1 type it is possible to construct a Markov renewal process of GI/M/1 type such that the matrix transforms \(G\left( z,s\right) \) for the M/G/1-type process and \( R\left( z,s\right) \,\)for the GI/M/1-type process satisfy a duality relationship. In his 1996 PhD thesis, L. Bright used time reversal arguments to show that it is possible to define a different dual for positive-recurrent and transient processes of M/G/1\(\;\)type and GI/M/1 type. The present authors compare the properties of the Ramaswami and Bright dual processes and show that the Bright dual has desirable properties that can be exploited in the design of algorithms for the analysis of Markov chains of GI/M/1 type and M/G/1 type.

MSC:

60K25 Queueing theory (aspects of probability theory)
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
90B22 Queues and service in operations research

Citations:

Zbl 0699.60091

Software:

SMCSolver
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akar, N. and Sohraby, K. (1997). An invariant subspace approach in M/G/1 and G/M/1 type Markov chains. Commun. Statist. Stoch. Models 13 , 381–416. · Zbl 0896.60061 · doi:10.1080/15326349708807433
[2] Asmussen, S. (1989). Aspects of matrix Wiener–Hopf factorisation in applied probability. Math. Scientist 14 , 101–116. · Zbl 0688.60055
[3] Asmussen, S. and Ramaswami, V. (1990). Probabilistic interpretations of some duality results for the matrix paradigms in queueing theory. Commun. Statist. Stoch. Models 6 , 715–733. · Zbl 0744.60108 · doi:10.1080/15326349908807170
[4] Bini, D. A. and Meini, B. (1995). On cyclic reduction applied to a class of Toeplitz-like matrices arising in queueing problems. In Computations with Markov Chains , ed. W. J. Stewart, Kluwer, Boston. pp. 21–28. · Zbl 0862.60085
[5] Bini, D. A, Latouche, G. and Meini, B. (2005). Numerical Methods for Structured Markov Chains . Oxford University Press. · Zbl 1076.60002 · doi:10.1093/acprof:oso/9780198527688.001.0001
[6] Bini D.A., Meini B. and Ramaswami V. (2008). A probabilistic interpretation of cyclic reduction and its relationships with logarithmic reduction. Calcolo 45 , 207–216. · Zbl 1175.65012 · doi:10.1007/s10092-008-0151-6
[7] Bini, D. A., Meini, B., Steffé, S. and Van Houdt, B. (2006). Structured Markov chains solver: software tools. In Proc. SMCTools Workshop (Pisa, 2006; ACM Internat. Conf. Proc. Ser. 201 ), ACM Press, New York.
[8] Bright, L. (1996). Matrix-analytic methods in applied probability. Doctoral Thesis, University of Adelaide.
[9] Falkenberg, E. (1994). On the asymptotic behaviour of the stationary distribution of Markov chains of M/G/1-type. Commun. Statist. Stoch. Models 10 , 75–97. · Zbl 0791.60087 · doi:10.1080/15326349408807289
[10] Gail, H. R., Hantler, S. L. and Taylor, B. A. (1994). Solutions of the basic matrix equation for M/G/1 and G/M/1 type Markov chains. Commun. Statist. Stoch. Models 10 , 1–44. · Zbl 0791.60086 · doi:10.1080/15326349408807287
[11] Gail, H. R., Hantler, S. L. and Taylor, B. A. (1996). Spectral analysis of M/G/1 and G/M/1 type Markov chains. Adv. Appl. Prob. 28 , 114–165. JSTOR: · Zbl 0845.60092 · doi:10.2307/1427915
[12] Gail, H. R., Hantler, S. L. and Taylor, B. A. (1998). Matrix-geometric invariant measures for G/M/1 type Markov chains. Commun. Statist. Stoch. Models 14 , 537–569. · Zbl 0913.60085 · doi:10.1080/15326349808807487
[13] Kelly, F. P. (1983). Invariant measures and the q-matrix. In Probability, Statistics and Analysis (London Math. Soc. Lecture Notes 79 ), eds J. F. C. Kingman and G. E. H. Reuter, Cambridge University Press, pp. 143–160. · Zbl 0498.60077
[14] Latouche, G. (1993). Algorithms for infinite Markov chains with repeating columns. In Linear Algebra, Markov Chains, and Queueing Models (IMA Vol. Math. Appl. 48 ), Springer, New York, pp. 231–265. · Zbl 0790.65121
[15] Latouche, G. (1994). Newton’s iteration for non-linear equations in Markov chains. IMA J. Numer. Anal. 14 , 583–598. · Zbl 0861.65132 · doi:10.1093/imanum/14.4.583
[16] Latouche, G. and Ramaswami, V. (1993). A logarithmic reduction algorithm for quasi-birth-and-death processes. J. Appl. Prob. 30 , 650–674. JSTOR: · Zbl 0789.60055 · doi:10.2307/3214773
[17] Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling . Society for Industrial and Applied Mathematics, Philadelphia, PA. · Zbl 0922.60001 · doi:10.1137/1.9780898719734
[18] Neuts, M. F. (1978). Markov chains with applications in queueing theory, which have a matrix-geometric invariant probability vector. Adv. Appl. Prob. 10 , 185–212. JSTOR: · Zbl 0382.60097 · doi:10.2307/1426725
[19] Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models . John Hopkins University Press, Baltimore, MD. · Zbl 0469.60002
[20] Neuts, M. F. (1989). Structured Stochastic Matrices of M/G/1 and Their Applications . Marcel Dekker, New York. · Zbl 0695.60088
[21] Ramaswami, V. (1990). A duality theorem for the matrix paradigm in queueing theory. Commun. Statist. Stoch. Models 6 , 151–161. · Zbl 0699.60091 · doi:10.1080/15326349908807141
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.