теория очередей (queueing theory)

[LynxGAV]

Мне недавно стало известно, что есть известные классические модели так называемой теории очередей, созданные более 50 лет назад и описанные в каждом учебнике, которые генерируют интервалы с распределением $p(\triangle t) \propto (\triangle t)^{-\gamma}$, $\gamma$, например, $\in (2,3)$ из стандартного Пуассоновского распределения $p(n,\lambda t)=\frac{{(\lambda t)}^n}{n!}e^{-\lambda t}$.

Что это за модели такие супер известные? Как называются? В каких учебниках описаны?

[AlexDem]

Это вроде как "Теория массового обслуживания" называется? Я, правда, не залезал, не могу ничего сказать по теме. Ваша формула есть в Википедии в разделе "Простейший поток".

[LynxGAV]

AlexDem писал(а):

Это вроде как "Теория массового обслуживания" называется?

Не знаю, как это называется. В англ. языке я краем уха слышала "queue" - очередь, потому перевела дословно. Хотя у меня самой очереди ассоциируются только с походами за хлебом и колбасой при Советском Союзе . Народ должен знать, это ж прикладная математика, как никак.

AlexDem писал(а):

Я, правда, не залезал, не могу ничего сказать по теме. Ваша формула есть в Википедии в разделе "Простейший поток".

Ну, слава богу, что такое Пуассоновское распределение, я знаю, вопрос и заключается в том, как из него получить степенное.

[PAV]

LynxGAV писал(а):

$p(\triangle t) \propto (\triangle t)^{-\gamma}$, $\gamma$, например, $\in (2,3)$

Что-то я недопонимаю. Если $\Delta t\to 0$, то правая часть в бесконечность уходит. Наверное, минус лишний?

[LynxGAV]

PAV писал(а):

Что-то я недопонимаю. Если $\Delta t\to 0$, то правая часть в бесконечность уходит. Наверное, минус лишний?

Минус не лишний. Распределение степенного типа с $\gamma \in (2,3)$, с первым моментом конечным и всеми более высокими расходящимися. Оно несколько идеализированно, потому что на практике время между двумя событиями $\triangle t$ не может быть бесконечно большим и потому заменяется на $p(\triangle t) \propto (\triangle t)^{-\gamma} e^{-\lambda \triangle t}$, чтобы нарушить степенную зависимость для больших $\triangle t$.

Известные классические модели?

Добавлено спустя 14 минут 37 секунд:

В принципе, пусть будет $\gamma$ какое-нибудь $\gamma > 1$, частные случаи потом прояснятся.

[PAV]

Что такое $p(\Delta t)$? Что такое "распределение интервалов"? Проясните терминологию, пожалуйста, по возможности. Мне кажется, что используемые у Вас обозначения противоречат принятым в теории массового обслуживания, а Вы вкладываете в них иной смысл.

Добавлено спустя 2 минуты 24 секунды:

Я тут когда-то объяснял про связь Пуассоновского распределения со стандартным потоком. Это не совсем то, о чем Вы спрашиваете, но может помочь прояснить обозначения.

http://dxdy.ru/topic6114.html

[Архипов]

Теория очередей разработана не в теории вероятности, а в теории автоматов.
Там много полезных алгоритмов. Операционные системы в ЭВМ организуют множество разных очередей в передаче данных.
На транспорте, в массовом обслуживании организуют очереди в плановом порядке (логистика).
Различные конвееры (с параллельным, аварийным резервированием),
Таким образом, в очередях заинтересованы все, кому дорого время. А "пробки","простои", "невязки", "нестыковки", ...- погрешности алгоритмов, реже - продукт случая.

PAV:

[PAV]

Архипов писал(а):

Теория очередей разработана не в теории вероятности, а в теории автоматов.
Там много полезных алгоритмов. Операционные системы в ЭВМ организуют множество разных очередей в передаче данных.
На транспорте, в массовом обслуживании организуют очереди в плановом порядке (логистика).
Различные конвееры (с параллельным, аварийным резервированием),
Таким образом, в очередях заинтересованы все, кому дорого время. А "пробки","простои", "невязки", "нестыковки", ...- погрешности алгоритмов, реже - продукт случая.

Математическая энциклопедия писал(а):

Очередей теория - раздел теории массового обслуживания... С математической точки зрения задачи теории очередей могут быть включены в теорию случайных процессов....

К теории автоматов не имеет никакого отношения.

Не надоело Вам еще выставлять всем напоказ свои незнания? Каким образом Ваше замечание поможет автору темы решить свой вопрос? Оно пустое и не несет никакой информации, а выглядит лишь странной попыткой отметиться в "умном разговоре". Более того, я уже давно замечаю за Вами склонность к такого рода вещам. Это засоряет форум.

Архипов, замечание за оффтопик и систематическую демонстрацию своей математической безграмотности. Ваши неверные заявления способны ввести в заблуждение участников форума, поэтому предупреждаю, что я буду относиться к ним очень внимательно и серьезно. Так что хорошо думайте, прежде чем что-то писать.

[Архипов]

PAV в сообщении #183430 писал(а):

Архипов, замечание за оффтопик и систематическую демонстрацию своей математической безграмотности. Ваши неверные заявления способны ввести в заблуждение участников форума,

Не являюсь должностным лицом на этом форуме. За последствия своих заявлений не отвечаю. Не знал, что "очередь" - чисто математическая категория. Кто заблудился - обращайтесь к администратору форума. Он выведет на верный математический путь.

[PAV]

Архипов
не надо передергивать ситуацию. Речь с самого начала шла не об "очередях", а о "теории очередей". С которой Вы, по-видимому, не знакомы, но услышав известное слово, тут же к нему прицепились и начали развивать тему по своему разумению. Манера обсуждать отдельные слова, выдирая их из контекста, отличает многие Ваши посты на этом форуме и не приветствуется. Обратите внимание на пост участника AlexDem, который специально отметил, что не убежден в правильности своего понимания, чтобы случайно не ввести кого-либо в заблуждение (как принято в цивилизованных обсуждениях), но при этом привел конкретную ссылку на близкую тему. Видно, что его пост написан с целью попробовать помочь автору с его вопросом. А Ваш пост никакой полезной информации относительно вопроса не содержит и вообще слабо к теме относится. А уж заявления типа

Архипов писал(а):

А "пробки","простои", "невязки", "нестыковки", ...- погрешности алгоритмов, реже - продукт случая.

- это уже совсем какая-то ересь.

А потом кто-нибудь станет в другом месте утверждать, что "теория очередей относится к теории автоматов", ссылаясь при этом на "научный форум dxdy". Или просто лишь получит неправильное представление и будет дальше с ним жить. Меня как модератора математического раздела такое положение вещей категорически не устраивает. А поскольку с Вашим участием подобные моменты я замечал и раньше, то хочу, чтобы это прекратилось, и чтобы участникам не приходилось отслеживать Ваши посты и писать к ним опровержения. Надеюсь, что я достаточно ясно выразился, и что больше вопросов не будет.

[Narn]

Может быть, эта ссылка будет полезной (список книг по теории очередей):

http://web2.uwindsor.ca/math/hlynka/qonline.html

[LynxGAV]

Narn писал(а):

Может быть, эта ссылка будет полезной (список книг по теории очередей):

http://web2.uwindsor.ca/math/hlynka/qonline.html

Спасибо, я посмотрела в своей библиотеке по слову "queue*", выдало несколько книг, из которых только одна удобоваримая, все остальное, - сборники каких-то статей.

PAV писал(а):

Что такое $p(\Delta t)$? Что такое "распределение интервалов"? Проясните терминологию, пожалуйста, по возможности. Мне кажется, что используемые у Вас обозначения противоречат принятым в теории массового обслуживания, а Вы вкладываете в них иной смысл.

Да уж, обозначения неахти, но "distribution of intervals" (between events) мне встречалось. Меня теория очередей сама по себе совершенно не интересует, просто подсказали, что если есть какие-то модели, то их надо искать где-то в этой области. Временной промежуток между двумя последовательными событиями $\triangle t$ - часто обозначают просто буквой $t$, $\tau$.

Прочитала Вашу подпись и решила подумать еще... Пока что могу перефразировать вопрос сл. образом.

Известно, что когда события происходят независимо случайным образом, распределение времен между событиями является экспоненциальным и распределение для числа событий до определенного момента времени, или за определенный промежуток времени, является Пуассоновским. Если распределение времен между событиями степенное с отрицательной экспонентой, то каково распределение для числа событий? Интересуют любые модели, связанные с таким степенным распределением, мне нужны аналогии, чтобы его применить в эпидемиологии.

[Посмотрела пару простейших моделей (Erlang и кого-то еще). Первую часть предыдущего абзаца можно переформулировать так: когда прибытие в очередь происходит согласно Пуассоновскому процессу, времена между прибытиями имеют экспоненциальное распределение. И обратно, если времена обслуживания имеют экспоненциальное распределение, то клиенты принимаются к обслуживанию согласно Пуассоновскому процессу.]

[bubu gaga]

Особо не вчитывался в тему, но очень напомнило содержание четвёртой главы книги А. Дрейка

http://ocw.mit.edu/OcwWeb/Electrical-En ... /index.htm

Другим источником может послужить книга Hiller, Liebermann, Introduction to Operations Research, глава 17 в восьмом издании. Там же есть и дальнейшие ссылки.

[LynxGAV]

bubu gaga писал(а):

Особо не вчитывался в тему, но очень напомнило содержание четвёртой главы книги А. Дрейка

http://ocw.mit.edu/OcwWeb/Electrical-En ... /index.htm

Другим источником может послужить книга Hiller, Liebermann, Introduction to Operations Research, глава 17 в восьмом издании. Там же есть и дальнейшие ссылки.

Вторую посмотрю, в первой похоже имелось ввиду "renewal processes" and "random incidence". В первой из этих глав приводится пример.

As an example, suppose that we are burning light bulbs one at a time and replacing each bulb the instant it fails. If the lifetimes of the bulbs are independent random variables with PDF f(xo), we have a renewal process in which the points in time at which bulb replacements occur are the arrivals.

Судя по этому примеру, не подходит он под мой случай. Лампочки выходят из строя приблизительно за одинаковое время. По крайней мере, не могу себе представить, что одна лампочка будет работать день, а другая на 10^4 дней больше, причем почти все они будут перегорать за 1 день. Как-то совсем не правдоподобно. Степенное распределение именно это и подразумевает. Если представить себе события изображенные точками на временной оси, то степенное распределение с $\gamma \in (2,3)$ будет представлено скоплениями точек, находящихся на очень маленьких расстояниях друг от друга и разделенными большими "пустыми" интервалами.
.
"Random incidence" посмотрю, но слово random уже не нравится...

Еще возникла у меня аналогия с траффиком в интернете. Если роутеры работают нормально, то время ожидания для пакетов очень маленькое, если происходят проблемы, то пакеты не отправляются очень долго. Только мне совсем не известно, возникают ли там степенные распределения или нет.

Кроме математического описания, интересует также алгоритм для генерирования событий на определенном промежутке времени, разделенных временными интервалами со степенным распределением.

[Kuzya]

1. Начните с Феллера, т,2, гл VI, параграф 6.
2. Не очень понятны трудности с моделированием случайных величин с заданным распределением