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.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

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