Efficient Solution for a Class of Markov Chain Models of Tandem Queueing Networks

Authors: Chun Wen, Tingzhu Huang

Abstract:

We present a new numerical method for the computation of the steady-state solution of Markov chains. Theoretical analyses show that the proposed method, with a contraction factor α, converges to the one-dimensional null space of singular linear systems of the form Ax = 0. Numerical experiments are used to illustrate the effectiveness of the proposed method, with applications to a class of interesting models in the domain of tandem queueing networks.

Keywords: Markov chains, tandem queueing networks, convergence, effectiveness.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077605

References:

[1] E. Seneta, Non-Negative Matrices, John Wiley, New York, 1973.
[2] H. De Sterck, T.A. Manteuffel, S.F. McCormick, K. Miller, J. Pearson, J. Ruge, and G. Sanders, Smoothed aggregation multigrid for Markov chains, SIAM J. Sci. Comput., 2010, 32 (1): 40-61.
[3] G. Latouche, V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling, ASA-SIAM series on statistics and applied probability, 1999.
[4] S.D. Kamvar, T.H. Haveliwala, C.D. Manning, G.H. Golub, Extrapolation methods for accelerating PageRank computations, Proceedings of the Twelfth International World Wide Web Conference, 2003, pp. 261-270.
[5] B. Philippe, Y. Saad, W.J. Stewart, Numerical methods in Markov Chain modeling, Operations Research, 1992, 40 (6): 1156-1179.
[6] Z.-Z. Bai, G.H. Golub, L.-Z. Lu, J.F. Yin, Block triangular and skew- Hermitian splitting methods for positive-definite linear systems, SIAM J. Sci. Comput., 2005, 26 (3): 844-863.
[7] Z.-Z. Bai, G.H. Golub, M.K. Ng, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 2003, 24 (3): 603-626.
[8] A. Berman, R.J. Plemmons, Nonnegative Matrices in the Mathematics Science, Classics Allp. Math. 9, SIAM, Philadelphia, 1994.