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

Email: zverkina@gmail.com
Moscow

References

  1. 1. АНИЧКИН С.А. Склеивание процессов восстановления иего применение // Проблемы устойчивости стохастическихмоделей. Труды семинара. – 1984. – М.: ВНИИСИ. –C. 4–24.
  2. 2. БОРИСОВ И.С. Методы одного вероятностного про-странства для марковских процессов // Тр. Ин-та матема-тики. – 1982. – Т. 1. – С. 4–18.
  3. 3. БОРОВКОВ А.А. Обобщенные процессы восстановления. –М.: Российская академия наук, 2020. – 453 с.
  4. 4. СЕВАСТЬЯНОВ Б.А. Формулы Эрланга в телефонии припроизвольном законе распределения длительности разгово-ра // Труды Третьего Всесоюзного математического съезда,Москва, июнь–июль 1956. – 1959. –Т. 4. – М.: Изд-во АНСССР. – C. 121–135.
  5. 5. СЕВАСТЬЯНОВ Б.А. Эргодическая теорема для марков-ских процессов и ее приложение к телефонным системамс отказами // Теория вероятн. и ее примен. – 1957. – Т. 2,вып. 1. – С. 106–116.
  6. 6. ШЕЛЕПОВА А.Д., САХАНЕНКО А.И. Об асимптотике ве-роятности невыхода неоднородного обобщенного процессавосстановления за невозрастающую границу // Сиб. элек-трон. матем. изв. – 2021. – Т. 18:2. – С. 1667—1688.
  7. 7. AFANASYEVA L.G., TKACHENKO A.V. On theConvergence Rate for Queueing and Reliability ModelsDescribed by Regenerative Processes // Journal ofMathematical Sciences. – October 2016. – Vol. 218, Issue 2. –P. 119–36.
  8. 8. ASMUSSEN S. Applied probability and queues. – Springer,New York, 2003.
  9. 9. CHANG J. T. Inequalities for the Overshoot // The Annals ofApplied Probability. – 1994. – Vol. 4(4). – P. 1223.
  10. 10. DOEBLIN W. Exposé de la théorie des cha ˆ ines simplesconstantes de Markov à un nombre fini d’états // Rev. Math.de l’Union Interbalkanique. – 1938. – Vol.2. – P. 77–105.
  11. 11. ERLANG A. K. Solution of some problems in the theory ofprobabilities 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 bypermission from the Danish Acad. Techn. Sci. athttp://oldwww.com.dtu.dk/teletraffic/Erlang.html.
  12. 12. FERREIRA M.A., ANDRADE M. The M|G|∞ queuebusy period distribution exponentiality // Journal of appliedmathematics. – 2011. – Vol. 4, No. 3. – P. 249–260.
  13. 13. FORTET R. Calcul des probabilités. – CNRS, Paris, 1950.
  14. 14. GRIFFEATH D. A maximal coupling for Markov chains // undZeitschrift für Wahrscheinlichkeitstheorie Verwandte Gebiete. –1975. – Vol. 31, Iss. 2. – P. 95–106.
  15. 15. KALASHNIKOV V.V. Mathematical Methods in QueuingTheory. – Kluwer Academic Publishers, Amsterdam, 1994.
  16. 16. KALIMULINA E., ZVERKINA G. On some generalization ofLorden’s inequality for renewal processes // arXiv.org. Cornell:Cornell university library. – 2019. – 1910.03381v1. – P. 1–5.
  17. 17. KATO K. Coupling Lemma and Its Application to TheSecurity Analysis of Quantum Key Distribution // TamagawaUniversity Quantum ICT Research Institute Bulletin. – 2014. –Vol.4, No.1, – P. 23-30.
  18. 18. LORDEN G. On Excess over the Boundary // The Annals ofMathematical Statistics. – 1970. – Vol. 41(2). – P. 520–527.
  19. 19. PECHINKIN A.V. On an invariant queueing system // Math.Operationsforsch. Statist. Ser. Optim. – 1983. – Vol. 14(3). –P. 433–444.
  20. 20. PECHINKIN A.V., SOLOVYEV A.D., YASHKOV S.F. Asystem with servicing discipline whereby the order of minimumremaining length is serviced first // Eng. Cybern. – 1979. –Vol. 17(5). – P. 38–45.
  21. 21. SMITH W. L. Renewal theory and its ramifications // J. Roy.Statist. Soc. – 1958. – Ser. B, Vol. 20:2. – P. 243–302.
  22. 22. STADJE W. The busy period of the queueing system M|G|∞ //Journal of Applied Probability. – 1985. – Vol. 22. – P. 697–704.
  23. 23. STOYAN D. Qualitative Eigenschaften und Abschtzungenstochastischer Modelle. – Berlin, 1977.
  24. 24. TAK ´ ACS L. Introduction to the Theory of Queues. – OxfordUniversity Press, 1962.
  25. 25. VAN DOORN E.A., ZEIFMAN A.I. On the speed ofconvergence to stationarity of the Erlang loss system //Queueing Systems. – 2009. – Vol. 63. – P. 241–252.
  26. 26. VERETENNIKOV A.YU. On rate of convergence to thestationary distribution in queueing systems with one servingdevice // Automation and Remote Control. – Vol. 74, Iss. 10. –P. 1620–1629. (2013).
  27. 27. VERETENNIKOV A.YU. On the rate of mixing andconvergence to a stationary distribution in Erlang-type systemsin continuous time // Problems Inf. Transmiss. –2010. – Vol.46(4). – P. 382–389.
  28. 28. VERETENNIKOV A.YU. The ergodicity of service systemswith an infinite number of servomechanisms // Математиче-ские заметки. – 1977. – Vol. 22(4). – P. 804–808.
  29. 29. VERETENNIKOV A., BUTKOVSKY O. A. On asymptoticsfor Vaserstein coupling of Markov chains // Stochastic Processesand their Applications. – 2013. – Vol. 123(9). – P. 3518–3541.
  30. 30. VERETENNIKOV A.YU., ZVERKINA G.A. Simple proof ofDynkin’s formula for single-server systems and polynomialconvergence rates // Markov Proc. Rel. Fileds. – 2014. –Vol. 20, Iss. 3. – P. 479–504; arXiv:1306.2359 [math.PR](2013).
  31. 31. ZVERKINA G. On strong bounds of rate of convergence forregenerative processes // Communications in Computer andInformation Science. – 2016. – Vol. 678. – P. 381–393.
  32. 32. ZVERKINA G. Lorden’s inequality and coupling methodfor backward renewal process // Proc. of XX Int. Conf. onDistributed Computer and Communication Networks: Control,Computation, Communications (DCCN-2017, Moscow),2017. – P. 484–491.
  33. 33. ZVERKINA G. On strong bounds of rate of convergence forregenerative processes // Communications in Computer andInformation Science – 2016. – Vol. 678. – P. 381–393.
  34. 34. ZVERKINA G. About some extended Erlang-Sevast’yanovqueueing system and its convergence rate (English and Russianversions) // https:∖∖arxiv.org/abs/1805.04915; Фундаменталь-ная и прикладная математика. – 2018. – No. 22, Iss. 3. –P. 57–82.
  35. 35. ZVERKINA G., KALIMULINA E. On generalized intensityfunction and its application to the backward renewal timeestimation 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») на элемент с текстом «Принять и продолжить».