Теорема Беркса - Википедия - Burkes theorem

В теория массового обслуживания, дисциплина в рамках математической теория вероятности, Теорема Берка (иногда Теорема Берка о выходе[1]) это теорема (заявлено и продемонстрировано Пол Дж. Берк во время работы в Bell Telephone Laboratories ) утверждая, что для M / M / 1 очередь, M / M / c очередь или же Очередь M / M / ∞ в установившемся состоянии с приходом Пуассоновский процесс с параметром скорости λ:

  1. Процесс ухода - это пуассоновский процесс с параметром скорости λ.
  2. Вовремя т количество клиентов в очереди не зависит от процесса отправления до временит.

Доказательство

Берк впервые опубликовал эту теорему вместе с доказательством в 1956 году.[2] Теорема была предвосхищена, но не доказана О’Брайеном (1954) и Морсом (1955).[3][4][5] Второе доказательство теоремы следует из более общего результата, опубликованного Райхом.[6] Доказательство, предложенное Бёрком, показывает, что интервалы времени между последовательными отправлениями независимо и экспоненциально распределены с параметром, равным параметру скорости прибытия, из которого следует результат.

Трассировка с выделением моментов отправления / прибытия в процессе прямого / обратного времени.

Альтернативное доказательство возможно при рассмотрении обратный процесс и отмечая, что M / M / 1 очередь - обратимый случайный процесс.[7] Рассмотрим фигуру. К Критерий Колмогорова для обратимости любой процесс рождения-смерти обратимая цепь Маркова. Обратите внимание, что моменты прихода в прямой цепи Маркова являются моментами ухода обращенной цепи Маркова. Таким образом, процесс отъезда - это Пуассоновский процесс скорости λ. Более того, в прямом процессе прибытие во время t не зависит от количества заявок после t. Таким образом, в обратном процессе количество заявок в очереди не зависит от процесса отправления до момента времени.т.

Это доказательство может показаться нелогичным в том смысле, что процесс завершения процесса рождения-смерти не зависит от предлагаемой услуги.

Связанные результаты и расширения

Теорема может быть обобщена «только на несколько случаев», но остается верной для M / M / c очереди и очереди Geom / Geom / 1.[7]

Считается, что теорема Берка не распространяется на очереди, обслуживаемые Марковские процессы прибытия (MAP) и предполагается, что выходной процесс очереди MAP / M / 1 является MAP, только если очередь является очередью M / M / 1.[8]

Аналогичная теорема для Броуновская очередь было доказано Дж. Майкл Харрисон.[3][9]

Рекомендации

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