Определение Пуассоновского потока. Свойства. Процесс пуассона Пуассоновский случайный поток его свойства

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

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

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

Обозначили случайное число событий, наступивших на интервале времени t 1 ,через х 1 и на интервале t 2 , через х 12 . Для потока без последействия случайные величины х 1 и х 2 независимы, т.е. вероятность того, что на участке t 2 наступило определенное число событий m 2 не зависит от того, сколько событий m 1 наступило на участке t 1 .

P (x 2 =m 2 ½x 1 =m 1) = P (x 2 =m ).

(m 1 =0, 1, 2,…)

(m 2 =0, 1, 2,…). (2.47)

Из теории вероятностей известно, что для пуассоновского потока число событий х 1 , попадающих на любой интервал длины t, примыкающих к точке t, распределено по закону Пуассона (рис. 2.5.):

где (а× (t× t)) m – среднее число событий, наступающих на интервале времени t, примыкающем к моменту времени t . Поэтому поток и называется «пуассоновским».

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

Если пуассоновский поток событий является стационарным , то величина а не будет зависеть от t:

В этом случае вероятность того, что на произвольно выбранном участке времени продолжительностью t наступит m событий, определяется по формуле:

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

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

Но эта вероятность равна вероятности того, что случайные величины Т будут больше величины t . Следовательно,

F (t )=P (T <1)=1 - p ×(T >t )=1 - e - l t , t >0. (2.54)

где F (t ) –функция распределения случайной величины Т .

Дифференцируя это выражение, получим плотность распределения случайной величины Т :

f(t )=le - l t , (t >0). (2.55)

Таким образом, в простейшем потоке интервалы между двумя соседними событиями распределен по доказательному закону с параметром l.

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

Математическое ожидание и дисперсия случайной величины Т -интервала времени между двумя событиями в простейшем потоке, равны:

Таким образом,

Регулярный поток событий:

где Т* участок, на который упадает случайное событие.

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

Плотность распределения интервала между любыми событиями, может быть представлена в виде:

f (t )=d(t-m t ), (2.59)

где d(t ) – известная дельта-функция.

Так как интервал между соседними точками строго постоянен и равен m t , то очевидно математическое ожидание этого интервала равно m t , а D t = 0.

Найдем закон распределения времени Q от случайной точки до наступления очередного события:

Характеристическая функция интервала между соседними событиями в регулярном потоке будет иметь вид:

g (x )= e - imt x. (2.61)

Регулярный поток событий сравнительно редко используется при решении прикладных задач. Это объясняется тем, что такой поток событий обладает очень большим (неограниченным) последействием, так как, зная лишь один момент наступления событий в регулярном потоке, можно восстановить всё прошлое этого потока и предсказать будущее.

Интервал времени между двумя соседними событиями простейшего потока имеет распределение:

f 1 (x) = f(x) = (x³0),

где - интенсивность потока.

Используя метод имитации показательного (экспоненциального) распределения, получаем следующий способ моделирования пуассоновского потока:

t 0 =0; t j = t j -1 - (1/ ) lnu , (j=1,2,3,...).

Величина u - случайное число, получаемое от ДСЧ.

Равномерный поток

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

f(x)=1/(b-a) , (a£x£b).

f 1 (x)=2(b-x)/(b-a) 2 ;

F 1 (x)=1-[(b-x) 2 /(b-a) 2 ] , (a£x£b)

Применяя для моделирования метод обратной функции, получим алгоритм вычисления первого момента времени

где u получают от ДСЧ.

Окончательно имеем следующий алгоритм моделирования равномерного потока:

1) момент времени t 1 наступления первого события вычисляется по формуле

2) для последующих моментов времени производимы вычисления по формуле

t j =t j -1 + a + (b-a)u;

Величина u вырабатывается ДСЧ.

Поток Эрланга порядка k

Потоком Эрланга k-го порядка называют поток событий, получающегося "прореживанием" простейшего потока, когда сохраняется каждая k-я точка (событие) в потоке, а все промежуточные выбрасываются.

Интервал времени между двумя соседними событиями в потоке Эрланга k-го порядка представляет собой сумму k независимых случайных величин Z 1 ,Z 2 ,...,Z k , имеющих показательное распределение с параметром λ:

Закон распределения случайной величины Z называется законом Эрланга k-го порядка и имеет плотность

, (x > 0).

Математическое ожидание и дисперсия случайной величины Z соответственно равны:

M[Z]=k/ ; D[Z]=k/ 2 .

На основе определения потока Эрланга получается простой способ моделирования: прореживается пуассоновский поток с интенсивностью = /k, т.е. в пуассоновском потоке допускаем моменты времени с номерами 1,2,...,k-1, а k-й момент оставляем, т.к. он принадлежит новому потоку и т.д. Таким образом, моменты времени потока Эрланга вычисляются по формулам:

где - интенсивность потока Эрланга k-го порядка, u j - случайные числа от ДСЧ.

3. ОБЪЕКТЫ И СРЕДСТВА ИССЛЕДОВАНИЯ

Объектами исследования в лабораторной работе являются потоки событий, образованные слиянием нескольких потоков с известными характеристиками.

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

Одним из простых методов сортировки является метод пузырька (BUBBLE) который позволяет массив A, содержащий N элементов, расположить, например, в возрастающем порядке. Соответствующий алгоритм приведен на рис.4.1. Однако. Более эффективным методом для данного типа задач будет метод вставки.

процедура BUBBLE(A, N);

Цикл I=1,N1;

Если A(K) £ A(J) то идти к 20;

Если (K³1), то идти к 10;

Рис.4.1. Подпрограмма сортировки методом пузырька

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

4. ПОДГОТОВКА К РАБОТЕ

4.1. Ознакомиться с основными типами потоков событий.

4.2. Ознакомиться с методами моделирования пуассоновского, равномерного потока событий и потока Эрланга порядка k.

4.3. Ознакомиться с методами сортировки массивов чисел.

5. ПРОГРАММА РАБОТЫ

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

Первые 100 моментов времени поступления заявок в результирующем потоке вывести на печать. По первым 1000 заявкам рассчитать оценку средней интенсивности потока. Найденную оценку сравнить с теоретическим значением интенсивности потока.

5.1. Поток образован слиянием трёх пуассоновских потоков событий с интенсивностями 1 , 2 , 3 (1/с) (табл.5.1.).

Таблица 5.1.

5.2. Поток образован слиянием двух равномерных потоков с параметрами a 1 , b 1 и a 2 , b 2 (с) (табл. 5.2.).

Таблица 5.2.

5.3. Поток образован слиянием пуассоновского потока с интенсивностью (1 /с) и равномерного потока с параметрами a и b (с) (табл.5 3.).

Таблица 5.3.

6. КОНТРОЛЬНЫЕ ВОПРОСЫ

6.1. Дать определение потока событий.

6.2. Как строится вероятностное описание потока событий.

6.3. В чём состоит способ моделирования стационарного потока с ограниченным последствием.

6.4. Охарактеризовать пуассоновский поток и способ его моделирования.

6.5. Охарактеризовать равномерный поток и способ его моделирования.

6.6. Дать характеристику потока Эрланга k-го порядка и метода его имитации.

6.7. Привести характеристики потока событий, исследованного в лабораторной работе.

Лабораторная работа 6

Информатика, кибернетика и программирование

Определение Пуассоновского потока. Пуассоновский поток это ординарный поток без последействия. Классической моделью трафика в информационных сетях является Пуассоновский простейший поток. Он характеризуется набором вероятностей Pk поступления k сообщений за временной интервал t: где k=01 число сообщений; λ интенсивность потока.

1. Определение Пуассоновского потока. Свойства.

Пуассоновский поток - это ординарный поток без последействия.

Классической моделью трафика в информационных сетях является Пуассоновский (простейший) поток. Он характеризуется набором вероятностей P(k) поступления k сообщений за временной интервал t:

где k=0,1,… - число сообщений; λ - интенсивность потока.

Заметим, что интервал времени измерения количества сообщений t и интенсивность потока λ являются постоянными величинами.

Семейство Пуассоновских распределений P(k) в зависимости от λ изображено на рис.1. Большее значение λ соответствует более широкому и симметричному графику плотности вероятности.

Рис. 1. Пуассоновские распределения. Плотности вероятностей.

Математическое ожидание (среднее) и дисперсия Пуассоновского потока равны λ t .

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

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

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

При моделировании Пуассоновский поток можно получить мультиплексированием совокупности ON/OFF источников, которые называются Марковскими процессами (рис.2.).

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

2. СМО с отказами (классическая система Эрланга)

Здесь мы рассмотрим одну из первых по времени, «классических» задач теории массового обслуживания; эта задача возникла из практических нужд телефонии и была решена в 1909 г. датским инженером-математиком А.К. Эрлангом. Задача ставится так: имеется n каналов (линий связи), на которые поступает поток заявок с интенсивностью λ. Поток обслуживаний каждого канала имеет интенсивность μ. Найти предельные вероятности состояний системы и показатели ее эффективности.

Система S (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): S 0 , S 1 ,…, S n , где S k – состояние системы, когда в ней находится k заявок, т.е. занято k каналов.

Граф состояний СМО соответствует процессу гибели и размножения (рис. 3).

Рис. 3. Граф состояний СМО

Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью λ. Интенсивность же потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии S 2 (два канала заняты), то она может перейти в состояние S 1 (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживаний будет 2μ . Аналогично суммарный поток обслуживаний, переводящий СМО из состояния S 3 (три канала заняты) в S 2 , будет иметь интенсивность 3μ , т.е. может освободиться любой из трех каналов, и т.д.

В формуле (1) для схемы гибели и размножения получим для предельной вероятности состояния:

(1)

где члены разложения - коэффициенты при p 0 в выражениях для предельных вероятностей p 1 , p 2 ,..., p n .

Заметим, что в формулу (1) интенсивности λ и μ входят не по отдельности, а только в виде отношения μ/λ. Обозначим: μ/λ = p , и будем называть величину ρ приведенной интенсивностью потока заявок или интенсивностью нагрузки канала. Она выражает среднее число заявок, приходящих за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулу (1) в виде:

(2)

При этом:

(3)

Формулы (2) и (3) для предельных вероятностей получили названия формул Эрланга в честь основателя теории массового обслуживания.

Вероятность отказа СМО есть предельная вероятность того, что все n каналов системы будут заняты, т.е.

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

Абсолютную пропускную способность получим, умножая интенсивность потока заявок λ на Q:

(4)

Осталось только найти среднее число занятых каналов k. Эту величину можно было бы найти «впрямую», как математическое ожидание дискретной случайной величины с возможными значениями 0,1,..., n и вероятностями этих значений p 0 , p 1 , …, p n :

Подставляя сюда выражения (3) для p k и выполняя соответствующие преобразования, мы, в конце концов, получили бы формулу для k. Однако среднее число занятых каналов можно найти проще, если учесть, что абсолютная пропускная способность A системы есть не что иное, как интенсивность потока обслуженных системой заявок (в единицу времени). Так как каждый занятый канал обслуживает в среднем μ заявок (в единицу времени), то среднее число занятых каналов:

или, учитывая (4):

Этот термин используют, как правило, в теории массового обслуживания.

Математическая энциклопедия. - М.: Советская энциклопедия . И. М. Виноградов . 1977-1985 .

Смотреть что такое "ПУАССОНОВСКИЙ ПОТОК" в других словарях:

Пуассоновский поток - см. Поток требований (заявок) … Экономико-математический словарь

То же, что Пуассоновский процесс. Этот термин используют, как правило, в массового обслуживания теории (См. Массового обслуживания теория) … Большая советская энциклопедия

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

Поток событий последовательность событий, которые наступают в случайные моменты времени. Свойства Свойство стационарности: вероятность появления k событий на любом промежутке времени зависит только от числа k и от длительности t промежутка… … Википедия

В теории случайных процессов описывает количество наступивших случайных событий, происходящих с постоянной интенсивностью. Содержание 1 Определение 1.1 Простой Пуассоновский процесс … Википедия

пуассоновский входящий поток - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN exponential arrivals … Справочник технического переводчика

Случайный процесс X(t).с независимыми приращениями X(t2) X(t1), t2>tl имеющими Пуассона распределение. В однородном П. п. для любых t2 > t1 (1) Коэффициент l>0 наз. интенсивностью пуассоновского процесса X(t). Траектории П. п. X(t).… … Математическая энциклопедия

Случайный процесс, описывающий моменты наступления 0 Большая советская энциклопедия

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

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

ординарность (в каждый момент времени в СМО может пос­тупать не более одной заявки). Ординарность потока означает, что вероятность попадания на элементарный участок Dt двух или более событий пренебрежимо мала по сравнению с вероятностью попадания на него ровно одного события, т.е. при Dt->0 эта вероятность представляет собой бесконечно малую высшего порядка.

В каждый момент времени в СМО может пос­тупать не более одной заявки

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

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

отсутствие последействия - для любых не перекрывающихся участков времени T 1 ,T 2 ,…,T n числа событий Х 1 =Х(t 1 ,T 1),Х 2 =Х(t 2 ,T 2),…., Х n = Х(t n ,T n), попадающих на эти участки, представляют собой независимые случайные величины, т.е. вероятность попадания любого числа событий на один из участков не зависит от того, сколько их попало на другие.

Отсутствие последействия означает, что для любого момента времени t0, будущие моменты наступления события потока (при t>t0) не зависят от того, в какие моменты наступали события в прошлом (при t

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

Стационарность

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

зависит только от длины этого участка и не зависит от того, где именно на оси времени 0t этот участок расположен.

Это значит, что числа событий Х 1 (t 1 , T) и Х 2 (t 2 , T), попадающих на два участка одинаковой длины T, будут иметь одинаковые распределения. Отсюда следует, в частности, что для стационарного потока событий его интенсивность l(t) постоянна:

l(t) = l = const

Поток событий, обладающий всеми тремя свойствами, называется простейшим (или стационарным пуассоновским потоком).

Кроме того, к достоинствам простейшего потока можно так­же отнести следующее:

а) Сумма N независимых, ординарных и стационарных пото­ков заявок с интенсивностями сходится к простейшему потоку с интенсивностью , при условии, что складываемые потоки оказывают более или ме­нее одинаково малое влияние на суммарный поток;

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

Поток с ограниченным последействием (рекуррентный поток) – поток, у которого случайные интервалы t1, t2,…, tn между соседними по времени событиями представляют собой независимые случайные величины. При его моделировании применяется последовательная (рекуррентная процедура): сначала разыгрывается величина t1, затем t2 и т.д. Например, последовательность вызовов такси.