×

Componentwise bounds for nearly completely decomposable Markov chains using stochastic comparison and reordering. (English) Zbl 1141.60360

Summary: This paper presents an improved version of a componentwise bounding algorithm for the state probability vector of nearly completely decomposable Markov chains, and on an application it provides the first numerical results with the type of algorithm discussed. The given two-level algorithm uses aggregation and stochastic comparison with the strong stochastic (st) order. In order to improve accuracy, it employs reordering of states and a better componentwise probability bounding algorithm given st upper- and lower-bounding probability vectors. Results in sparse storage show that there are cases in which the given algorithm proves to be useful.

MSC:

60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)

Software:

MARCA
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] O. Abu-Amsha, J.-M. Vincent, An algorithm to bound functionals of Markov chains with large state space, Rapport de recherche MAI n 25, IMAG, Grenoble, France, 1996; O. Abu-Amsha, J.-M. Vincent, An algorithm to bound functionals of Markov chains with large state space, Rapport de recherche MAI n 25, IMAG, Grenoble, France, 1996
[2] Courtois, P.-J., Decomposability: Queueing and Computer System Applications (1977), Academic Press: Academic Press New York · Zbl 0368.68004
[3] Courtois, P.-J.; Semal, P., Bounds for the positive eigenvectors of nonnegative matrices and for their approximations by decomposition, Journal of the Association for Computer Machinery, 31, 804-825 (1984) · Zbl 0628.65029
[4] T. Dayar, Permuting Markov chains to nearly completely decomposable form, Technical Report BU-CEIS-9808, Department of Computer Engineering and Information Science, Bilkent University, Ankara, Turkey, 1998, Available from <>; T. Dayar, Permuting Markov chains to nearly completely decomposable form, Technical Report BU-CEIS-9808, Department of Computer Engineering and Information Science, Bilkent University, Ankara, Turkey, 1998, Available from <>
[5] T. Dayar, N. Pekergin, Stochastic comparison, reorderings, and nearly completely decomposable markov chains (NSMC’99), in: B. Plateau, W.J. Stewart, M. Silva (Eds.), Numerical Solution of Markov Chains, Prensas Universitarias de Zaragoza, Spain, 1999, pp. 228-246; T. Dayar, N. Pekergin, Stochastic comparison, reorderings, and nearly completely decomposable markov chains (NSMC’99), in: B. Plateau, W.J. Stewart, M. Silva (Eds.), Numerical Solution of Markov Chains, Prensas Universitarias de Zaragoza, Spain, 1999, pp. 228-246
[6] Dayar, T.; Stewart, W. J., Comparison of partitioning techniques for two-level iterative solvers on large, sparse Markov chains, SIAM Journal on Scientific Computing, 21, 1691-1705 (2000) · Zbl 0957.60076
[7] Dayar, T.; Stewart, W. J., On the effects of using the Grassmann-Taksar-Heyman method in iterative aggregation-disaggregation, SIAM Journal on Scientific Computing, 17, 287-303 (1996) · Zbl 0840.60062
[8] Grassmann, W. K.; Taksar, M. I.; Heyman, D. P., Regenerative analysis and steady state distributions for Markov chains, Operations Research, 33, 1107-1116 (1985) · Zbl 0576.60083
[9] Kamburowski, J., Stochastically minimizing the makespan in two-machine flow shops without blocking, European Journal of Operational Research, 112, 304-309 (1999) · Zbl 0938.90029
[10] Keilson, J.; Kester, A., Monotone matrices and monotone Markov processes, Stochastic Processes and Their Applications, 5, 231-241 (1977) · Zbl 0367.60078
[11] Massey, W. A., Stochastic orderings for Markov processes on partially ordered spaces, Mathematics of Operations Research, 12, 350-367 (1987) · Zbl 0622.60098
[12] Meyer, C. D., Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems, SIAM Review, 31, 240-272 (1989) · Zbl 0685.65129
[13] N. Pekergin, Stochastic delay bounds on fair queueing algorithms, in: Proceedings of INFOCOM’99, New York, 1999, pp. 1212-1220; N. Pekergin, Stochastic delay bounds on fair queueing algorithms, in: Proceedings of INFOCOM’99, New York, 1999, pp. 1212-1220
[14] Pekergin, N., Stochastic performance bounds by state reduction, Performance Evaluation, 36-37, 1-17 (1999) · Zbl 1051.68528
[15] N. Pekergin, T. Dayar, D.N. Alparslan, Componentwise bounds for nearly completely decomposable Markov chains using stochastic comparison and reordering, Technical Report BU-CE-0202, Department of Computer Engineering, Bilkent University, Ankara, Turkey, 2002, Available from <>; N. Pekergin, T. Dayar, D.N. Alparslan, Componentwise bounds for nearly completely decomposable Markov chains using stochastic comparison and reordering, Technical Report BU-CE-0202, Department of Computer Engineering, Bilkent University, Ankara, Turkey, 2002, Available from <> · Zbl 1141.60360
[16] P. Semal, Analysis of large Markov models, bounding techniques and applications, Doctoral Thesis, Université Catholique de Louvain, Belgium, 1992; P. Semal, Analysis of large Markov models, bounding techniques and applications, Doctoral Thesis, Université Catholique de Louvain, Belgium, 1992
[17] Shaked, M.; Shantikumar, J. G., Stochastic Orders and Their Applications (1994), Academic Press: Academic Press San Diego, CA
[18] Skelly, P.; Schwartz, M.; Dixit, S., A histogram-based model for video traffic behavior in an ATM multiplexer, IEEE/ACM Transactions on Networking, 1, 446-459 (1993)
[19] Stewart, W. J., Introduction to the Numerical Solution of Markov Chains (1994), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0821.65099
[20] Stoyan, D., Comparison Methods for Queues and Other Stochastic Models (1983), John Wiley & Sons: John Wiley & Sons Berlin, Germany
[21] M. Tremolieres, J.-M. Vincent, B. Plateau, Determination of the optimal upper bound of a Markovian generator, Technical Report 106, LGI-IMAG, Grenoble, France, 1992; M. Tremolieres, J.-M. Vincent, B. Plateau, Determination of the optimal upper bound of a Markovian generator, Technical Report 106, LGI-IMAG, Grenoble, France, 1992
[22] Truffet, L., Near complete decomposability: Bounding the error by stochastic comparison method, Advances in Applied Probability, 29, 830-855 (1997) · Zbl 0892.60101
[23] Vèque, V.; Ben-Othman, J., MRAP: A multiservices resource allocation policy for wireless ATM network, Computer Networks and ISDN Systems, 29, 2187-2200 (1998)
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.