Главная » Дизайн спальни » Процесс пуассона. Моделирование пуассоновского процесса

Процесс пуассона. Моделирование пуассоновского процесса

Аннотация: Пуассоновский процесс - самый важный точечный процесс. Позже мы поймем, что его роль среди точечных процессов столь же фундаментальна, как роль нормального распределения среди статистических распределений. Результатом сложения случайных переменных с помощью Центральной предельной теоремы является нормальное распределение. Подобным способом мы получаем экспоненциальное распределение при совмещении стохастических точечных процессов. Большинство других прикладных точечных процессов являются обобщением или модификацией Пуассоновского процесса. Этот процесс дает удивительно хорошее описание многих реальных процессов жизни. Чем сложнее процесс, тем лучше Пуассоновский процесс будет служить для него общей моделью. Пуассоновский процесс имеет широкое практическое применение, поэтому мы изучим его подробно в этой лекции. Сначала (секция 6.2) поговорим о физической модели. При этом главное внимание будет уделено распределениям, связанным с процессом, а затем мы рассмотрим некоторые важные свойства Пуассоновского процесса (секция 6.3). Наконец, в секции 6.4 рассмотрим прерванный Пуассоновский процесс, как пример обобщения.

Характеристики Пуассоновского процесса

Фундаментальные свойства Пуассоновского процесса определены в секции 5.2:

а. стационарность;

б. независимость (отсутствие последействия) во все моменты времени (периоды), и

в. простота (ординарность).

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

В этом случае, используя (4.8) и (4.10) равенство Феллера- Дженсена (5.4), можно показать фундаментальное отношение между кумулятивным (накопленным) Пуассоновским распределением и распределением Эрланга:

(6.1)

Эта формула может также быть получена повторным интегрированием по частям.

Распределения Пуассоновского процесса

В этой секции мы поговорим о динамическом и физическом представлении Пуассоновского процесса (1928 и Дженсен, 1954 ). Дифференцирования основаны на простой физической модели и концентрируются на распределениях вероятности, связанных с Пуассоновским процессом.

Физическая модель получается следующим способом. События (поступление) помещены наугад на реальной оси времени независимо от всех других событий, т.е. мы помещаем события однородно и независимо на реальных осях времени.

Средняя плотность выбрана как события (поступление) в единицу времени. Если рассматривать ось как ось времени, то в среднем мы будем иметь поступлений в единицу времени.

Вероятность , что данное поступление заявки возникает в пределах временного интервала, не зависит от местоположения интервала на оси времени.

Рис. 6.1.

В Пуассоновском процессе мы рассматриваем поступление заявки в пределах двух не перекрывающихся временных интервалов продолжительностью и соответственно.

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

Математическая формулировка вышеупомянутой модели следующая.

Экспоненциальное распределение

Следующий существенный шаг в развитии Пуассоновского распределения - получение вероятности , которая является вероятностью непоступления заявки в пределах временного интервала длины , то есть вероятности, что первое поступление заявки произойдет позже, чем . Мы покажем, что - экспоненциальное распределение (сравните с результатом секции 4.1).

Из (6.2) мы имеем:

(6.6)

Обозначая , (6.6) может быть записано как:

(6.7)

Дифференцируя, например, по , мы имеем

Заметим, что должна быть константой, и поэтому

(6.8)

Подставляя (6.8) в (6.7), мы получаем . Тогда имеет форму

Из (6.3) мы получаем :

Таким образом, на основе пункта (1) и (2) выше мы показали, что:

Вероятность, что следующее появление заявки в пределах интервала может быть записана, как:

(6.13)

то есть вероятность, что заявка поступит в пределах интервала , равна , независимо om пропорционально (3.17).

Поскольку независима от величины (возраста ) , экспоненциальное распределение не имеет памяти (сравните секции 4.1 и 3.1.2). Процесс не имеет возраста .

Параметр называется интенсивностью или скоростью экспоненциального распределения и соответствующего Пуассоновского процесса, и это соответствует интенсивности в (5.6). Экспоненциальное распределение - вообще очень хорошая модель для интервалов поступления вызовов, когда нагрузка генерируется автоматически, а не вручную (рис.6.2).

Рис. 6.2.

Теоретические значения получены при условии экспоненциально распределенных времен интервалов. Согласно принципу измерения (метод сканирования) непрерывное экспоненциальное распределение преобразовано в дискретное распределение Вестберга (Westerberg) (15.14) (критерий - = 18,86 с 19 степенями свободы, квантиль = 53)

Распределение Эрланга k-ого порядка

Из приведенного выше можно заметить, что время поступления точно событий определяется суммой IID (independently and identically distributed - независимо и тождественно распределенных) экспоненциально распределенных случайных переменных.

Распределение этой суммы - распределение Эрланга k - ого порядка (секция 4.2), и плотность равна:

(6.14)

Для мы получаем экспоненциальное распределение. Распределение , получено свертыванием и . Если мы принимаем, что выражение (6.14) правильно для , тогда получаем свертыванием :

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

Распределение Эрланга -ого порядка со статистической точки зрения - это специальное гамма-распределение .

Средняя величина и дисперсия получаются из (6.12):

(6.15)

Пример 6.2.1: статистика вызова в системе с программным управлением (сравните с Примером 5.1.2)

Пусть вызовы поступают в систему с программным управлением, например, на программно управляемую телефонную станцию (

Перевод

Введение

Одним из важнейших процессов, наблюдаемых в природе, является пуассоновский точечный процесс. Поэтому важно понять, как такие процессы можно моделировать. Методы моделирования различаются в зависимости от типа пуассоновского точечного процесса, т. е. пространства, в котором протекает процесс и однородности или неоднородности процесса. Мы не будем заинтересованы развитием пуассоновского точечного потока или с важными приложениями его в различных областях. Чтобы этот материал показался интересным, читателю настоятельно рекомендуется прочитать соответствующие разделы в Феллере (1965) и Синларе (1975) для основной теории и некоторые разделы в Триведи (1982) для приложений в ИТ.

На первом шаге мы определим пуассоновский процесс на = T
UNTIL Ложь (это бесконечный цикл; по желанию можно добавить критерий остановки)

Этот алгоритм просто реализовать, поскольку нет нужды генерировать пуассоновские случайные величины. Для других простых множеств A, существуют тривиальные обобщения теоремы 1.2. Например, когда A=x, где t может равняться бесконечности, 0 < T1 < T2 <… - равномерный пуассоновский процесс с интенсивностью λ и U1,U2,… - последовательность независимых одинаково распределённых равномерно на случайных величин, то (T1,U1),(T2,U2),… определяют пуассоновский процесс с интенсивностью λ на А.

Пример 1.1.

Равномерный пуассоновский процесс на единичной окружности
Если A - окружность с единичным радиусом, то разные свойства равномерного пуассоновского процесса можно использовать, чтобы получить несколько методов генерации (которые обобщаются на d-мерные сферы). Пусть λ - желаемая интенсивность.
Во-первых, мы просто могли бы сгенерировать случайную пуассоновскую величину N с параметром λπ, а затем вернуть последовательность N независимых одинаково распределённых равномерно на единично окружности векторов. Если мы применим метод порядковых статистик, предлагаемый теоремой 1.2, то пуассоновская случайная величина получается неявно. Например, перейдя в полярные координаты (R,φ) заметим, что для равномерного пуассоновского процесса R и φ независимы, и случайная величина R имеет плотность 2r, r меняется от 0 до 1, а φ равномерно распределена на . Таким образом, мы можем поступить следующим образом: Сгенерировать равномерный пуассоновский процесс 0 < φ1 < φ2 <… < φN с параметром интенсивности λ/(2π) на экспоненциальным методом и вернуть (φ1,R1),...,(φN,RN), где Ri - независимые одинаково распределённые случайные величины с плотностью 2r на , которые можно сгенерировать, взяв максимум из двух независимых равномерно распределённых на случайных величин. Особой причины применять эспоненциальный метод к углам нет. Таким же образом мы могли подобрать и радиусы. К сожалению, порядковые радиусы не формируют одномерный равномерный пуассоновский процесс на . Однако, тем не менее они образуют неоднородный пуассоновский процесс, и генерация таких процессов будет рассмотрена в следующем разделе.

Неоднородные пуассоновские процессы

Бывают такие ситуации, когда события происходят в «случайные моменты времени», но некоторые моменты более возможны, чем другие. Это случай прибытий в центры интенсивной терапии, предложений работ в компьютерных центрах и травмы игроков НХЛ. Для этих случаев очень хорошей моделью является модель неоднородного пуассоновского процесса, определённого здесь ради удобства на = T
UNTIL False

Пример 1.2. Однородный пуассоновский процесс

Для особого случая λ(t)=λ, Λ(t)=λt несложно видеть, что InvΛ(E+Λ(T))=T+E/λ, в результате чего мы снова получаем экспоненциальный метод.

Пример 1.3.

Для моделирования утреннего потока автомобилей перед часом пик, мы иногда можем взять λ(t)=t, тогда Λ(t)=t^2/2 и получим шаг

Если функцию интенсивности можно представить в виде суммы функций интенсивности, т. е. ,

0 < T i1 < T i2 <… T in - независимые реализации отдельных неоднородных пуассоновских процессов, то объединённая упорядоченная последовательность образует реализацию неоднородного пуассоновского процесса с функкцией интенсивности λ(t). Это относится к методу композиции, но разница теперь состоит в том, что нам нужны реализации всех компонентов процесса. Декомпозицию можно использовать, когда существует естественное разложение, продиктованное аналитической формой λ(t). Поскольку основная операция в слиянии процессов - взять минимальное значение из n процессов, для больших n преимущество может предоставить хранение моментов времени в куче из n элементов.

В итоге получим метод композиции:

Сгенерировать T,...,T для n пуассоновских процессов и хранить эти значения вместе с индексами соответствующих процессов в таблице
T = 0 (текущее время)
k = 0
REPEAT
Найти минимальный элемент T в таблице и удалить его
k = k + 1
T[k] = T
Сгенерировать T и вставить в таблицу
UNTIL False

Третий общий принцип - это принцип утоньшения (Льюис и Шедлер, 1979). Аналогично тому, что происходит в методе отклонения, предполагаем, что существует лёгкая доминирующая функция интенсивности λ(t) <= μ(t) для любого t.

Тогда идея состоит в том, чтобы сгенерировать однородный Пуассоновский процесс на части положительной полуплоскости между 0 и μ(t), затем рассмотреть однородный пуассоновский процесс под λ и, наконец, вернуть x-компоненты событий в этом процессе. Это требует следующей теоремы.

Теперь рассмотрим метод утоньшения Льюиса и Шедлера:

T = 0
k = 0
REPEAT
Сгенерировать Z, первое событие в неоднородном пуассоновском процессе с функцией интенсивности μ, который происходит после момента времени T. Присвоить T = Z
Сгенерировать равномерно распределённую на случайную величину U
IF U <= λ(Z)/μ(Z)
THEN k = k + 1, X[k] = T
UNTIL False

Утверждается, что последовательность X k так сгенерированная образует неоднородный пуассоновский процесс с функцией интенсивности λ. Заметим, что мы взяли неоднородный процесс 0 < Y1 < Y2 <… с функцией интенсивности μ и убрали некоторые точки. Насколько мы знаем, (Y i ,U i μ(Y i) - однородный пуассоновский процесс с единичной интенсивностью на кривой, если U i независимые одинаково распределённые равномерно на случайные величины в силу теоремы 1.3. Таким образом, подпоследовательность на кривой λ определяет однородный пуассоновский процесс с единичной интенсивностью на этой кривой (часть 3. теоремы 1.3). Наконец, взятие x-координат только этой подпоследовательности даёт нам неоднородный пуассоновский процесс с функцией интенсивности λ.
Неоднородный пуассоноский процесс с функцией интенсивности μ обычно моделируют методом инверсии.

Пример 1.4. Функция с циклической интенсивностью

Следующий пример также принадлежит Льюису и Шедлеру (1979). Рассмотрим функцию с циклической интенсивностью λ(t)= λ(1+cos(t)) с очевидным выбором доминирующей функции μ=2λ.

Тогда алгоритм моделирования примет вид:

T = 0
k = 0
REPEAT
Сгенерировать экспоненциальную случайную величину E c параметром 1
T = T + E/(2λ)
Сгенерировать равномерную на случайную величину U
IF U <= (1+cos(T))/2
THEN k = k + 1, X[k] = T
UNTIL False

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

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

Пуассоновский процесс

Рассмотрим бесконечно малый промежуток времени Dt (Dt® 0), проходящий между моментами t и t+Dt . При определении пуассоновского процесса используются три основные предпосылки:

1. вероятность одного поступления в течение времени Dt определяется в виде: lDt+О(Dt) , где О(Dt ) – члены более высокого порядка, которыми мы можем пренебречь при Dt ®0;

2. вероятность нулевого поступления в течение времени Dt равна 1-lDt ;

3. поступление – без последействия (без памяти), т.е. поступление в течение Dt не зависит от предыдущих поступлений.

Если теперь рассмотреть большой промежуток времени Т , то вероятность p(k) того, что в промежутке Т произойдут k поступлений, равна:

Где k = 0, 1, 2, …

Это равенство называется распределением Пуассона. Оно нормировано:

и его среднее значение имеет вид:

Дисперсия распределения:

Теперь рассмотрим большой промежуток времени и отметим на нём моменты, в которые наступили события Пуассоновского процесса.

Очевидно, что t - это положительная случайная величина с непрерывным распределением. Оказывается, что для Пуассоновского распределения величина t распределена по показательному закону:

Среднее значение показательного распределения:

а дисперсия .

Рассмотрим очередь из нескольких вызовов, ожидающих обслуживания. Отметим время завершения обслуживания:

Обозначим случайную величину, описывающую время между завершениями обслуживания через r . Эта же величина является временем обслуживания. Если r распределена по показательному закону со средним значением

E(r)=1/m ,

то плотность распределения будет равна:

Процесс обслуживания является полным аналогом процесса поступления и обладает всеми свойствами последнего. На основании этого вероятность завершения обслуживания в малом промежутке времени (t, t+Dt) в точности равна mDt + О(Dt) , а вероятность незавершения обслуживания в промежутке (t, t+Dt) равна 1-mDt+О(Dt) независимо от предыдущих или последующих завершений.

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

Ещё одно полезное свойство, объединяющее одну из причин, по которой Пуассоновский процесс часто используется для моделирования входящих потоков, заключается в том, что при объединении m независимых Пуассоновских потоков с произвольными интенсивностями l 1 , l 2 , … l m , объединённый поток также будет Пуассоновским с интенсивностью .

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

Система обслуживания М/М/1

Система обслуживания М/М/1 – это система с одной обслуживающей линией, Пуассоновским входящим потоком, показательным распределением обслуживания и дисциплиной ОПП (обслуживание в порядке поступления).

Диаграмма изменений состояний во времени для системы может быть изображена следующим образом:

Пусть процессы поступления и обслуживания определяются соответственно параметрами l и m . Определим вероятность p n (t+Dt) того, что в момент времени t+Dt в системе будет находиться n клиентов (пакетов или вызовов). Из диаграммы видно, что в момент времени t система могла находиться только в состоянии n-1, n или n+1 . Тогда мы можем записать:

Вероятности перехода из одного состояния в другое получены в результате рассмотрения путей, по которым происходят эти переходы, и расчёта соответствующих вероятностей. Например, если система осталась в состоянии n, то могли произойти либо уход и одно поступление с вероятностью mDt , либо ни одного ухода или поступления с вероятностью , что и показано в первом случае.

Производя упрощения, иcпользуя разложение в ряд Тейлора, можно получить следующее уравнение:

Для стационарного состояния вероятность p n (t) приближается к некоторому постоянному значению, поэтому = 0. Тогда последнее уравнение для стационарного случайного процесса упрощается и принимает вид:

Форма уравнения (1) показывает, что при работе системы действует стационарный принцип равновесия: левая часть описывает интенсивность уходов из состояния n, а правая часть – интенсивность приходов в состояние n из n-1 или n+1 . Чтобы существовали вероятности стационарного состояния, эти две интенсивности должны быть равны.

Рассмотрим диаграмму состояний для системы М/М/1

Ввиду предположений о Пуассоновском процессе поступления и уходов клиентов переходы имеют место только между соседними состояниями с показанными интенсивностями.

Уравнение (1) может быть решено несколькими способами. При простейшем их них может быть использовано условие равновесия. Если рассчитать общий «поток вероятности», пересекающий границу области 1, и приравнять исходящий поток к входящему, получиться уравнение (1). Область 2 охватывает всё множество точек от 0 до n . Поток, поступающий в эту область, равен mp n +1 , а поток, покидающий её, равен lp n . Приравнивая эти два потока, получим: mp n +1 =lp n . Повторяя последнее уравнение n раз, получим:

mp n =lp n-1 ; mp 2 =lp 1 ;

mp 3 =lp 2 ; mp 1 =lp 0 ;

Следовательно,

Значение р 0 для случая бесконечной очереди можно найти, используя нормирующее условие: . Просуммировав n вышеприведенных уравнений и учитывая нормировку, получим:

Используя это, можно записать решение для установившегося режима:

Распределение вероятностей (2) системы М/М/1 называется геометрическим распределением.

Обобщим результаты для случая конечной очереди, вмещающей не более N пакетов. Можно показать, то в этом случае.

Перевод

Введение

Пример 1.1.

Неоднородные пуассоновские процессы

Пример 1.2. Однородный пуассоновский процесс

Пример 1.3.

Если функцию интенсивности можно представить в виде суммы функций интенсивности, т. е. ,

В итоге получим метод композиции:

Теперь рассмотрим метод утоньшения Льюиса и Шедлера:

Пример 1.4. Функция с циклической интенсивностью

Тогда алгоритм моделирования примет вид:

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

Слияние. Пусть N (t ) и N 2 (t) - два независимых пуассоновских процесса с интенсивностями А^и Х 2 . Тогда сумма процессов N(t) = N j (0+ N 2 (t) снова будет процессом Пуассона с интенсивностью A.J +Х 2 (рис. 14.9).

Рассмотрим короткий интервал (/, H-dx). Вероятность, что ни одно событие не произойдет в суммарном процессе, вычисляется в силу независимости как

Рис. 14.9. Слияние двух процессов Пуассона

В то же время вероятность того, что произойдет одно событие в суммарном процессе:

Производящая функция суммы случайных процессов, согласно (10.10) и (14.23), будет иметь вид

Приведенные формулы доказывают наше утверждение.

В общем случае для суммы т независимых процессов с интенсивностями Xj - результирующий процесс будет пуассоновским с интенсивностью

Предположим, что две случайные переменные Г, и Т 2 , представляющие интервалы времени между событиями двух пуассоновских процессов, взаимно независимы и экспоненциально распределены с интенсивностями Х ] и X 2 соответственно. Определим новую переменную

Функция распределения Т, согласно (14.25) и (14.27),

Вероятность того, что в интервале сначала произойдет событие Т { , а затем Т 2:

Как видно, вероятность не зависит от t.

В общем случае, если Г р Г 2 ,..., Т п независимые экспоненциально распределенные случайные величины с параметрами Х х, Х 2 ,...,Х п соответственно, то Т =min{7’ 1 ,Т 2 ,...,Т п } будет распределена экспоненциально с параметром Х { +Х 2 - ------Х п и вероятностью, что Tj имеет наименьшее значение :

Очевидно, что сумма вероятностей равна 1.

Случайное выделение. Если из пуассоновского процесса с интенсивностью X случайным образом с вероятностью р выбирать событие независимо от выбора других событий (рис. 14.10), то результирующий процесс будет пуассоновским с интенсивностью рХ.

Рис. 14.10.

Рассмотрим короткий интервал (/, t+ dx). Вероятность того, что в процессе, полученном с помощью случайной выборки, не произойдет событие, равна

В то же время вероятность, что в выборочном процессе произойдет одно событие, равна

что соответствует пуассоновскому процессу с интенсивностью рХ.

Расщепление. Пусть N(t) -процесс Пуассона с интенсивностью X, a N { (0 и N 2 (it ) обозначают число отмеченных с вероятностью р и не отмеченных с вероятностью (1 -р) заказов, прибывших в интервале (рис. 14.11). Тогда N x (t ) и N 2 (t) - процессы Пуассона с интенсивностями рХи (1- р) А,и оба процесса независимы. Доказательство аналогично предыдущему.

Рис. 14.11.

Равновероятность события в интервале. Пусть п событий произошли в моменты 0 t Т]. Тогда случайные переменные t { , t 2 ,...,t n имеют равномерное распределение в этом интервале.

Сначала предположим, что только одно событие происходит внутри интервала , а время этого события представляется случайной переменной Х х. Тогда имеют место два эквивалентных утверждения, представляющие вероятности совместных событий:

Согласно закону условной вероятности, первое утверждение можно записать как

Комбинируя выражения и подставляя пуассоновское распределение, получаем:

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

Свойство PASTA (Poisson Arrival See Time Average) называют также ROP (Random Observer Property). Рассмотрим произвольную систему сервиса S, находящуюся в различных состояниях Sj. Клиенты прибывают в систему с интенсивностью А,. Клиент побуждает переход системы в другое состояние. В установившемся режиме мы можем рассматривать две различные вероятности: Pj - вероятность состояния Sj системы со стороны внешнего наблюдателя (клиента); р* - вероятность состояния системы при прибытии клиента. В общем случае Pj *= р*.

Свойство PASTA утверждает, что для пуассоновского процесса pj = р* , поскольку стохастические характеристики поступающего потока в момент начала рассмотрения одинаковы и независимы от выбора момента рассмотрения. Следовательно, распределение вероятностей состояний системы в момент рассмотрения должно быть таким же, как до этого момента. Другими словами, прибывший клиент не изменяет статистические характеристики системы, хотя изменяет ее состояние, и всегда наблюдает систему в ее стационарном состоянии. Интуитивно это свойство означает, что пуассоновский процесс полностью случаен. Свойство PASTA не справедливо для непуассоновских потоков.

Напечатать