Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T05:40:50.941Z Has data issue: false hasContentIssue false
  • English
  • Français

Reduction techniques for discrete-time Markov chains on totally ordered state space using stochastic comparisons

Part of: Distribution theory - Probability

Published online by Cambridge University Press:  14 July 2016

Laurent Truffet
Laurent Truffet*
Affiliation:
Ecole des Mines de Nantes
*
∗Postal address: Ecole des Mines de Nantes, Dpt. Automatique et Productique, 4, rue Alfred Kastler BP 20722, 44307 Nantes, Cedex 3, France. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We propose in this paper two methods to compute Markovian bounds for monotone functions of a discrete time homogeneous Markov chain evolving in a totally ordered state space. The main interest of such methods is to propose algorithms to simplify analysis of transient characteristics such as the output process of a queue, or sojourn time in a subset of states. Construction of bounds are based on two kinds of results: well-known results on stochastic comparison between Markov chains with the same state space; and the fact that in some cases a function of Markov chain is again a homogeneous Markov chain but with smaller state space. Indeed, computation of bounds uses knowledge on the whole initial model. However, only part of this data is necessary at each step of the algorithms.

Keywords

Transient analysisstrong orderexact and ordinary lumpability

MSC classification

Primary: 60E99: None of the above, but in this section
Type
Research Papers
Information
Journal of Applied Probability , Volume 37 , Issue 3 , September 2000 , pp. 795 - 806
Copyright
Copyright © Applied Probability Trust 2000 

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

Buchholz, P. (1994). Exact and ordinary lumpability in finite Markov chains. J. Appl. Prob. 31, 59–75.Google Scholar
Doisy, M. (1992). Comparaison de processus à valeurs dans Zd . In Actes des journées de mathématiques appliquées de Pau-Zaragosse.Google Scholar
Keilson, J., and Kester, A. (1977). Monotone matrices and monotone Markov processes. Stoch. Proc. Appl. 5, 231–241.Google Scholar
Kemeny, J. G., and Snell, J. L. (1960). Finite Markov Chains. Princeton University Press.Google Scholar
Massey, W. A. (1987). Stochastic orderings for Markov processes on partially ordered spaces. Math. Operat. Res. 11, 350–367.Google Scholar
Moulki, M., Beylot, A. L., Truffet, L., and Becker, M. (1998). An aggregation technique to evaluate the performance of a two-stage buffered ATM switch. Ann. Operat. Res. 79, 373–392.Google Scholar
Schweitzer, P. (1984). Aggregation methods for large Markov chains. Math. Comp. Perf. and Reliab. Eds. Iazeola, G. et al. Elsevier North-Holland, Amsterdam.Google Scholar
Stoyan, D. (1976). Comparison Methods for Queues and Other Stochastic Models. John Wiley, New York.Google Scholar
Trémolières, M., Vincent, J. M., and Plateau, B. (1992). Determination of the optimal stochastic upper bound of a Markovian generator. Tech. Rept, LGI-IMAG, Grenoble-FRANCE. RR 906-I-.Google Scholar
Truffet, L. (1996). Geometrical bounds on an output stream of a queue in ATM switch: application to the dimensioning problem. ATM Networks: Performance Modelling and Analysis, Vol. II. Ed. Kouvatsos, D. Chapman and Hall, London.Google Scholar
Truffet, L. (1997). Near complete decomposability: bounding the error by stochastic comparison method. Adv. Appl. Prob. 29, 830–855.CrossRefGoogle Scholar
Truffet, L. (1998). A family of bounds on the output stream of queues with iid batch arrival arising in ATM networks models. In Proc. 4th INFORMS Telecomm. Conf. Boca Raton.Google Scholar