В теории массового обслуживания , дисциплине в рамках математической теории вероятностей , теорема Берка (иногда выходная теорема Берка [1] ) является теоремой (сформулированной и продемонстрированной Полом Дж. Бёрком во время работы в Bell Telephone Laboratories ), утверждающей, что для M / M / 1 очередь , М / М / с очередью или M / M / ∞ очередь в стационарном состоянии с заездами процесса Пуассона с параметром скорости Х:
- Процесс ухода - это процесс Пуассона с параметром скорости λ.
- В момент t количество заявок в очереди не зависит от процесса отправления до момента t .
Доказательство
Берк впервые опубликовал эту теорему вместе с доказательством в 1956 году. [2] Теорема была предвосхищена, но не доказана О'Брайеном (1954) и Морсом (1955). [3] [4] [5] Второе доказательство теоремы следует из более общего результата, опубликованного Райхом. [6] Доказательство, предложенное Бёрком, показывает, что интервалы времени между последовательными отправлениями независимо и экспоненциально распределены с параметром, равным параметру скорости прибытия, из которого следует результат.
Альтернативное доказательство возможно, если рассмотреть обратный процесс и отметить, что очередь M / M / 1 является обратимым случайным процессом. [7] Рассмотрим рисунок. По критерию обратимости Колмогорова любой процесс рождения-смерти является обратимой цепью Маркова . Обратите внимание, что моменты прихода в прямой цепи Маркова являются моментами выхода обращенной цепи Маркова. Таким образом, процесс ухода - это процесс Пуассона со скоростью λ. Более того, в прямом процессе прибытие в момент t не зависит от количества заявок после t. Таким образом, в обратном процессе количество заявок в очереди не зависит от процесса отправления до момента времени t .
Это доказательство может быть нелогичным в том смысле, что процесс завершения процесса рождения-смерти не зависит от предлагаемой услуги.
Связанные результаты и расширения
Теорема может быть обобщена «только на несколько случаев», но остается верной для очередей M / M / c и очередей Geom / Geom / 1. [7]
Считается, что теорема Берка не распространяется на очереди, питаемые марковскими процессами прибытия (MAP), и предполагается, что выходной процесс очереди MAP / M / 1 является MAP, только если очередь является очередью M / M / 1. . [8]
Аналогичная теорема для броуновской очереди была доказана Дж. Майклом Харрисоном . [3] [9]
Рекомендации
- ^ Walrand, J. (1983). «Вероятностный взгляд на сети квазиобратимых очередей». IEEE Transactions по теории информации . 29 (6): 825–831. DOI : 10.1109 / TIT.1983.1056762 .
- ^ Берк, П.Дж. (1956). «Выход системы массового обслуживания». Исследование операций . 4 (6): 699–704. DOI : 10.1287 / opre.4.6.699 . S2CID 55089958 .
- ^ а б O'Connell, N .; Йор, М. (декабрь 2001 г.). «Броуновские аналоги теоремы Берка». Случайные процессы и их приложения . 96 (2): 285–298. DOI : 10.1016 / S0304-4149 (01) 00119-3 .
- ^ О'Брайен, Г. Г. (сентябрь 1954 г.). «Решение некоторых задач массового обслуживания». Журнал Общества промышленной и прикладной математики . 2 (3): 133–142. DOI : 10.1137 / 0102010 . JSTOR 2098899 .
- ^ Морс, PM (август 1955 г.). «Стохастические свойства очередей». Журнал Американского общества исследования операций . 3 (3): 255–261. DOI : 10.1287 / opre.3.3.255 . JSTOR 166559 .
- ^ Райх, Эдгар (1957). «Время ожидания при тандемных очередях» . Летопись математической статистики . 28 (3): 768–773. DOI : 10.1214 / АОМ / 1177706889 .
- ^ а б Хуэй, JY (1990). «Организация очередей для многоступенчатых пакетных сетей». Теория коммутации и трафика для интегрированных широкополосных сетей . Kluwer International Series в области инженерии и информатики. 91 . С. 313–341. DOI : 10.1007 / 978-1-4615-3264-4_11 . ISBN 978-1-4613-6436-8.
- ^ Бин, Найджел; Грин, Дэвид; Тейлор, Питер (1998). «Процесс вывода очереди MMPP / M / 1». Журнал прикладной теории вероятностей . 35 (4): 998. CiteSeerX 10.1.1.44.8263 . DOI : 10.1239 / JAP / 1032438394 .
- ^ Харрисон, Дж. Майкл (1985). Броуновское движение и системы стохастических потоков (PDF) . Нью-Йорк: Вили. Архивировано из оригинального (PDF) 14 апреля 2012 года . Проверено 1 декабря 2011 .