×

Algorithms for an irreducible and lumpable strong stochastic bound. (English) Zbl 1050.65006

As an extension of Vincent algorithm, a fairly new method based on the algorithmic derivation of a lumpable stochastic bounding matrix is proposed in order to analyze large state-space problems related to discrete time Markov chains with transition matrix \(P\). The main idea is to choose heuristically a partition which implies a large reduction of the state-space and may provide an appropriate irreducible, upper bound \(R\) for \(P\) during the bounding process. Because of the lumpability of the upper bound \(R\), the related numerical analysis deals with smaller matrices, and the lumped version is stored on the disk.
The implementation is done using only 2 vectors in the memory. A basic algorithm IMSUB deals with the irreducibility of the bounding matrix. The method is purely algorithmic and algebraic, and it does not require proofs based on the sample-path theorem and coupling [see D. Stoyan, Comparison methods for queues and other stochastic models, (Wiley) (1983; Zbl 0536.60085) for some examples)].
The algorithm is very efficient since it avoids to keep the entire transition matrix \(P\) in main memory. Monotonicity and comparability of one step transition probability matrices of time-homogeneous Markov chains is discussed too. An application of the proposed algorithm to the computation of the loss probabilities in a shared buffer with the Robin service discipline and the Pushout memory access algorithm is presented.

MSC:

65C50 Other computational problems in probability (MSC2010)
60J22 Computational methods in Markov chains
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J05 Discrete-time Markov processes on general state spaces
65C40 Numerical analysis or methods applied to Markov chains

Citations:

Zbl 0536.60085

Software:

MARCA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] O. Abu-Amsha, J.-M. Vincent, An algorithm to bound functionals of Markov chains with large state space, in: 4th INFORMS Conference on Telecommunications, Boca Raton, Florida, 1998; O. Abu-Amsha, J.-M. Vincent, An algorithm to bound functionals of Markov chains with large state space, in: 4th INFORMS Conference on Telecommunications, Boca Raton, Florida, 1998
[2] M. Benmammoun, J.M. Fourneau, N. Pekergin, A. Troubnikoff, An algorithmic and numerical approach to bound the performance of high speed networks, IEEE MASCOTS 2002, Fort Worth, USA, pp. 375-382; M. Benmammoun, J.M. Fourneau, N. Pekergin, A. Troubnikoff, An algorithmic and numerical approach to bound the performance of high speed networks, IEEE MASCOTS 2002, Fort Worth, USA, pp. 375-382
[3] Buchholz, P., Exact and ordinary lumpability in finite Markov chains, J. Appl. Probab., 31, 3159-3175 (1994)
[4] Buchholz, P., An iterative bounding method for stochastic automata networks, Perform. Eval., 49, 211-226 (2002) · Zbl 1043.68066
[5] Courtois, P. J.; Semal, P., Computable bounds for conditional steady-state probabilities in large Markov chains and queueing models, IEEE JSAC, 4, 6 (1986) · Zbl 0612.65020
[6] Dayar, T.; Stewart, W. J., Comparison of partitioning techniques for two-level iterative solvers on large sparse Markov chains, SIAM J. Sci. Comput., 21, 1691-1705 (2000) · Zbl 0957.60076
[7] S. Donatelli, Superposed generalized stochastic Petri nets: definition and efficient solution, in: Proceedings of the 15th International Conference on Application and Theory of Petri Nets, Zaragoza, Spain, June 1994; S. Donatelli, Superposed generalized stochastic Petri nets: definition and efficient solution, in: Proceedings of the 15th International Conference on Application and Theory of Petri Nets, Zaragoza, Spain, June 1994
[8] J.M. Fourneau, N. Pekergin, An algorithmic approach to stochastic bounds, LNCS 2459, Performance evaluation of complex systems: techniques and tools, 2002, pp. 64-88; J.M. Fourneau, N. Pekergin, An algorithmic approach to stochastic bounds, LNCS 2459, Performance evaluation of complex systems: techniques and tools, 2002, pp. 64-88 · Zbl 1017.68502
[9] J.M. Fourneau, M. Le Coz, N. Pekergin, F. Quessette, An open tool to compute stochastic bounds on steady-state distributions and rewards, IEEE Mascots 03, USA, 2003; J.M. Fourneau, M. Le Coz, N. Pekergin, F. Quessette, An open tool to compute stochastic bounds on steady-state distributions and rewards, IEEE Mascots 03, USA, 2003
[10] G.Hébuterne, A. Gravey, A space priority queueing mechanism for multiplexing ATM channels, ITC Specialist Seminar, Computer Network and ISDN Systems, vol. 20, December 1990, pp. 37-43; G.Hébuterne, A. Gravey, A space priority queueing mechanism for multiplexing ATM channels, ITC Specialist Seminar, Computer Network and ISDN Systems, vol. 20, December 1990, pp. 37-43
[11] Keilson, J.; Kester, A., Monotone matrices and monotone Markov processes, Stoch. Process. Appl., 5, 231-241 (1977) · Zbl 0367.60078
[12] B. Plateau, On the stochastic structure of parallelism and synchronization models for distributed algorithms, in: Proceedings of the SIGMETRICS Conference, Texas, 1985, pp. 147-154; B. Plateau, On the stochastic structure of parallelism and synchronization models for distributed algorithms, in: Proceedings of the SIGMETRICS Conference, Texas, 1985, pp. 147-154
[13] Stewart, W. J., Introduction to the Numerical Solution of Markov Chains (1994), Princeton University Press · Zbl 0821.65099
[14] Stewart, W. J.; Atif, K.; Plateau, B., The numerical solution of stochastic automata networks, European J. Oper. Res., 86, 503-525 (1995) · Zbl 0914.90112
[15] Stoyan, D., Comparison Methods for Queues and Other Stochastic Models (1983), Wiley
[16] Truffet, L., Reduction technique for discrete time Markov chains on totally ordered state space using stochastic comparisons, J. Appl. Probab., 37, 3 (2000) · Zbl 0971.60022
[17] Uysal, E.; Dayar, T., Iterative methods based on splittings for stochastic automata networks, European J. Oper. Res., 110, 166-186 (1998) · Zbl 0934.93061
[18] N. Van Dijk, Error bound analysis for queueing networks, Performance 96 Tutorials, Lausanne, 1996; N. Van Dijk, Error bound analysis for queueing networks, Performance 96 Tutorials, Lausanne, 1996
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.