Lorden's inequality and the rate of convergence of the distribution of one generalized erlang -- sevast'yanov queuing system

Cover Page

Cite item

Full Text

Abstract

It is more important to estimate the rate of convergence to a stationary distribution rather than only to prove the existence one in many applied problems of reliability and queuing theory. This can be done via standard methods, but only under assumptions about an exponential distribution of service time, independent intervals between recovery times, etc. Results for such simplest cases are well-known. Rejection of these assumptions results to rather complex stochastic processes that cannot be studied using standard algorithms. A more sophisticated approach is needed for such processes. That requires generalizations and proofs of some classical results for a more general case. One of them is the generalized Lorden's inequality proved in this paper. We propose the generalized version of this inequality for the case of dependent and arbitrarily distributed intervals between recovery times. This generalization allows to find upper bounds for the rate of convergence for a wide class of complicated processes arising in the theory of reliability. The rate of convergence for a two-component process has been obtained via the generalized Lorden's inequality in this paper.

About the authors

Galina Aleksandrovna Zverkina

V.A. Trapeznikov Institute of Control Sciences of RAS

Author for correspondence.
Email: zverkina@gmail.com
Moscow

References

  1. Аничкин С. А. Склеивание процессов восстановления и его применение // Проблемы устойчивости стохастических моделей. Труды семинара. – 1984. – М.: ВНИИСИ. – С. 4–24.
  2. Борисов И. С. Методы одного вероятностного пространства для марковских процессов // Тр. Ин-та математики. – 1982. – Т. 1. – С. 4–18.
  3. Боровков А. А. Обобщенные процессы восстановления. – М.: Российская академия наук, 2020. – 453 с.
  4. Севастьянов Б. А. Формулы Эрланга в телефонии при произвольном законе распределения длительности разговора // Труды Третьего Всесоюзного математического съезда, Москва, июнь–июль 1956. – 1959. – Т. 4. – М.: Изд-во АН СССР. – С. 121–135.
  5. Севастьянов Б. А. Эргодическая теорема для марковских процессов и ее приложение к телефонным системам с отказами // Теория вероятн. и ее примен. – 1957. – Т. 2, вып. 1. – С. 106–116.
  6. Шелепова А. Д., Саханенко А. И. Об асимптотике вероятности невыхода неоднородного обобщенного процесса восстановления за невозрастающую границу // Сиб. электрон. матем. изв. – 2021. – Т. 18:2. – С. 1667–1688.
  7. Afanasyeva L. G., Tkachenko A. V. On the convergence rate for queueing and reliability models described by regenerative processes // Journal of Mathematical Sciences. – 2016. – Vol. 218, Issue 2. – P. 119–136.
  8. Asmussen S. Applied Probability and Queues. – New York: Springer, 2003.
  9. Chang J. T. Inequalities for the overshoot // The Annals of Applied Probability. – 1994. – Vol. 4(4). – P. 1223.
  10. Doeblin W. Exposé de la théorie des chaînes simples constantes de Markov à un nombre fini d’états // Rev. Math. de l’Union Interbalkanique. – 1938. – Vol. 2. – P. 77–105.
  11. Erlang A. K. Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges // Elektroteknikeren. – 1917. – Vol. 13. – P. 5–13 (in Danish); Engl. transl.: P. O. Elect. Eng. Journal. – 1918. – Vol. 10. – P. 189–197; Reprinted as: WEB-based edition by permission from the Danish Acad. Techn. Sci. at http://oldwww.com.dtu.dk/teletraffic/Erlang.html.
  12. Ferreira M. A., Andrade M. The M|G|∞ queue busy period distribution exponentiality // Journal of Applied Mathematics. – 2011. – Vol. 4, No. 3. – P. 249–260.
  13. Fortet R. Calcul des probabilités. – Paris: CNRS, 1950.
  14. Griffeath D. A maximal coupling for Markov chains // Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete. – 1975. – Vol. 31, Iss. 2. – P. 95–106.
  15. Kalashnikov V. V. Mathematical Methods in Queuing Theory. – Amsterdam: Kluwer Academic Publishers, 1994.
  16. Kalimulina E., Zverkina G. On some generalization of Lorden’s inequality for renewal processes // arXiv.org. – Cornell: Cornell University Library. – 2019. – 1910.03381v1. – P. 1–5.
  17. Kato K. Coupling lemma and its application to the security analysis of quantum key distribution // Tamagawa University Quantum ICT Research Institute Bulletin. – 2014. – Vol. 4, No. 1. – P. 23–30.
  18. Lorden G. On excess over the boundary // The Annals of Mathematical Statistics. – 1970. – Vol. 41(2). – P. 520–527.
  19. Pechinkin A. V. On an invariant queueing system // Math. Operationsforsch. Statist. Ser. Optim. – 1983. – Vol. 14(3). – P. 433–444.
  20. Pechinkin A. V., Solovyev A. D., Yashkov S. F. A system with servicing discipline whereby the order of minimum remaining length is serviced first // Eng. Cybern. – 1979. – Vol. 17(5). – P. 38–45.
  21. Smith W. L. Renewal theory and its ramifications // J. Roy. Statist. Soc. – 1958. – Ser. B, Vol. 20:2. – P. 243–302.
  22. Stadje W. The busy period of the queueing system M|G|∞ // Journal of Applied Probability. – 1985. – Vol. 22. – P. 697–704.
  23. Stoyan D. Qualitative Eigenschaften und Abschätzungen stochastischer Modelle. – Berlin, 1977.
  24. Takács L. Introduction to the Theory of Queues. – Oxford University Press, 1962.
  25. Van Doorn E. A., Zeifman A. I. On the speed of convergence to stationarity of the Erlang loss system // Queueing Systems. – 2009. – Vol. 63. – P. 241–252.
  26. Veretennikov A. Yu. On rate of convergence to the stationary distribution in queueing systems with one serving device // Automation and Remote Control. – 2013. – Vol. 74, Iss. 10. – P. 1620–1629.
  27. Veretennikov A. Yu. On the rate of mixing and convergence to a stationary distribution in Erlang-type systems in continuous time // Problems Inf. Transmiss. – 2010. – Vol. 46(4). – P. 382–389.
  28. Veretennikov A. Yu. The ergodicity of service systems with an infinite number of servomechanisms // Математические заметки. – 1977. – Vol. 22(4). – P. 804–808.
  29. Veretennikov A., Butkovsky O. A. On asymptotics for Vaserstein coupling of Markov chains // Stochastic Processes and their Applications. – 2013. – Vol. 123(9). – P. 3518–3541.
  30. Veretennikov A. Yu., Zverkina G. A. Simple proof of Dynkin’s formula for single-server systems and polynomial convergence rates // Markov Proc. Rel. Fields. – 2014. – Vol. 20, Iss. 3. – P. 479–504; arXiv:1306.2359 [math.PR] (2013).
  31. Zverkina G. On strong bounds of rate of convergence for regenerative processes // Communications in Computer and Information Science. – 2016. – Vol. 678. – P. 381–393.
  32. Zverkina G. Lorden’s inequality and coupling method for backward renewal process // Proc. of XX Int. Conf. on Distributed Computer and Communication Networks: Control, Computation, Communications (DCCN–2017, Moscow). – 2017. – P. 484–491.
  33. Zverkina G. On strong bounds of rate of convergence for regenerative processes // Communications in Computer and Information Science. – 2016. – Vol. 678. – P. 381–393.
  34. Zverkina G. About some extended Erlang–Sevast’yanov queueing system and its convergence rate (English and Russian versions) // https://arxiv.org/abs/1805.04915; Фундаментальная и прикладная математика. – 2018. – №22, Iss. 3. – P. 57–82.
  35. Zverkina G., Kalimulina E. On generalized intensity function and its application to the backward renewal time estimation for renewal processes // Proc. of the 5th Int. Conf. on Stochastic Methods (ICSM–5, 2020). – М.: Изд-во РУДН, 2020. – P. 306–310.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).