Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T10:58:22.564Z Has data issue: false hasContentIssue false
  • English
  • Français

Ramaswami's duality and probabilistic algorithms for determining the rate matrix for a structured GI/M/1 Markov chain

Published online by Cambridge University Press:  17 February 2009

Emma Hunt
Emma Hunt
Affiliation:
School of Mathematical Sciences, The University of Adelaide, Adelaide SA 5005, Australia; e-mail: [email protected].
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We show that Algorithm H* for the determination of the rate matrix of a block-GI/M/1 Markov chain is related by duality to Algorithm H for the determination of the fundamental matrix of a block-M/G/1 Markov chain. Duality is used to generate some efficient algorithms for finding the rate matrix in a quasi-birth-and-death process.

Type
Research Article
Information
The ANZIAM Journal , Volume 46 , Issue 4 , April 2005 , pp. 485 - 493
Copyright
Copyright © Australian Mathematical Society 2005

References

[1]Asmussen, S. and Ramaswami, V., “Probabilistic interpretations of some duality results for the matrix paradigms in queueing theory”, Comm. Statist. Stochastic Models 6 (1990) 715–733.Google Scholar
[2]Bini, D. and Meini, B., “On cyclic reduction applied to a class of Toeplitz-like matrices arising in queueing problems”, in Proc. 2nd Intern. Workshop on Numerical Solution of Markov Chains, (Raleigh, North Carolina, 1995) 21–38.Google Scholar
[3]Bini, D. and Meini, B., “Improved cyclic reduction for solving queueing problems”, Numer. Algo. rithms 15 (1997) 57–74.Google Scholar
[4]Bini, D. A., Latouche, G. and Meini, B., “Quadratically convergent algorithms for solving matrix polynomial equations”, Technical Report 424, Université Libre Bruxelles, 2000.Google Scholar
[5]Bright, L. W., “Matrix-analytic methods in applied probability”, Ph. D. Thesis, University of Adelaide, 1996.Google Scholar
[6]Hajek, B., “Birth-and-death processes on the integers with phases and general boundaries”, J. Appi. Probab. 19 (1982) 488–499.Google Scholar
[7]Hunt, E., “A probabilistic algorithm for determining the fundamental matrix of a block M/G/l Markov chain”, Math. Comput. Modelling 38 (2003) 1203–1209.Google Scholar
[8]Hunt, E., “A probabilistic algorithm for finding the rate matrix of a block- GI/M/1 Markov chain”, ANZIAM J. 45 (2004) 457–475.CrossRefGoogle Scholar
[9]Latouche, G.. “A note on two matrices occurring in the solution of quasi birth-and-death processes”, Stochastic Models 3 (1987) 251–257.Google Scholar
[10]Latouche, G. and Ramaswami, V., “A logarithmic reduction algorithm foQuasi-Birth-Death processes”, J. Appl. Probab. 30 (1993) 650–674.CrossRefGoogle Scholar
[11]Meini, B., “Solving QBD problems: the cyclic reduction algorithm versus the invaiant subspace method”, Adv. Perf Anal. 1 (1998) 215–225.Google Scholar
[12]Neuts, M. F., Matrix geometric solutions in stochastic models (JohnsHopkins University Press, Baltimore, 1981).Google Scholar
[13]Ramaswami, V., “A duality theorem for the matrix paradigms in queueing theory”, Comm. Statist. Stochastic Models 6 (1990) 151–161.CrossRefGoogle Scholar