The calculation of the stationary distribution for a stochastic infinite matrix is generally difficult and does not have closed form solutions, it is desirable to have simple approximations converging rapidly to this distribution. In this paper, we use the weak perturbation theory to establish analytic error bounds for the M/G/1 model. Numerical examples are carried out to illustrate the quality of the obtained error bounds.
Accepté le :
DOI : 10.1051/ro/2018027
Mots clés : Truncation, queueing system, weak stability, algorithm
@article{RO_2018__52_4-5_1411_0,
author = {Issaadi, Badredine and Abbas, Karim and A{\"\i}ssani, Djamil},
title = {A weak perturbation theory for approximations of invariant measures in {M/G/1} model},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1411--1428},
publisher = {EDP-Sciences},
volume = {52},
number = {4-5},
year = {2018},
doi = {10.1051/ro/2018027},
zbl = {1430.60075},
mrnumber = {3884159},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2018027/}
}
TY - JOUR AU - Issaadi, Badredine AU - Abbas, Karim AU - Aïssani, Djamil TI - A weak perturbation theory for approximations of invariant measures in M/G/1 model JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 1411 EP - 1428 VL - 52 IS - 4-5 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2018027/ DO - 10.1051/ro/2018027 LA - en ID - RO_2018__52_4-5_1411_0 ER -
%0 Journal Article %A Issaadi, Badredine %A Abbas, Karim %A Aïssani, Djamil %T A weak perturbation theory for approximations of invariant measures in M/G/1 model %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 1411-1428 %V 52 %N 4-5 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2018027/ %R 10.1051/ro/2018027 %G en %F RO_2018__52_4-5_1411_0
Issaadi, Badredine; Abbas, Karim; Aïssani, Djamil. A weak perturbation theory for approximations of invariant measures in M/G/1 model. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1411-1428. doi : 10.1051/ro/2018027. http://www.numdam.org/articles/10.1051/ro/2018027/
[1] , and , An introduction to numerical transform inversion and its application to probability models, in Computational Probability, edited by . Kluwer Academic Publishers (2000) 257–323. | DOI | Zbl
[2] , , and , Resolving the fairness issues in bus-based optical access networks. IEEE J. Sel. Areas Commun. 23 (2005) 1444–1457. | DOI
[3] , Models of DASD subsystems with multiple access paths: a throughput-driven approach. IEEE Trans. Comput. C 32 (1983) 451–463. | DOI
[4] , Introduction to Numerical Analysis Using MATLAB. Inc., United States (2009).
[5] , and , Regular perturbation of V -geometrically ergodic Markov chains. J. Appl. Probab. 50 (2013) 184–194. | DOI | MR | Zbl
[6] , Numerical Linear Algebra With Applications: Using MATLAB, 1st edn. Academic Press (2015). | MR | Zbl
[7] and , Monotone infinite stochastic matrices and their augmented truncations. Stoch. Process. Appl. 24 (1987) 287–292. | DOI | MR | Zbl
[8] and , Fundamentals of Queueing Theory. Wiley (1985). | MR | Zbl
[9] and Approximating Markov chains and V -geometric ergodicity via weak perturbation theory. Stoch. Process. Appl. 124 (2014) 613–638. | DOI | MR | Zbl
[10] , Approximating the stationary distribution of an infinite stochastic matrix. J. Appl. Probab. 28 (1991) 96–103. | DOI | MR | Zbl
[11] , and , Perturbation Analysis of the GI/M/s Queue. Methodol. Comput. Appl. Probab. 19 (2017) 819–841. | DOI | MR | Zbl
[12] and , Mathematical Methods for Construction of Queueing Models. Wadsworth & Brooks Cole (1990). | DOI | MR | Zbl
[13] , Strong Stable Markov Chains. Edition VSP, Utrecht, The Netherlands (1996). | DOI | MR | Zbl
[14] and , Stability of the spectrum for transfer operators. Ann. Scuola Norm. Sci. 4 (1999) 141–152. | Numdam | MR | Zbl
[15] , Augmented truncation approximations of discrete-time Markov chains J. Oper. Res. Lett. 38 (2010) 218–222. | DOI | MR | Zbl
[16] , Rigorous numerical investigation of the statistical properties of piecewise expanding maps. A feasibility study. Nonlinearity 14 (2001) 463–490. | DOI | MR | Zbl
[17] and , Markov chains and stochastic stability, 2nd edition. Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo (2009). | DOI | MR | Zbl
[18] , and , Web traffic modeling exploiting. TCP connections’ temporal clustering through HTML-REDUCE. IEEE Netw. 14 (2000) 46–55. | DOI
[19] , Sur les Chaines de Markoff a une Infinite Dénombrable d’États Possibles. Doklady Akad. Sci. U.R.S.S 48 (1945) 159–161. | Zbl
[20] , Finite Approximations to Infinite Non-Negative Matrices. Proc. Cambridge Phil. Soc. 63 (1967) 983–992. | DOI | MR | Zbl
[21] , The Principles of Truncations in Applied Probability. Comm. Math. Univ. North Carolina 9 (1968) 533–539. | MR | Zbl
[22] , Non-negative Matrices and Markov Chains. Springer-Verlag, New York (1980). | MR | Zbl
[23] , Computing the stationary distributon for infinite Markov chains. Linear Algebra Appl. 34 (1980) 259–267. | DOI | MR | Zbl
[24] and , A perturbation theory for ergodic Markov chains and application to numerical approximations. SIAM J. Numer. Anal. 37 (2000) 1120–1137. | DOI | MR | Zbl
[25] , Sur l’approximation de la distribution stationnaire d’une chaine de Markov stochastiquement monotone. Stoch. Process. Appl. 56 (1995) 133–149. | DOI | MR | Zbl
[26] , Stochastic modelling and analysis, in A Computational Approach. John Wiley, New York (1986). | MR
[27] , Truncation approximations of invariant measures for markov chains J. Appl. Probab. 35 (1998) 517–536. | DOI | MR | Zbl
[28] , The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods. SIAM (2007). | DOI | MR | Zbl
[29] , Approximation of the invariant probability distribution of an infinite stochastic matrix. Adv. Appl. Probab. 12 (1980) 710–726. | DOI | MR | Zbl
Cité par Sources :
