Теорема Берка

В теории массового обслуживания — дисциплине математической теории вероятностей — теорема Бёрка (иногда теорема Бёрка о выходе). ^{[ 1 ]}) — это теорема (сформулированная и продемонстрированная Полом Дж. Берком во время работы в Bell Telephone Laboratories ), утверждающая, что для очереди M/M/1 , очереди M/M/c или очереди 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 ]}

Ссылки

^ Уолранд, Дж. (1983). «Вероятностный взгляд на сети квазиобратимых очередей». Транзакции IEEE по теории информации . 29 (6): 825–831. дои : 10.1109/TIT.1983.1056762 . S2CID 216943 .
^ Берк, П.Дж. (1956). «Результаты системы массового обслуживания». Исследование операций . 4 (6): 699–704. дои : 10.1287/опре.4.6.699 . S2CID 55089958 .
^ Перейти обратно: ^а ^б О'Коннелл, Н.; Йор, М. (декабрь 2001 г.). «Броуновские аналоги теоремы Берка» . Случайные процессы и их приложения . 96 (2): 285–298. дои : 10.1016/S0304-4149(01)00119-3 .
^ О'Брайен, Г.Г. (сентябрь 1954 г.). «Решение некоторых проблем массового обслуживания». Журнал Общества промышленной и прикладной математики . 2 (3): 133–142. дои : 10.1137/0102010 . JSTOR 2098899 .
^ Морс, премьер-министр (август 1955 г.). «Стохастические свойства очередей ожидания». Журнал Американского общества исследования операций . 3 (3): 255–261. дои : 10.1287/опре.3.3.255 . JSTOR 166559 .
^ Райх, Эдгар (1957). «Время ожидания в тандемных очередях» . Анналы математической статистики . 28 (3): 768–773. дои : 10.1214/aoms/1177706889 .
^ Перейти обратно: ^а ^б Хуэй, JY (1990). «Очередь в многоступенчатых пакетных сетях». Теория коммутации и трафика для интегрированных широкополосных сетей . Международная серия Kluwer по инженерным наукам и информатике. Том. 91. стр. 313–341. дои : 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 . дои : 10.1239/яп/1032438394 . S2CID 122137199 .
^ Харрисон, Дж. Майкл (1985). Броуновское движение и стохастические системы потоков (PDF) . Нью-Йорк: Уайли. Архивировано из оригинала (PDF) 14 апреля 2012 г. Проверено 1 декабря 2011 г.

[1] Уолранд, Дж. (1983). «Вероятностный взгляд на сети квазиобратимых очередей». Транзакции IEEE по теории информации . 29 (6): 825–831. дои : 10.1109/TIT.1983.1056762 . S2CID 216943 .

[2] Берк, П.Дж. (1956). «Результаты системы массового обслуживания». Исследование операций . 4 (6): 699–704. дои : 10.1287/опре.4.6.699 . S2CID 55089958 .

[connell-3] Перейти обратно: ^а ^б О'Коннелл, Н.; Йор, М. (декабрь 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/опре.3.3.255 . JSTOR 166559 .

[6] Райх, Эдгар (1957). «Время ожидания в тандемных очередях» . Анналы математической статистики . 28 (3): 768–773. дои : 10.1214/aoms/1177706889 .

[hui-7] Перейти обратно: ^а ^б Хуэй, JY (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/яп/1032438394 . S2CID 122137199 .

[9] Харрисон, Дж. Майкл (1985). Броуновское движение и стохастические системы потоков (PDF) . Нью-Йорк: Уайли. Архивировано из оригинала (PDF) 14 апреля 2012 г. Проверено 1 декабря 2011 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

v т и Теория массового обслуживания
Одиночные узлы массового обслуживания	Очередь Д/М/1 Очередь М/Д/1 Очередь М/Д/Ц Очередь М/М/1 Теорема Берка Очередь М/М/Ц Очередь М/М/∞ Очередь M/G/1 Формула Поллачека – Хинчина Матричный аналитический метод Очередь M/G/k Очередь G/M/1 Очередь G/G/1 Формула Кингмана Уравнение Линдли Разветвить очередь – присоединиться к ней Массовая очередь
Процессы прибытия	Точный процесс Пуассона Марковский процесс прибытия Рациональный процесс прибытия
Сети массового обслуживания	Сеть Джексона Уравнения дорожного движения Теорема Гордона – Ньюэлла Анализ среднего значения Алгоритм Бузена сеть Келли G-сеть Сеть BCMP
Политика обслуживания	ФИФО ЛИФО Совместное использование процессора Круговой Самая короткая работа следующая Кратчайшее оставшееся время
Ключевые понятия	Цепь Маркова с непрерывным временем Обозначения Кендалла Закон Литтла Решение в форме продукта Уравнение баланса Квазиобратимость Потоко-эквивалентный серверный метод Теорема о прибытии Метод разложения метод Бенеша
Предельные теоремы	Предел жидкости Теория среднего поля Приближение интенсивного движения Отраженное броуновское движение
Расширения	Жидкая очередь Многоуровневая сеть массового обслуживания Система опроса Состязательная сеть массового обслуживания Сеть потерь Очередь повторных попыток
Информационные системы	Буфер данных Эрланг (единица измерения) Распределение Эрланга Управление потоком (данные) Очередь сообщений Перегрузка сети Сетевой планировщик Конвейер (программное обеспечение) Качество обслуживания Планирование (вычисления) Телетрафик инжиниринг
Категория