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

GENERALIZED CLASS [Cscr ] MARKOV CHAINS AND COMPUTATION OF CLOSED-FORM BOUNDING DISTRIBUTIONS

Published online by Cambridge University Press:  27 February 2007

Mouad Ben Mamoun ,
Ana Bušić  and
Nihal Pekergin
Mouad Ben Mamoun
Affiliation:
PRiSM, Université Versailles St Quentin, 78035 Versailles, France, and, Université Mohammed V, Rabat, Maroc
Ana Bušić
Affiliation:
PRiSM, Université Versailles St Quentin, 78035 Versailles, France
Nihal Pekergin
Affiliation:
PRiSM, Université Versailles St Quentin, 78035 Versailles, France, and, Centre Marin Mersenne, Université Paris 1, 75013 Paris, France, E-mail: {mobe,abusic,nih}@prism.uvsq.fr
Get access Rights & Permissions [Opens in a new window]

Abstract

In this article we first give a characterization of a class of probability transition matrices having closed-form solutions for transient distributions and the steady-state distribution. We propose to apply the stochastic comparison approach to construct bounding chains belonging to this class. Therefore, bounding chains can be analyzed efficiently through closed-form solutions in order to provide bounds on the distributions of the considered Markov chain. We present algorithms to construct upper-bounding matrices in the sense of the ≤st and ≤icx order.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 21 , Issue 2 , April 2007 , pp. 235 - 260
Copyright
© 2007 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Abu-amsha, O. & Vincent, J.M. (1998). An algorithm to bound functionals of Markov chains with large state space. In 4th INFORMS Conference on Telecommunications, Florida.
Ben Mamoun, M. (2002). Encadrements stochastiques et évaluation de performances des réseaux. PhD thesis, University of Versailles.
Ben Mamoun, M. & Pekergin, N. (2000). Computing closed-form stochastic bounds on the stationary distribution of Markov chains. In D. Gardy & A. Mokkadem (eds.), Mathematics and computer science: Algorithms, trees, combinatorics and probabilities. Basel: Birkhauser-Verlag, pp. 197–209.
Ben Mamoun, M. & Pekergin, N. (2002). Closed-form stochastic bounds on the stationary distribution of Markov chains. Probability in the Engineering and Informational Sciences 16: 403–426.Google Scholar
Ben Mamoun, M. & Pekergin, N. (2005). Computing closed-form stochastic bounds on transient distributions of Markov chains. In M. Papazoglu & K. Yamazaki (eds.), Applications and the Internet SAINT2005 workshops. New York: IEEE Computer Society, pp. 260–263.
Courtois, P.J. & Semal, P. (1984). Bounds for the positive eigenvectors of nonnegative matrices and their approximation by decomposition. Journal of the ACM 31(4): 804–825.Google Scholar
Fourneau, J.M. & Pekergin, N. (2002). An algorithmic approach to stochastic bounds. In M. Calzrossa & S. Tucci (eds.), Performance evaluation of complex systems: Techniques and tools. Berlin: Springer-Verlag, pp. 64–89.
Golubchik, L. & Lui, J. (1997). Bounding of performance measures for a threshold-based queuing systems with hysteresis. In Proceeding of ACM SIGMETRICS'97, pp. 147–157.
Keilson, J. & Kester, A. (1977). Monotone matrices and monotone Markov processes. Stochastic Processes and their Applications 5: 231–241.Google Scholar
Li, H. & Shaked, M. (1994). Stochastic convexity and concavity of Markov processes. Mathematics in Operations Research 19(2): 477–493.Google Scholar
Lui, J., Muntz, R., & Towsley, D. (1998). Computing performance bounds of Fork–Join parallel programs under a multiprocessing environment. IEEE Transactions on Parallel and Distributed Systems 9(3): 295–311.Google Scholar
Mahevas, S. & Rubino, G. (2001). Bound computation of dependability and performance measures. IEEE Transactions on Computers 50(5): 399–413.Google Scholar
Muller, A. & Stoyan, D. (2002). Comparison methods for stochastic models and risks. New York: Wiley.
Muntz, R.R. & Lui, J. (1994). Computing bounds on steady-state availability of repairable computer systems. Journal of the ACM 41(4): 676–707.Google Scholar
Pekergin, N. (1999). Stochastic performance bounds by state space reduction. Performance Evaluation 36–37, 1–17.
Shaked, M. & Shantikumar, J.G. (1994). Stochastic orders and their applications. San Diego: Academic Press.
Stewart, W.J. (1994). Introduction to the numerical solution of Markov chains. Princeton, NJ: Princeton University Press.
van Dijk, N.M. (1998). Bounds and error bounds for queueuing networks. Annals of Operations Research 79: 295–319.Google Scholar
van Dijk, N.M. & van der Wal, J. (1989). Simple bounds and monotonicity results for finite multi-server exponential tandem queues. Queueing Systems 4: 1–16.Google Scholar