Основы теории массового обслуживания

В.Г. Карташевский Основы теории массового обслуживания Рекомендовано УМО по образованию в области телекоммуникаций в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки дипломированных специалистов 210400 (654400) - Телекоммуникации Радио и связь Москва 2006 УДК 621.391 К27 Карташевский В.Г. Основы теории массового обслуживания : Учебное пособие для вузов.- М.: Радио и связь, 2006.- 86с.: 34ил. ISBN 5-256-1808-6 Освещаются основы теории массового обслуживания, знание которых необходимо для современного представления о процессах распределения информации в телекоммуникационных и вычислительных сетях. Рассматриваются потоки заявок на обслуживание, при условии, что структура потока носит случайный характер. Особое внимание уделено пуассоновскому потоку событий. Проанализирована работа устройств массового обслуживания (в обозначении Кендалла) типа М/М/1, M/G/1, G/M/1 и их модификаций. Рассмотрены системы с относительным приоритетом обслуживания. Для студентов вузов, обучающихся по специальностям направления «Телекоммуникации», может быть полезна специалистам в области связи. ИБ № 3142 ISBN 5-256-1808-6 Издательская лицензия № 010164 от 29.01.97г. 2 Оглавление Оглавление . . . . . . . Введение . . . . . . . . 1. Потоки событий . . . . . . 1.1. Основные определения . . . . 1.2. Закон распределения времени, на который падает точка . . . . . . 1.3. Закон распределения времени до наступления очередного события . . . . . 1.4. Пуассоновский поток событий . . . Анализ интервалов времени в пуассоновском потоке . . . . . . . 1.5. Вывод формулы Пуассона через производящую функцию. . . . . . . 1.6. Другие стационарные потоки Пальма . . Регулярный поток . . . . . Нормальный поток . . . . . Поток Эрланга . . . . . Предельная теорема для суммарного потока . Предельная теорема для редеющего потока . 2. Анализ систем массового обслуживания . . 2.1. Классификация систем . . . . 2.2. Система обслуживания М/М/1 . . . Вероятность блокировки . . . . 2.3. Формула Литтла . . . . . 2.4. Системы обслуживания, зависящие от состояний Система M/M/2 . . . . . Система М/М/ . . . . . Система с нетерпеливыми клиентами . . Система M/M/N/0 . . . . . 2.5. Система обслуживания M/G/1 . . . Система M/D/1 . . . . . 2.6. Упрощенный вывод формулы для Е(n) системы M/G/1 . . . . . . . 2.7. Система G/M/1 . . . . . 2.8. Системы обслуживания с относительными приоритетами . . . . . . Литература . . . . . . 3 3 4 7 7 9 14 18 21 24 27 27 29 30 32 33 37 37 39 44 48 52 54 57 58 60 62 66 71 74 79 86 Введение. Ежедневно мы сталкиваемся с ситуациями, в которых появляется потребность в массовом обслуживании. Самым простым примером такой ситуации является очередь в магазине или на остановке автобуса, которая появляется из-за того, что у тех, кто занимается обслуживанием, нет возможности обслужить всех сразу. Не случайно, в публикациях на английском языке теорию массового обслуживания называют теорией очередей. Можно привести множество примеров, когда проявляются проблемы массового обслуживания - невозможность дозвониться по нужному номеру, скопление самолётов над аэродромом из-за отсутствия посадочных полос, обслуживание группы станков одним рабочим, ремонт судов при ограниченном числе доков, перевозка грузов автотранспортной конторой и т.д. Примеры разные, но им присущи формальные признаки, которые позволяют описать их с помощью одного и того же математического аппарата. Главная задача, стоящая перед теорией – установить с необходимой точностью количественную связь между числом приборов обслуживания, характеристиками входящего потока требований (заявок) на обслуживание и качеством обслуживания. Под качеством обслуживания в теории массового обслуживания обычно понимается своевременность обслуживания поступивших в систему требований. Естественно, качество обслуживания надо уметь оценивать количественно. Общая особенность всех задач теории массового обслуживания – случайный характер исследуемых явлений. Действительно, количество требований на обслуживание (например, число звонков, поступающих на телефонную станцию за фиксированный промежуток времени) – случайная величина. Временной интервал между поступлением требований – случайная величина. И, наконец, время обслуживания каждой заявки – также случайная величина. Поэтому решение всех задач массового обслуживания основывается на методах теории вероятностей. 4 Рассмотрим основные элементы системы обслуживания, которые представлены на рис. В.1. массового Рис.В.1. Основные элементы системы массового обслуживания. Входящий поток – совокупность требований на обслуживание, поступивших в систему за определенный интервал времени. Требование – это запрос на удовлетворение потребности. Требование часто отождествляется с его носителем. Если речь идет о потоке данных для обработки на ЭВМ, то требованиями могут считаться пакеты данных. В качестве требований в очереди в парикмахерской могут рассматриваться сами клиенты, в потоке больных в приёмном покое больницы – больные и в потоке приходящих на разгрузку в порт судов – сами суда. Системы обслуживания определяются числом приборов и бывают одноканальные и многоканальные (одна или несколько колонок на бензозаправке и т.д.). Многоканальные системы могут состоять из разнотипных приборов. Системы бывают полнодоступные и неполнодоступные (обслуживающие приборы или каналы доступны любому требованию – это полнодоступное включение). Полнодоступность и неполнодоступность иллюстрируется рис.В.2. Если использовать аналогии с телефонной связью, то, например, линия «а» доступна абонентам А и В, линия «с» доступна абонентам А и Д, а линия «е» доступна абонентам А, В, С, Д, т.е. всем абонентам. 5 Рис.В.2. Полнодоступное и неполнодоступное включение. Важным фактором, определяющим работу системы массового обслуживания, является способ обслуживания. Различают способы - в порядке поступления (FIFO), в обратном порядке (LIFO), случайным образом, обслуживание по приоритетам и ряд других. Возможно объединение очередей, взаимодействие очередей и т.д. Способ обслуживания тесно связан с поведением клиента – отказ становиться в очередь, использование клиентом априорной информации, уход из очереди до начала обслуживания (соглашение между клиентами) и т.д. Обозначенный на рис.В.1 выходящий поток, как элемент системы массового обслуживания важен, так как сам может быть входящим потоком для другой системы. Характеристики выходящего потока зависят от характеристик входящего потока и времени обслуживания (если в парикмахерской два мастера с разной производительностью, то это будет влиять и на входящий и на выходящий поток). Анализ выходящего потока позволяет найти характеристики обслуживающих приборов. В заключение подчеркнем еще раз, что под качеством обслуживания в теории массового обслуживания понимается не то, как хорошо выполнено обслуживание (бритьё, качество ремонта и др.), а как хорошо организовано обслуживание, насколько полно загружены приборы, не создаётся ли большая очередь, велик ли уход не обслуженных требований. 6 1. Потоки событий. 1.1. Основные определения. Поток событий – последовательность событий, происходящих одно за другим в случайные моменты времени. Графически поток можно отобразить так, как показано на рис.1.1, где на оси времени отмечено начало наблюдения 0 и моменты наступления событий t i , i  1,2,3... t1 t2 tk t Рис.1.1. Графическое отображение потока событий Потоки бывают однородными и неоднородными (просто самолёты или самолёты по маркам). Обычно используют однородные потоки. Регулярный поток – события следуют одно за другим через строго определенные промежутки времени. T1 T2 T3 Ti t Рис.1.2. Поток событий при независимых Ti Рассмотрим поток событий, представленный на рис.1.2, где Т1, Т2… - случайные интервалы времени (случайные величины), независимые между собой. Такой поток называется потоком Пальма или потоком с ограниченным последействием. Поток называется ординарным, если для малого Δt выполняется условие: 7 P1 (t , t )  P1 (t , t ) , (1.1) где P1 (t , t ) - вероятность того, что за Δt произойдёт одно событие и P1 (t , t ) - вероятность того, что за Δt произойдёт более одного события. Таким образом, поток можно считать ординарным, если за малый промежуток времени может произойти не более одного события (или ни одного события, вероятность чего обозначим P0 (t , t ) ). Для любого Δt очевидно справедливо: P0 (t , t )  P1 (t , t )  P1 (t , t )  1 , (1.2) т.к. составляющие формулы (1.2) определяют полную группу несовместных событий. Для ординарного потока: P0 (t , t )  P1 (t , t )  1, (1.3) потому что P1 (t , t )  O(t ) , где O(t ) - величина, порядок малости которой выше чем Δt, т. е.: O(t )  0. t 0 t lim (1.4) В качестве примера ординарного потока можно привести ситуацию на автостраде, когда машины пересекают линию «Стоп», даже при многорядном движении. Пример неординарного потока – поток пассажиров, прибывающих в лифте на данный этаж. Стационарный поток определяется следующим образом. Для стационарного потока вероятность появления некоторого числа событий за интервал τ, зависит только от τ (длины интервала) и не зависит от расположения τ на оси t. Регулярный поток и поток Пальма с одинаково распределёнными интервалами Ti являются стационарными потоками. 8 Возьмём ординарный поток. Среднее число событий, произошедших за время Δt (вычисляется по формуле математического ожидания): 0  P0 (t , t )  1  P1 (t , t )  P1 (t , t ) . Если существует предел P1 (t , t )  (t ) , t 0 t lim (1.5) то (t ) называется интенсивностью ординарного потока (размерность [1/t]). Для стационарного потока: (t )   - число событий в единицу времени. 1.2. Закон распределения интервала времени, на который падает точка. Пусть дан стационарный поток Пальма (см. рис.1.3). Все случайные интервалы времени между событиями независимы и имеют одинаковую функцию распределения F(t), которой соответствует плотность вероятности w(t). Здесь в соответствии с принятыми в теории вероятностей правилами записи формул, если случайная величина обозначена большой буквой Т, то аргумент плотности вероятности этой случайной величины обозначается малой буквой t. Это не должно приводить к путанице в обозначениях и ни в коем случае не означает, что w(t) рассматривается как функция текущего времени. На ось времени случайным образом «падает» точка S, и её положение никак не связано с моментами появления событий. Требуется найти закон распределения того участка T*, на который упала точка (см. рис.1.3). Описанная модельная ситуация возникает, когда пассажир (точка S) приходит на остановку, а автобус уже ушёл (предполагается, что поток автобусов – стационарный поток Пальма). 9 T T T T* T T t *S Рис.1.3. Интервал времени, на который падает точка. Закон распределения F (t  ) интервала T*, когда пассажир стоит на остановке, отличается от F(t). Упрощенное объяснение этого факта можно представить следующим образом (см. рис.1.4). 0,2 0,8 0,2 0,8 0,2 0,8 0,8 0,2 * t T* Рис.1.4. К определению закона распределения F (t  ) Пусть T принимает два значения с вероятностью 0,5: t1=0,8 и t2=0,2. На остановку приходит пассажир. Более вероятно, что он попадёт на участок длины 0,8. Хотя в среднем число интервалов t1 и t2 одинаково, но t1 в четыре раза длиннее t2. Поэтому вероятность попадания в отрезок длиной 0,8 в четыре раза больше вероятности попадания в отрезок 0,2. Получается, что эти вероятности равны соответственно 0,8 и 0,2. Итак, закон распределения, на который упала точка, отличается от априорного. Найдём в общем виде плотность w*(t) того интервала T*, на который случайным образом упала точка. Возьмём интервал (t, t+dt). Тогда: P  w* (t )dt - вероятность того, что S попадёт на интервал, длина которого заключена в промежутке ( t,t+dt ). Эту вероятность можно 10 определить как отношение суммарной длины таких промежутков на очень большом интервале к длине этого большого интервала. Пусть общее число промежутков (больших и маленьких) на большом интервале равно N. Среднее число промежутков, длина которых лежит в интервале (t, t+dt), по закону больших чисел равно Nw(t )dt , где w(t )dt - вероятность наличия любого интервала длиной из промежутка ( t,t+dt ) среди всех N интервалов. Средняя длина такого интервала - tw(t )dt . Средняя суммарная длина таких промежутков - Ntw(t )dt . Средняя общая длина большого интервала - NET , где E{} - символ усреднения. При известной плотности w(t) среднее Е{T} записывается в виде  ET    tw(t )dt  mt . (1.6) ( mt - еще одно обозначение среднего). Следовательно: w (t )dt  Ntw(t )dt t  w(t )dt . NET  ET  (1.7) При N   :  t  w(t ) t  0 w (t )   mt .  0 t0  (1.8) Как следует из (1.8) w (t ) обладает всеми свойствами плотности вероятности. Чтобы найти среднее и дисперсию случайной величины T* целесообразно использовать аппарат характеристических функций. По определению определяется как: характеристическая     e g ( x)  E e ixT  11 itx w(t )dt функция g(x) (1.9) и представляет собой прямое преобразование Фурье плотности вероятности. Характеристическая функция безразмерна, а переменная x имеет размерность обратную размерности случайной величины T. Соответственно плотность вероятности по известной характеристической функции может быть найдена с помощью обратного преобразования Фурье w(t )  1  itx e g ( x)dx . 2  (1.10) Свойства характеристической функции: 1) Если Ti независимые случайные величины и n n i 1 i 1 T (n)   Ti , то g ( n ) ( x)   g i ( x) . Если все Ti распределены одинаково, то g ( n ) ( x)  g ( x) n 2) g ( x)  1 3) g(x) используется для вычисления моментов: g (0)  1, g / (0)  ( d g ( x))  iET , dx x 0 g // (0)  (   d2 g ( x))  E T 2 . 2 dx x 0 (1.11) (1.12) Поэтому ET   ig / (0) , (1.13) DT    g // (0)  ( g / (0)) 2 , (1.14) где D{T }  E{T 2 }  E 2 {T } - дисперсия (второй центральный момент) случайной величины Т. Заметим здесь, что через производные более высокого порядка от характеристической 12 функции можно соответственно найти моменты распределения случайной величины более высоких порядков. 4) Если случайная величина T имеет характеристическую функцию g t (x) , то случайная величина Y  aT имеет характеристическую функцию в виде g y ( x)  g t (ax) . (1.15) Найдём характеристическую функцию случайной * величины T - интервала, на который случайным образом упала точка S. g  ( x)    e itx w (t )dt    e  itx tw(t ) dt mt Заметим справедливость соотношения teitx  i учетом которого можно записать g  ( x)  i d itx e , с dx d  itx w(t ) ig / ( x) e dt   . dx  mt mt С использованием выражения (1.13) ( ET   mt  ig / (0) ) для характеристической функции случайной величины T* окончательно получим g / ( x) g ( x)  / . g (0)  (1.16) На основе выражений (1.16), (1.13) и (1.14) найдём числовые характеристики случайной величины T*. Среднее значение   mt   E T  D g  / (0) g // (0)  mte  Dt   /   mt  t . i  mt mt ig (0) (1.17) Из (1.17) следует, что всегда mt   mt . Лишь в случае регулярного потока событий, когда интервалы становятся неслучайными и, следовательно, Dt=0, получается mt   mt . 13 Таким образом, указание на то, что S попало на какой-то интервал, как бы увеличивает его среднюю длину по сравнению с тем, как его оценивали бы без этого указания. Найдём дисперсию случайной величины T*:   D T    g //  (0)  ( g /  (0)) 2 ,       g /// (0)  iE T 3  iE T 3 E T3 g (0)  /    , iET  ET  g (0) g / (0) //  g /  (0)    g // (0)  E T 2  , iET  g / (0) ( g /  (0)) 2     D T    (E T 2 ) 2 , ( ET ) 2         E T 3 (E T 2 ) 2 E T 3 (E T 2 ) 2    . ET  ( ET ) 2 mt mt2   Из (1.18) видно, что дисперсия D T  больше и меньше дисперсии DT . (1.18) может быть и 1.3. Закон распределения времени до наступления очередного события Пусть имеется стационарный поток Пальма и точка S, занимающая на оси t любое положение (см. рис.1.5). T T T T* T T S H * Рис.1.5. К определению закона распределения . 14 t Плотность распределения интервала T* отличается от плотности распределения w(t ) всех остальных T и согласно (1.8) записывается в виде w (t )  t w(t ), t  0 . mt Найдем закон распределения случайной величины . Для этого рассмотрим гипотезу: интервал T* принял значение на участке (t* , t* + dt*). Вероятность справедливости этой гипотезы запишется как w * (t*)dt*  t * w(t*) dt * . mt Будем искать плотность распределения  при условии справедливости сформулированной гипотезы. Эту условную плотность обозначим   / t  .   Нет оснований считать какой-то участок интервала t*, на который упала точка S, более вероятным для положения этой точки, чем другой. Поэтому точка S на интервале t* будет распределена равномерно и условная плотность   / t  тоже будет равномерна  1  , при   (0; t*) ( t*)   t * . 0, при   (0; t*) Совместная плотность  и T* имеет вид:      w t  ,   w t    / t  .  (1.19) (1.20) Безусловная плотность: ()       w(t*;)dt*   w * (t*)( / t*)dt * . (1.21) С учетом (1.19) подынтегральная функция отлична от нуля при 0   t* , т.е. при t*  . Поэтому (1.21) преобразуется к виду 15  t* 1 1  1  F () , w(t*)  dt  w(t*)dt*   m t * m m t t  t  ()   (1.22) где F(x) - функция распределения случайной величины T. x F ( x)   w(t )dt 1  F () при   0  . ()   mt 0 при   0  Итак: mt  E (T ) Здесь величины T. - математическое ожидание (1.23) случайной Найдем числовые характеристики случайной величины  через её характеристическую функцию g  (x)  g  ( x)   e ix ()d   1  ix e (1  F ()) d . mt 0 (1.24) Интеграл в (1.24) можно вычислить по частям. Обозначая имеем u  1  F () , dv  eix d , du  w()d , v 1 ix e . ix Теперь 1 g  ( x)  mt  e ix  (1  F ())  ix    g ( x)  1 e ix ,  w()d  imt x 0 ix   где g(x) – характеристическая функция случайной величины T (как преобразование Фурье w(t)). Напомним, что согласно (1.11) g ' (0)  iE(T )  imt , g (0)  1 , поэтому: g  ( x)  g ( x)  g (0) . xg ' (0) Найдем E и D . 16 (1.25)  g ( x)  1   m  E  ig (0)  i  imt x  1 g ' ( x)  x  g ( x)  1   x 0 mt x2 / /  x 0  1 d  g ( x )  1    x 0  mt dx  x  . Если в последнем выражении подставить x  0 , то получится неопределенность типа . Раскроем её по правилу Лопиталя. m   1 g ( x)  x  g ( x)  g ( x)  mt 2x x 0  g ( x) 2mt x 0  g (0) . 2mt Согласно формуле (1.14)  g (0)  Dt  mt2 , поэтому Dt  mt2 1  D  m m    mt  t   t* 2mt 2  mt  2 (1.26) (после третьего знака равенства учтена формула (1.17)). Следовательно, математическое ожидание остатка  всегда не меньше, чем половина математического ожидания любого интервала между событиями в стационарном потоке Пальма. Поступая аналогично, найдем дисперсию D     E T 3 (E T 2 )2 . D   3mt 4mt2 (1.27) В заключение параграфа заметим, что случайные величины Н и  зависимы (вследствие соотношения   H  T  , см. рис.1.5), а закон распределения Н такой же, как у . 17 1.4. Пуассоновский поток событий. Пуассоновский поток – это поток обладающий двумя свойствами – ординарностью и отсутствием последействия. Понятие ординарности было объяснено выше, а свойство отсутствия последействия можно сформулировать следующим образом: для двух неперекрывающихся интервалов времени число событий, попадающих в один интервал, не зависит от того, сколько событий попало в другой. Пусть дан стационарный поток с интенсивностью  . Из ординарности потока следует: - вероятность наступления одного события за время t : p  λ  t  O(t ) - вероятность ненаступления события q  1  λ  t  O(t ) Рассмотрим интервал T  m  t , представленный на рис. 1.6. Из независимости (отсутствия последействия) событий на соседних интервалах следует, что вероятность наступления k событий на m интервалах определяется биномиальной формулой: P(k )  Cmk p k q mk , где число сочетаний C mk  t t t (1.28) m! . (m  k )!k! t . . . t t T  m  t Рис. 1.6. К определению пуассоновского потока событий. 18 Для вычисления факториалов используем формулу Стирлинга m! 2m m m e  m (1.29) (при m=1 ошибка вычислений по (1.29) составляет 8%, при m=100 ошибка - 0,08%), а для вычисления (1    t ) T t при T t  0 - второй замечательный предел lim (1    t ) t  e T . t 0 С учетом сделанных замечаний формула (1.28) преобразуется к виду P(k )  (  T ) k  T e , k! (1.30) и именно в таком виде она известна как распределение Пуассона, где k=0,1,2,... Вид этого дискретного распределения приведен на рис.1.7. T  1 0,4 P 0,4 P 0,3 0,3 0,2 0,2 0,1 0,1 T  2 k 1 2 3 4 5 k 6 1 2 3 4 5 6 Рис.1.7. Распределение Пуассона Заметим, что распределение Пуассона удовлетворяет условию нормировки   P(k )  1 . k 0 В случае нестационарного потока распределение Пуассона записывается в виде: Pt .,T (k )  (a(t , T )) k a (t ,T ) e , k! 19 (1.31) где a(t , T ) -среднее число событий, наступающих на интервале T, примыкающем к моменту t, a(t , T )  t T  (t )dt , t а (t ) - интенсивность нестационарного потока. В стационарном случае a(t , T )  a(T )  t T  dt  T и получа- t ется формула (1.30). Найдем среднее и дисперсию распределения Пуассона. Среднее:  Ek   kP(k )  T . (1.32) k 0 Вычисление (1.32) иллюстрируется следующими соотношениями (с учетом условия нормировки)  k k 0   (  T ) k  T (T ) k 1 ( T ) n e  Te T  Te T   T . k! ( k  1 )! n ! k 1 n 0 Дисперсия:    2 (k )  Ek  Ek  E k 2  E 2 k  T . 2 (1.33) Здесь необходимо отметить, что распределение Пуассона обладает уникальным свойством – равенством среднего и дисперсии, - что отличает его от всех известных распределений и может служить признаком при идентификации распределения на практике. Из отношения ( k ) 1  Ek  T следует, что при больших T распределение тесно группируn ется около среднего. Оценкой  может служить величина , где T n - измеренное на практике число событий на интервале Т. 20 Стационарный пуассоновский поток событий называется простейшим потоком. Рассмотрим теперь интервалы времени  (см. рис.1.8) между событиями в стационарном пуассоновском потоке, которые представляют собой непрерывные случайные величины. Возьмем начальный интервал времени (он ничем не отличается от всех остальных), и отметим после 0 некоторую точку x. На интервале (0, x) не будет ни одного события, если  x. τ x * τ x * t t 1- первое поступление Рис.1.8. Анализ интервалов времени в пуассоновском потоке Вероятность выполнения этого неравенства может быть вычислена по формуле (1.30) для k  0 с учетом того, что х=Т P(  x)  P(k  0)  e  x . при x T Далее: P(  x)  1  e x Последнее выражение - это (по определению) функция распределения случайной величины  , т.е. P(  x)  F ( x) . Но тогда w ( x)  dF ( x)   e  x , dx (1.34) т.е. для пуассоновского потока  имеет экспоненциальное распределение для   0 (см. рис. 1.9). 21 w λ x 1/λ Рис.1.9. Экспоненциальное распределение. Характеристики экспоненциального распределения:  среднее - mt  E ()   w()d  1 ,   дисперсия - Dt   2     E () w()d  2 1 . 2 Если случайная точка S попадает на интервал T * между событиями в пуассоновском потоке (см. предыдущий параграф), то w (t )  1 w(t )  2 te t , t  0 . mt (1.35) Формула (1.35) – это распределение Эрланга 1-го порядка. При этом согласно формулам (1.17), (1.18) получим E (T  )  mt  Dt 2  mt  и D(T  )  2 . 2 Сравнивая mt и E (T  ) , а так же Dt и D(T  ) , можно утверждать, что наличие случайной точки S в каком-либо интервале пуассоновского потока “раздвигает” его, увеличивая среднее и дисперсию вдвое. Теперь найдем () для пуассоновского потока. 22 1  F () 1  (1  e   ) ()    e  , 1 mt  (1.36) что совпадает с экспоненциальным распределением, справедливым для интервала времени между событиями в пуассоновском потоке, т.е. случайная величина  распределена так же, как и T. Это является формой проявления свойства отсутствия последействия. Любая информация о том, как вел себя поток до точки S, не дает нам сведений о том, что произойдет после точки S. Вычислим характеристическую функцию интервала между соседними событиями в простейшем потоке.  g ( x)   e itx e t dt     (  ix)e (  ix )t dt  .    ix 0   ix (1.37) Итак, поток Пальма является простейшим, если характеристическая функция интервала между соседними  событиями равна .   ix В заключение отметим одно важное свойство пуассоновского процесса. Пусть есть m пуассоновских потоков с интенсивностями  1 ,  2 , …  m . Объединим эти потоки. Тогда объединенный поток будет опять пуассоновский m с интенсивностью     n . Покажем справедливость этого n 1 утверждения. Пусть N (i ) (t , t  t ) - число событий i-го процесса в N (t , t  t ) - число событий в промежутке (t , t  t ) , i=1,2…m. объединенном процессе. 23 m P( N (t , t  t )  0)   P( N (i ) (t , t  t )  0)  i 1 m   [1  λ i t  O(t )]  1  λt  O(t ) , i 1 m где     i . Ответ становится очевидным, если учесть, что t i 1 в степени выше первой является величиной высшего порядка малости по сравнению с t . Аналогично: P( N (t , t  t )  1)  λt  O(t ) . 1.5. Вывод формулы Пуассона через производящую функцию. Рассмотрим поток событий, обладающий свойствами ординарности и отсутствия последействия. Пусть Pn (t ) - вероятность того, что за малый интервал времени t , примыкающий к моменту времени t, произойдет n событий. Очевидно 0  Pn (t )  1, и будем считать, что выполняется условие нормировки   Pn (t )  1. Опишем динамику изменения вероят- n 0 ности состояния потока за время t . Для n=0 (отсутствие событий на интервале t ) можно записать: P0 (t  t )  P0 (t )(1  t ) . (1.38а) Множитель (1  t ) является в силу ординарности потока вероятностью того, что за интервал t не произойдет ни одного n  1 согласно формуле полной события. Для любого вероятности аналогично (1.38а) запишем Pn (t  t )  Pn (t )(1  t )  Pn1 (t )t . (1.38б) Из последнего выражения легко получить Pn (t  t )  Pn (t )  Pn (t )  Pn1 (t ) для n  1. t 24 При t  0 слева получается производная Pn (t )  dPn (t ) , и в dt соответствие с этим выражения (1.38а) и (1.38б) можно переписать в дифференциальной форме. P  (t )  P (t )  0    Pn (t )  Pn (t )  Pn1 (t ) n0 n 1 . (1.39) Это - дифференциально-разностные уравнения, которые удобно решать, используя производящую функцию. По определению производящая функция является Z – преобразованием распределения вероятностей и записывается в виде:  G( z, t )   Pn (t ) z n  P0 (t )  P1 (t ) z  P2 (t ) z 2  ...... , (1.40) n 0 где z – любое комплексное число, которое дает сходимость суммы в (1.40). Из (1.40) следует, что если G( z, t ) продифференцировать n раз по z, то можно найти Pn (t ) , положив z=0, т.е. Pn (t )  1 d n G( z, t ) n! dz n . (1.41) z 0 При решении уравнений начало отсчета времени можно выбирать произвольно, даже после того, как произойдет некоторое число событий. Возможно, что при t=0 уже произошло i событий. Тогда: Pn (0)  0 при n  i, Pn (0)  1 при n i. Таким образом  G( z,0)   Pn (0) z n  Pi (0) z i  z i . (1.42) n 0 Из определения G( z, t ) также следует: G(1, t )  1 , 25 (1.43)  dG( z, t ) d     Pn (t ) z n   Pn (t ) z n . dt dt n0 n 0 и (1.44) Умножим систему (1.39) на z n (первое уравнение на z 0 ) и просуммируем по n, тогда получим:     n n P ( t ) z    P ( t ) z    n  n  Pn1 (t ) z n . n 0 n 0 n 1 Слева от знака равенства согласно (1.44) записана dG( z , t ) . Первое слагаемое справа очевидно имеет dt вид {G( z, t )} , а второе представляется как производная    P0 (t ) z  P1 (t ) z 2    zG( z, t ) . В итоге получаем дифференциальное уравнение dG( z, t )  ( z  1)G ( z, t )  0 , dt которое, как известно, имеет решение: G( z, t )  Ce ( z 1)t . Константа C определяется из начальных условий. Пусть при t=0 не было ни одного события. Тогда из (1.42) следует, что G( z,0)  1 т.к. i=0. Поэтому С=1. Окончательно получаем: G( z, t )  e  ( z 1)t . (1.45) Теперь воспользуемся формулой (1.41) : P0 (t )  e t , P1 (t )  e t ,  (  t ) n e  t Pn (t )  . n! Последняя формула совпадает с распределением Пуассона, где t интерпретируется как интервал (0,t). 26 1.6 Другие стационарные потоки Пальма. Регулярный поток: Здесь T  mt , что и обозначено на рис.1.10. Из теории вероятностей известно, что плотность вероятности неслучайной величины определяется дельта-функцией. mt mt mt mt ... ... mt t *θ Рис.1.10. Регулярный поток. Поэтому для постоянного интервала mt можно записать w(t )  (t  mt ) . (1.46) Напомним здесь основные свойства дельта-функции. 1. Фильтрующее свойство. Если () - произвольная функция (без разрывов в 0), то справедливо соотношение 0   ()()d  (0) . Здесь – малая константа. 0 2. При ()  1 0  ()d  1 . Естественно, что и в 0 бесконечных пределах интегрирования результат будет такой же. Это позволяет утверждать, что дельта-функция как плотность вероятности удовлетворяет условию нормировки. 3. δ(τ)  0 при τ  0 . 4. τδ(τ)  0 . 27 Вернемся к регулярному потоку. Для него очевидно Dt  0 . Найдём плотность вероятности интервала, на который падает точка S w (t )  t  mt  mt t t w(t )  (t  mt )  (t  mt )  (t  mt ) . (1.47) mt mt mt Как видно из (1.47) случайная точка S никак не изменяет вероятностные свойства интервала, на который она попадает. Найдём закон распределения времени  от случайной точки до очередного события  1  F     mt 1   (t  mt )dt mt  1    mt 0   (0, mt ) . (1.48)   (0, mt ) Получился равномерный закон для плотности вероятности. В этом нет ничего удивительного, если вспомнить, что при падении точки S было предположено, что она с равной вероятностью может попасть в любой бесконечно малый промежуток интервала Т*. Найдём числовые характеристики распределения (1.48). m  Из формулы (1.26) D  Из формулы (1.27) mt D m  t  t. 2 2mt 2 mt3 (mt2 ) 2 mt2 .   3mt 12 4mt2 Характеристическая функция:     e g ( x)  E e ixT itx (t  mt )dt  e imt x . (1.49)  Регулярный поток для моделирования потока событий используется редко, так как он обладает неограниченным последействием, т.е., зная лишь один момент наступления события в регулярном потоке, можно восстановить всё прошлое и предсказать всё будущее потока. 28 Нормальный поток. По определению одномерная нормальная плотность вероятности имеет вид (формула записана применительно к случайной величине Т ): w(t )   1  t 2 ( t  mt ) 2 e 2 t2 . (1.50) В (1.50) mt - среднее значение и  2 - дисперсия распределения. График нормальной плотности приведен на рис.1.11. w t t t mt Рис.1.11. График нормальной плотности вероятности. Строго говоря, интервал времени не может быть распределён по нормальному закону, так как область определения нормального закона (,) . Однако, если mt  3 t , то этот закон можно выполняется условие приближенно использовать. Устремим  t  0 . Тогда из (1.50) следует: lim  t 0 1  t 2  e ( t  mt ) 2 2 t2 Плотность распределения случайным образом упала точка S: 29  (t  mt ) . интервала, (1.51) на который w (t )  t t f (t )  e mt mt  t 2  ( t  mt ) 2 2 t2 t  0. (1.52) Соответственно плотность вероятности интервала от точки S до наступления очередного события имеет вид ()  1  F ()  mt   mt ) t mt 1   ( (  0) , (1.53) где t2 1 x 2   ( x)   e dt . 2   Характеристическая распределения g ( x)   e itx  (1.54) функция 1  t 2  e ( t  mt ) 2 t2 dt  e imt x  нормального t2 x 2 2 . (1.55) Поток Эрланга Поток Эрланга получается путём особого преобразования («разрежения») простейшего потока. Это преобразование осуществляется путём выбрасывания некоторых событий из простейшего потока. Процесс «разрежения» потока поясняется на рис.1.12, где буквой П обозначен простейший поток. Если выбрасывается каждая вторая точка, то получается Э1 – поток Эрланга первого порядка. Если выбрасывается два события подряд и оставляется каждое третье, то получается Э2 – поток Эрланга второго порядка и т.д. Потоком Эрланга k-го порядка называется поток Пальма, у которого интервалы между событиями представляют собой сумму (k+1) независимых случайных величин, распределённых одинаково по экспоненциальному закону с параметром  , где  - интенсивность простейшего потока и k  0,1,2,... 30 П П t T1 T2 T3 T4 t T1 ... Э1 t T2 T3 ... Э2 t Рис.1.12. «Разрежение» простейшего потока. При k  0 получается исходный простейший поток П. Для простейшего потока характеристическая функция интервала времени между соседними событиями определяется в виде g ( x)  следует, что 1 . Из свойств характеристической функции   ix для суммы k 1 независимых интервалов    характеристическая функции будет иметь вид.      ix  k 1    Поэтому для Эk можно записать g k ( x)    .    ix  k 1 . Совершая обратный переход от характеристической функции к плотности вероятности, получим для Эk: w(t )   (  t )  t e k! t  0. (1.56) Функция распределения для этой плотности имеет вид ( t ) n  t e . n 0 n! t k F (t )   w(t )dt  1   (1.57) Соответственно числовые характеристики определяются  как mt   tw(t )dt   k 1 ,  Dt   (t  mt ) 2 w(t )dt  31 k 1 . 2 При достаточно большом k (k>5) поток Эk можно считать приближённо нормальным. Это следует из того, что в Эk суммируется k+1 независимых величин (интервалов), распределённых одинаково, а такая сумма согласно центральной предельной теореме теории вероятностей (ЦПТ) при k   асимптотически нормальна. Предельная теорема для суммарного потока. Суммарный поток получается в результате «сложения» потоков. Для простейших потоков П1 и П2 «сложение» состоит в том, что все моменты появления событий в этих потоках относятся к одной оси времени, на которой отмечаются моменты появления событий в суммарном потоке П1+П2=П. П1 t П2 t П t Рис.1.13. Сложение простейших потоков. Как было установлено выше, суммарного потока справедливо: для интенсивности n     j , где n – число j 1 суммируемых потоков, а  j j  1,2,n - интенсивности суммируемых потоков. Предельная теорема для суммарного потока утверждает сходимость суммы независимых, ординарных, стационарных потоков к простейшему потоку. При этом условия, налагаемые 32 на суммируемые потоки, приблизительно такие же, как и условия ЦПТ: - складываемые потоки должна оказывать более или менее одинаково малое влияние на суммарный поток (не должно быть потоков с очень большой  ), -  j не должны при j   становиться исчезающе малыми. Сходимость к простейшему потоку осуществляется очень быстро (уже при n  4  5 ). Зависимые потоки при сложение так же дают сходимость к простейшему потоку, но, естественно, при существенно большем числе слагаемых. Сложение нестационарных потоков даёт нестациn онарный пуассоновский поток с интенсивностью (t )    j (t ) . j 1 Пуассоновский поток, как было показано выше, обладает устойчивостью (то есть при суммировании пуассоновских потоков вновь получается пуассоновский поток). Предельная теорема для редеющего потока. Рассмотрим специфическую операцию «разрежения» потока, когда событие переносится в разреженный поток с вероятностью p и, следовательно, отбрасывается с вероятностью q  1  p . Рис.1.14. поясняет такое разрежение потока, где обозначено: П–исходный поток (стационарный поток Пальма) и Пр – разреженный поток. Исследуем характеристики потока Пр. Для Тр справедz ливо: T p   Ti , где случайные величины Тi взаимно незавиi 1 симы, z – случайная величина, представляющая собой число просуммированных интервалов. Найдем вероятность того, что случайное число z равно некоторому фиксированному k. 33 П t T Tp Пp t Рис.1.14. Вероятностное разрежение потока. Очевидно: P( z  k )  pq k 1 k  1,2,3,... . Предположим z=k. Тогда при справедливости этой гипотезы характеристическая функция (условная) случайной величины Тр определяется как: g Tp / k ( x)  ( g ( x)) k , где g(x) - характеристическая функция случайной величины Тр. Безусловная характеристическая функция:   k 1 k 1 g Tp ( x)   P( z  k ) g Tp / k ( x)   pq p qg ( x) pg ( x)    q 1  qg ( x) 1  qg ( x) k 1 p  ( g ( x))   ( g ( x)q) k  q k 1 k . Результат получен в предположении 0  q  1 и g ( x)  1 с использованием формулы для суммы S N членов геометрической прогрессии при N   . (Если b0 , b1 ,bN - геометрическая N b  bN r прогрессия со знаменателем r , то S N   bn  0 и 1 r n 0 S   lim S N ). Зная g Tp (x) всегда можно найти плотность N  распределения wTp (t ) . 34 Найдём числовые характеристики случайной величины Тр, но предварительно вычислим E (z ) и D(z ) .   z 0 k 0 E ( z )   zP( z )   kpqk 1  p d  k d 1 1 q p ( ) .  dq k 0 dq 1  q p  D( z )  E ( z 2 )  ( E ( z )) 2   k 2 pq k 1  k 1 d   q  1  p q   kqk 1   2  2 dq  k 1 p  p 1  p2 .   найдём через характеристическую функ- Среднее E T p цию g Tp (x) . Согласно (1.11): ET p   igT/ p (0) . g T/ p ( x) x 0  pg / ( x)1  qg ( x)  pg ( x)qg / ( x) (1  qg ( x)) 2  x 0 g / (0) , так как p g (0)  1 . ig / (0) Итак ET p    . Но  ig / (0)  ET , поэтому: p ET p   ET  Ez. (1.58) Рассуждая аналогично, можно получить: D(T p )   gT//p (0)  ( gT/ p (0)) 2  DT Ez  ( ET ) 2 Dz. (1.59) Очевидно, что интенсивность простейшего потока мож1 но определить как   . Соответственно для разреженного ET  потока с учетом (1.58) запишем p  1 1   p . ET p  ET  Ez Теперь можно перейти к предельной теореме для редеющих потоков. Смысл её состоит в том, что если последовательно разрежать ординарный стационарный поток 35 Пальма достаточно большое число, то такой многократно разрежённый поток будет близок к простейшему. На практике уже 4  5 кратное разрежение (при р<0,8) даёт поток близкий к простейшему, даже если исходный поток был регулярным. 36