Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-09T01:19:28.254Z Has data issue: false hasContentIssue false
  • English
  • Français

Near Complete Decomposability: Bounding the Error by a Stochastic Comparison Method

Part of: Special processes

Published online by Cambridge University Press:  01 July 2016

Laurent Truffet
Laurent Truffet*
Affiliation:
Université Paris VI
*
∗ Postal address: Université Paris VI, Institut Blaise Pascal, Laboratoire MASI-CNRS UA 818, 4, Place Jussieu, F-75252, Paris Cedex 05, France.
Get access Rights & Permissions [Opens in a new window]

Abstract

An aggregation technique of ‘near complete decomposable' Markovian systems has been proposed by Courtois [3]. It is an approximate method in many cases, except for some queuing networks, so the error between the exact and the approximate solution is an important problem. We know that the error is O(ε), where ε is defined as the maximum coupling between aggregates. Some authors developed techniques to obtain a O(ε k) error with k > 1 error with k > 1, while others developed a technique called ‘bounded aggregation’. All these techniques use linear algebra tools and do not utilize the fact that the steady-state probability vector represents the distribution of a random variable. In this work we propose a stochastic approach and we give a method to obtain stochastic bounds on all possible Markovian approximations of the two main dynamics: short-term and long-term dynamics.

Keywords

NEAR COMPLETE DECOMPOSABILITYSTOCHASTIC BOUNDSMATRIX COMPARISONSTRONG ORDERING

MSC classification

Primary: 60K99: None of the above, but in this section
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 29 , Issue 3 , September 1997 , pp. 830 - 855
Copyright
Copyright © Applied Probability Trust 1997 

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

[1] Abu-Amsha, O. (1995) Evaluation de performance: Méthode d'encadrements stochastiques dans les réseaux d'automates stochastiques. Technical report. DEA INPG-ENSIMAG.Google Scholar
[2] Abu-Amsha, O. and Vincent, J.-M. (1995) An algorithm to bound functionals of Markov chains with large state space. Technical report. Google Scholar
[3] Courtois, P. J. (1977) Decomposability: Queueing and Computer Systems Applications. Academic Press, London.Google Scholar
[4] Courtois, P. J. (1978) Exact aggregation in queueing networks. In Proc. 1st AFCET-SMF Meeting on Appl. Math. Ecole Polytechn, Palaiseau. Tome I. pp. 35–51.Google Scholar
[5] Courtois, P. J. (1982) Error minimization in decomposable stochastic models. Appl. Prob. Comp. Sci. 1.Google Scholar
[6] Courtois, P. J. and Semal, P. (1984) Bounds for the positive eigenvectors of non-negative matrices and for their approximations by decomposition. J. Assoc. Comput. Mach. 31, 804–825.Google Scholar
[7] Courtois, P. J. and Semal, P. (1985) On polyhedra of Perron-Frobenius eigenvectors. Linear Algebra Appl. 65, 157–170.CrossRefGoogle Scholar
[8] Daley, D. J. (1968) Stochastically monotone Markov chains. Z. Wahrscheinlichkeitsth. 10, 305–317.CrossRefGoogle Scholar
[9] Franceschinis, G. and Muntz, R. R. (1994) Bounds for quasi-lumpable Markov chains. Perf. Eval. 20, 223–244.Google Scholar
[10] Kester, A. and Keilson, J. (1977) Monotone matrices and monotone Markov processes. Stoch. Proc. Appl. 5, 231–241.Google Scholar
[11] Massey, W. A. (1987) Stochastics orderings for Markov processes on partially ordered spaces. Math. Operat. Res. 11, 350–367.CrossRefGoogle Scholar
[12] Muntz, R. R., De Souza E Silva, E. and Goyal, A. (1989) Bounding availability of repairable computer systems. In ACM Sigmetrics and Performance '89 17, 29–38.CrossRefGoogle Scholar
[13] Ross, S. M. (1982) Stochastic Processes. Wiley, New York.Google Scholar
[14] Simon, H. A. and Ando, A. (1961) Aggregation of variables in dynamic systems. Econometrica 29.Google Scholar
[15] Stewart, G. W. (1987) Computable error bounds for aggregated Markov chains. J. Assoc. Comput. Mach. 30, 271–285.Google Scholar
[16] Stoyan, D. (1970) Comparison Methods for Queues and Other Stochastic Models. Wiley, New York.Google Scholar
[17] Tremolieres, M., Vincent, J. M. and Plateau, B. (1992) Determination of the optimal stochastic upper bound of a Markovian generator. Technical report. Grenoble.Google Scholar
[18] Vantilborgh, H. (1978) Exact aggregation in exponential queueing networks. J. Assoc. Comput. Mach. 25, 620–629.Google Scholar
[19] Vantilborgh, H. (1985) Aggregation with an error of O(e2). J. Assoc. Comput. Mach. 32, 162–190.Google Scholar
[20] Vincent, J.-M. (1994) Encadrement de performances: une approche algorithmique. Technical report. Google Scholar
[21] Whitt, W. (1986) Stochastic comparisons for non-Markov processes. Math. Operat Res. 11, 608–618.Google Scholar