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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018027
Classification : 68M20, 60K25, 60J10
Mots clés : Truncation, queueing system, weak stability, algorithm
Issaadi, Badredine 1 ; Abbas, Karim 1 ; Aïssani, Djamil 1

1
@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] J. Abate, G.L. Choudhury and W. Whitt, An introduction to numerical transform inversion and its application to probability models, in Computational Probability, edited by W.K. Grassmann. Kluwer Academic Publishers (2000) 257–323. | DOI | Zbl

[2] N. Bouabdallah, A.L. Beylot, E. Dotaro and G. Pujolle, Resolving the fairness issues in bus-based optical access networks. IEEE J. Sel. Areas Commun. 23 (2005) 1444–1457. | DOI

[3] A. Brandwajn, Models of DASD subsystems with multiple access paths: a throughput-driven approach. IEEE Trans. Comput. C 32 (1983) 451–463. | DOI

[4] R. Butt, Introduction to Numerical Analysis Using MATLAB. Inc., United States (2009).

[5] D. Ferré, L. Hervé and J. Ledoux, Regular perturbation of V -geometrically ergodic Markov chains. J. Appl. Probab. 50 (2013) 184–194. | DOI | MR | Zbl

[6] W. Ford, Numerical Linear Algebra With Applications: Using MATLAB, 1st edn. Academic Press (2015). | MR | Zbl

[7] D. Gibson and E. Seneta, Monotone infinite stochastic matrices and their augmented truncations. Stoch. Process. Appl. 24 (1987) 287–292. | DOI | MR | Zbl

[8] D. Gross and C. Harris, Fundamentals of Queueing Theory. Wiley (1985). | MR | Zbl

[9] L. Hervé and J. Ledoux. Approximating Markov chains and V -geometric ergodicity via weak perturbation theory. Stoch. Process. Appl. 124 (2014) 613–638. | DOI | MR | Zbl

[10] D.P. Heyman, Approximating the stationary distribution of an infinite stochastic matrix. J. Appl. Probab. 28 (1991) 96–103. | DOI | MR | Zbl

[11] B. Issaadi, K. Abbas and D. Aïssani, Perturbation Analysis of the GI/M/s Queue. Methodol. Comput. Appl. Probab. 19 (2017) 819–841. | DOI | MR | Zbl

[12] V.V. Kalashnikov and S.T. Rachev, Mathematical Methods for Construction of Queueing Models. Wadsworth & Brooks Cole (1990). | DOI | MR | Zbl

[13] N.V. Kartashov, Strong Stable Markov Chains. Edition VSP, Utrecht, The Netherlands (1996). | DOI | MR | Zbl

[14] G. Keller and C. Liverani, Stability of the spectrum for transfer operators. Ann. Scuola Norm. Sci. 4 (1999) 141–152. | Numdam | MR | Zbl

[15] Y. Liu, Augmented truncation approximations of discrete-time Markov chains J. Oper. Res. Lett. 38 (2010) 218–222. | DOI | MR | Zbl

[16] C. Liverani, Rigorous numerical investigation of the statistical properties of piecewise expanding maps. A feasibility study. Nonlinearity 14 (2001) 463–490. | DOI | MR | Zbl

[17] S. Meyn and R.L. Tweedie, Markov chains and stochastic stability, 2nd edition. Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo (2009). | DOI | MR | Zbl

[18] M. Molina, P. Castelli and G. Foddis, Web traffic modeling exploiting. TCP connections’ temporal clustering through HTML-REDUCE. IEEE Netw. 14 (2000) 46–55. | DOI

[19] T. A. Sarymsakov, 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] E. Seneta, Finite Approximations to Infinite Non-Negative Matrices. Proc. Cambridge Phil. Soc. 63 (1967) 983–992. | DOI | MR | Zbl

[21] E. Seneta, The Principles of Truncations in Applied Probability. Comm. Math. Univ. North Carolina 9 (1968) 533–539. | MR | Zbl

[22] E. Seneta, Non-negative Matrices and Markov Chains. Springer-Verlag, New York (1980). | MR | Zbl

[23] E. Seneta, Computing the stationary distributon for infinite Markov chains. Linear Algebra Appl. 34 (1980) 259–267. | DOI | MR | Zbl

[24] T. Shardlow and A.M. Stuart, A perturbation theory for ergodic Markov chains and application to numerical approximations. SIAM J. Numer. Anal. 37 (2000) 1120–1137. | DOI | MR | Zbl

[25] F. Simonot, 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] H.C. Tijms, Stochastic modelling and analysis, in A Computational Approach. John Wiley, New York (1986). | MR

[27] R.L. Tweedie, Truncation approximations of invariant measures for markov chains J. Appl. Probab. 35 (1998) 517–536. | DOI | MR | Zbl

[28] D.S. Watkins, The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods. SIAM (2007). | DOI | MR | Zbl

[29] D. Wolf, Approximation of the invariant probability distribution of an infinite stochastic matrix. Adv. Appl. Probab. 12 (1980) 710–726. | DOI | MR | Zbl

Cité par Sources :