О приближении потока событий к пуассоновскому

ЧЕБЫШЕВСКИЙ СБОРНИК

Том 18 Выпуск 2

УДК 519.21 DOI 10.22405/2226-8383-2017-18-2-222-234

О ПРИБЛИЖЕНИИ ПОТОКА СОБЫТИЙ К ПУАССОНОВСКОМУ

Ларкин Е.В., Горбачев Д.В., Привалов А.Н.

Аннотация

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

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

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

Библиография: 14 названий.

ON THE APPROXIMATION OF THE FLOW OF EVENTS FOR

A POISSON

Larkin E. V., Gorbachev D. V., Privalov A. N.

Abstract

When modeling an extensive class of technical systems, the mathematical apparatus of queuing systems (QMS) is widely used. An example of such a system is the computer network, where computer applications are generated and executed. Applications are generated usually not regularly, but by accident, forming the so-called random order of applications (requirements). Service requests, it also continues some random time. One of the central issues in the organization of mass-service systems is the elucidation of the regularities that subordinate the moments when system requirements for service are submitted.

The article explores the flow of events in technical systems of various purposes. On the basis of the fact that under the Poisson character of the flow mathematical modeling of the systems is greatly simplified, the problem of obtaining a simple criterion for determining the degree of approximation of the flow of events to a Poisson one is posed. Pearson's criterion, regression, correlation and parametric criteria were investigated. A criterion based on the calculation of the waiting function was obtained again. On the example of the study of the system with

"competitions"it is shown that the flow of events generated by the system tends to Poisson with an infinite increase in the number of "competing"subjects.

Keywords: Event flow, Poisson flow, semi-Markov process, Pearson's criterion, correlation, regression, expectation function, uniform law.

Bibliography: 14 titles.

1. Введение

Существует обширный класс систем, состояние которых характеризуются потоком событий. Примером такого рода систем является вычислительная сеть, где генерируются и выполняются заявки на выполнение вычислительных работ. Заявки генерируются обычно не регулярно, а случайно, образуя так называемый случайный поток заявок (требований). Обслуживание заявок, также продолжается какое-то случайное время. В качестве показателей эффективности ('МО используются: среднее число заявок, обслуживаемых в единицу времени; среднее число заявок в очереди; среднее время ожидания обслуживания; вероятность отказа в обслуживании без ожидания; вероятность того, что число заявок в очереди превысит определенное значение и т.п. В качестве событий могут рассматриваться поступление заявок на обслуживания [1, 2], завершение интерпретации программы [3, 4], поток транзакций при дистанционном управлении [5, 6] и т.п. События происходят в физическом времени, а интервал между событиями, для внешнего наблюдателя, является случайной величиной. Одной из разновидностей потока является стационарный пуассоновский поток, который обладает следующими свойствами: стационарностью, отсутствием последействия, ординарностью [7]. Использование абстракции «пуассоновский поток» позволяет существенно упростить выкладки в ряде приложений, в частности в теории массового обслуживания, поэтому при исследовании систем подобного класса возникает вопрос о степени приближения плотности распределения времени между событиями g(t) к плотности распределения интервалов в простейшем потоке, которая определяется экспоненциальным законом распределения.

2. Регрессионный критерий и критерий Пирсона

Интервалы времени между событиями в пуассоновском потоке характеризуется экспоненциальным законом распределения [7]

S

где T - математическое ожидание экспоненциального закона;

Регрессионный критерий основан на оценке интеграла квадрата разности между анализируемым g (t) и экспоненциальным (1) законами [8]:

оо

вг = j [g

0

Очевидно, что если g (t) ^ f (t), то er ^ 0.

Пустьд (t) = ô (t — T), гдe ô (t — T) - смещенная ¿-функция Дирака, для которой

оо

Ô

[ œ when t = T ;J 0

Тогда

те

= У [5

где

Т+а 2

1 4 2

= / *<«- Т =ат I ш

— ) М = ж;

Т-а те

£г2 = 5(1 -Тд)  ^ехр(-Т^М = -^Т ; о

Т

= / Т1 ехр( - |)^ = 21Т-

о

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

В том случае, если временные интервалы между событиями определяются экспериментально, и плотность распределения д (£) представляет собой статистический ряд вида

а(г)= ( ¿о < Ь и-1 < г < £ к < \

( ) V п1 "' п "' ),

где щ - количество результатов измерения, лежащих в интервале < £ < то для оценки близости плотности (3) и гистограммы (6) может быть использован критерий Пирсона [9], который в данном случае принимает вид

^ {Тщ - [ехр (-- ехр (-]  ^=1^}2

* 3-1

- ехР - еХР [-Т -Ъг=1Пг\

= £ 1 „ Г ^ ,-л-А-УГ^-- - ^

з=1 Т

ехр (-Ц-1^) - ехр  ^пк

Критерий (7) достаточно громоздок и применим в ограниченном количестве случаев.

3. Корреляционный критерий

Корреляционный критерий имеет вид [10]

те

= У д (*)  Т ехР ^-Т^) Мо

Определим значение второго критерия для случаев д (¿) = Т ехр (- Т) и 9 (^) = 5 (£ - Т).

В первом случае критерий достигает максимума:

те

=у Тех^-  Техр (- ^)м=

о

Во втором случае критерий достигает минимума

те

£с2 = У 5(1 - Т) ехр ^ - м = ±

Однако, если критерий - это индикатор отсутствия последействия, он должен быть безразмерным и укладываться в интервал 0 ^ ес ^ 1 Нуль должен достигаться в первом случае (отсутствие последействия), единица должна достигаться во втором случае (детерминированная связь между событиями). Это происходит, если значение ес, рассчитанное как корреляция по зависимости (8), будет пересчитано по формуле

= ф-ЯЪ)

с е-2 1 ;

Критерий ес изменяется в интервале 0 ^ ес ^ 1.

4. Параметрические критерии

Простейший вариант параметрического критерия основан на следующем свойстве экспоненциальной плотности распределения [11]:

Т = /О,

где В - дисперсия, определяемая по зависимости

О

(* -Т )2

Т

ехр

Очевидно, что подобными свойствами обладают многие плотности распределения, например, взвешенная пара вырожденных законов, д (Ь) = 0, 55 (Ь — т\) + 0, 55 (£ — т2), если т\ = 0, т2 > 0. Это затрудняет практическое использование зависимости (9).

Для установления более сложного критерия рассмотрим процесс генерации событий, как «соревнование», в котором участвуют два субъекта: внешний наблюдатель и генератор. Если в момент старта одновременно запускаются случайные процессы, характеризующие ременные интервалы между стартом и наблюдением и между двумя событиями, то «соревнование» может быть описано с помощью 2-параллельного полумарковского процесса [12, 13]

М = [А, Н (*)]

где А = {а,ы1, аш2, ад\, ад2, } - множество состояний; а,ш\, ад\ - стартовые состояния; аш2, ад2 - поглощающие состояния; Н (¿) - полумарковская матрица;

Н (I ) =

ад (*) 0

0

0

( ) 0

;0

00 00

Рассмотрим ситуацию, когда первый субъект выигрывает «соревнование» в момент време-

по полумарковскому процессу (10) (рис. 1 а) может быть построен ординарный полумарковский процесс (рис. 1 Ь) вида

М' = [А', Н' СО] ,

где А' = А У В - множество состояний; А = {а\, а.2, аз} - подмножество состояний, моделирующее начало и окончания блужданий по полумарковскому процессу; а1 - стартовое состояние; а2 аз

состояние, моделирующее окончание ожидания первым субъектом финиширования второго,

проигравшего субъекта; В = {Д, ..., ^, ...} - бесконечное множество состояний, задающих временные интервалы для различных ситуаций завершения дистанции вторым, проигравшим, субъектом; Ы (¿) = {Н'т п (£ )} - полумарковская матрица, задающая временные интервалы процесса.

Элементы Н'т п

второго субъекта, если он является «победителем» «соревнования»,

Ы12

г

где Ш (¿) = / ад (в) АО - функция распределения; в - вспомогательная переменная; о

Ы 2+ (¿)) 1 = 1, 2, ..., определяются как взвешенные плотности распределения времени «соревнования» и ожидает второго субъекта;

Ы, 2+г

второго субъекта; С (¿) = J д (в) АО] ад (г) [1 — С (г)] йт - вероятность финиширования первого

о

щ (I) • д(1 + т) 1 — С (т) ,

где щ(£) - единичная функция Хевисайда - плотность распределения времени пребывания полу-

В

плотности д (£ + т) значений с отрицательным аргументом.

В

ГО ГО

paoß = j[1 -G (r)j w (r)dT = jw (t) g (t) dt.

оо Взвешенная плотность распределения времени ожидания первым субъектом финиширования второго субъекта равна

те

(г) = г](г)! ы (т) д(ь + т) йт. о

Чистая плотность распределения определяется следующим образом

те

V (^¡Ы (т)д(1 + т)йт

и^д № =----

/ w

о

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

те

Г] (г) / д (т) ы (г + т) йт

^) = те = &) .

/ с

о

Рассмотрим поведение (Ь) для двух видов функции д (¿): когда указанная функция

описывает поток событий без последействия, т.е. д (1 ) = Т ехр (-Т)> и когда поток событий

( ) = ( - Т) Выражение (15) для первого случая принимает вид:

те

ц (^ /ы (т) Т ехр [-Ц^] йт

fw—g

А 1

ГО

1 - / [1 - exp

t=0

Таким образом, плотность j~ w—yq (t) отражает свойство отсутствия последействия в строго марковских процессах с непрерывным временем, которое может быть сформулировано следующим образом. Если плотность распределения времени между любыми двумя событиями в системе распределена по экспоненциальному закону, то для внешнего наблюдателя время, оставшееся до наступления очередного события, будет также распределено по экспоненциальному закону, независимо от момента начала наблюдения. Выражение (15) для второго случая принимает вид:

w

определения Tw m;n ^ arg w (t) ^ Tw max и математическое ожидание Tw min ^ Tw ^ Tw max. В зависимости от местоположения w(t) и g(t) на оси времени, возможны следующие ситуации:

a)T < Tw min. В этой ситуации выражение (5) не имеет смысла.

b) Tw min ^ T ^ Tw max. В этой ситуации плотность распределения выражается зависимостью (17), область определения fw—g (t) определяется как 0 ^ arg [fw—g (i)j ^ T — Tw mjn, и

ГО

/ tfw—a (t) dt < T. 0

c)T>Tw max В ЭТОЙ Ситуации fw^-g (t) — W(T t), T Tw max ^ arg [ fw^-g ^ T Tw minj

oo

и f tfw^g (t) dt < T. 0

Таким образом, математическое ожидание функции fw^g(t) для пуассоновского потока событий остается неизменным, а для детерминированного потока событий уменьшается, и это

W

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

Пусть плотность распределения времени наблюдения определяется вырожденным законом распределения с математическим ожиданием, равным Т, т.е. w (t) — 5 (t — T) (соответствует детерминированному потоку событий). Для этого случая плотность распределения времени ожидания ¿-функцией Дирака события, когда завершится событие g(t), определяется по зависимости

¡^ ю — "

т

Математическое ожидание (18) имеет вид

o

Ts^g — i tOO^11 dt.

0 j'g(t)dt

T

Критерий, основанный на определении времени ожидания, имеет вид

2

(ЧН'

где Т - математическое ожидание анализируемой плотности распределения времени между соседними событиями; - математическое ожидание плотности распределения (Ь),

рассчитываемое по зависимости (18). Для экспоненциального закона

^ =

Это означает отсутствие последействия. Для строго детерминированной связи между событиями, выражаемой ¿-функцией Дирака д

2

Это означает детерминированную связь между событиями, или «абсолютное последействие».

Исследуем поведение критерия у/ё^функции. Для этого определим математическое ожидание функции д

oo Т oo oo

J tg (t) dt — J tg (t) dt + Jtg(t + T) dtT + T J g(t + T) dt — , ,

0 0 0 0 — 'P\gT\g + P2g Ts^g + P2g T — T,

T oo

где Pig — J g (t) dt; p2g — J g (t) dt. 0 T

w

prob time

0.5

/ / / f

\яо У P2/s^t) ч j t-T/ / / / /

// Т о< / / * P2jfS—>j

0 0.5 1 1.5 2 time

Рис. 30: К расчету математического ожидания

Очевидно, что в (23) Т2 = Если д (t) = f (t), то из уравнения

Pi f Ti f + Р2 f Ts^f + P2f T = T,

где pif = V \P2f = i\Tif = T f-1,

следует, что

Ts^f = T.

Равенство (25) подтверждает справедливость зависимостей (16) и (21). При g (t) = f (t) из (23) следует

Via

1 - Vi a

Ts^a = "''Г - 1ä>.

Значение , в зависимости от соотношения значений Т\д и р\д может быть как > Т, так и < Т (случайТ$^д = Т представлен зависимостями (24), (25)). Очевидно, что первые два случая означают, что поток не является Пуаесоновеким

5. Пример

В качестве примера рассмотрим случай, когда поток событий формируется в результате «соревнования» К субъектов с равновероятными и одинаковыми законами распределения (рис. 2). Модель формирования потока может быть представлена в виде /Г-параллельного полумарковского процесса, показанного на рис. 2 [11],

Мк = [Ак, Ък СО] ,

где Ак = [ац, ..., а^, ..., акх, ах2, ..., аь2, ..., &к2} - множество состояний; ац, ..., а^, ...,

&К1 - подмножество стартовых состояний; а\2, ..., ак2, ..., &к2 - подмножество поглощающих состояний; кк (£) - полумарковская матрица;

Рис. 31: Формирование потока событий в результате «соревнования» к субъектов

hK (t) =

Ы (t) 0

Vk (t) 0

vk (t) 0

Vi (t) = ... = vk (t) = ...vK (t) =v(t) =

1, when 0 ^ t ^ 1; 0 in all other cases.

/Г-параллельный процесс запускается изо всех состояний подмножества ац, ..., йк\, ..., ак1 одновременно. Событие генерируется, когда один из ординарных процессов, например к-й, достигает своего поглощающего состояния, ак\, 1 ^ к ^ К. В соответствии с теоремой Б. Григелиониса, при К ^ ж поток событий, генерируемых параллельно независимыми генераторами, стремится к пуассоновскому.

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

зависимостью

где

9к (t) =

d{ 1 - [1 -V (¿Г}

t

V (t) = J v (т) (It =|

dt

21, when 0 < t < 1; 0 in all other cases.

Для случая

К (1 - t)K-i, when 0 < t < 1; 0 in all other cases.

9k =

0

0

Математическое ожидание для (31) определяется но зависимости

1

— [time]

Л + 1 L j

0

Тк = J tK (1 - t)K-1 dt =

Экспоненциальный закон, определяющий Иуассоновский ноток событий, имеет вид:

prob

fK (t) = (K + 1) exp [— (К + 1) t]

time

Для усеченнохх) закона

Тк =

К

Нш = Нш

(К + 1)2 Тк — Тк

[time].

Нш

1

= 0,

°У Тк К +1

т.е. с увеличением К закон приближается к экспоненциальному, что соответствует теореме Б. Грш'елиониса [14], и подтверждается введенным критерием, основанном на вычислении функции ожидания.

Вид плотностей распределения приведен на рис. 3. Уже при К 8 критерий равен 11,1, что можно считать хорошим приближением к экспоненциальному закону.

К= 1

1 gl

0.5

0 0 2 0 Л 0 6 0,8 ime

К= 4

X

\ ~— --

/к, ёк

prob

time

К = 2

1

0,2 0.4 0.6 0,8 time

fx-ёк

prob

time

17.5 К= 8

5\

1 Л

ъ Чй ь=-- -

Рис. 32: Вид плотностей распределения

6. Заключение

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

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

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

Работа выполнена при финансовой поддержке Министерства образования и науки Российской Федерации на выполняемый в рамках государственного задания на проект "Параллельные полу марковские процессы в системах управления мобильными роботам и "Лъ 2.3121.2017/ПЧ.

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

1. Сундарапандиан В. Вероятность, статистика и теория массового об-служивания. - Нью-Дели. 2009.

2. Гросс Д., Харрис K.M. Основы теории очередей. Изд. Джон Вилей и сыновья, 1974.

3. Ларкин Е.В., Ивутин А.Н. Диспетчеризация во встроенных системах // 2016 5-я Средиземноморская конференция по встроенным вычислительным системам (MECO). - 12-16 июня 2016 года, Бар, Черногория - IEEE, 2016. - Стр. 215 - 217.

4. Ларкин Е., Ивутин А.Н., Есиков Д. Д. Рекурсивный подход для оценки временных интервалов между транзакциями в процедуре опроса // 8-я Между-народная конференция по компьютерной и автоматизации (ICCAE 2016). - 3-4 марта 2016 года - Мельбурн, Австралия - Сеть конференций МАТЕС, 56 (2016) 01004

5. Ларкин Е.В., Ивутин А.Н., Котов В.В., Привалов А.Н. Интерактивный генератор команд // 7-я Международная конференция ICSI-2016. Бали, Индонезия, 25-30 июня. Труды. Часть 2. Лекционные заметки в области компьютерных наук. LNCS Sublibrary: SL1 -Теоретическая информатика и общие вопросы Springer, 2016. С. 601 - 609.

6. Ларкин Е.В., Привалов А.Н. Моделирование режимов диалога управления дистанционными роботами // Труды 5-го Международного семинара по математическим моделям и их приложениям Красноярск, Россия, 7-9 ноября 2016 г. - С. 92 - 103.

7. Марков A.A. Расширение закона больших чисел на зависимые кванты, Изв. физ.-матем. Казанский унив., (2-й сер.), - 1906, С. 135-156.

8. Боос Д.Д. Стефански Л. А. Эссенциальный статистический вывод. Теория и методы. -N.Y., Springer Verlag. 2013. - 568 (XVII) Стр.

9. Драпер И.Р., Смит Н. Приложения регрессионного анализа Изд. Джон Вилей и сыновья,1998 - 736 с.

10. Рейтинг М.К. Корреляционные методы. - опубликовано Чарльзом Гриффином и Компа-ни, Лондон, - 1955. - 196 с.

11. Вентцель Е.С. Теория вероятности. - М.: Мир Издательство, 1986. 86 с.

12. Ивутин А.Н., Ларкин Е.В. Моделирование параллельных игр // Вестник ЮжноУральского государственного университета. Серия: Математи-ческое моделирование, программирование и компьютерное программное обеспечение. - Челябинск, 2015 г. - т. 8, №2. - С. 43 - 54.

13. Ларкин Е.В., Ивутин А.Н., Котов В.В., Привалов А.Н. Моделирование ретрансляций // Вестник Южно-Уральского государственного университета. Математическое моделирование, программирование и компьютерное программное обеспечение. - 2016. с. 117- 128.

14. Глушков В.М., Амосов Н.М., Артеменко И.А. Энциклопедия кибернетики. Том 2. Киев, 1974.

15. Григелионис Б. О сходимости сумм случайных ступенчатых процессов к пуассоновскому процессу. Теория вероятности, С. 177 - 182., 1963.

REFERENCES

1. Sundarapandian V. Queueing Theory: Probability, Statistics and Queueing Theory. - PHI Learning. New Delhi. 2009.

2. Gross D., Harris C.M. Fundamentals of Queue Theory. John Wiley k, Sons N.Y/ 1974..

3. Larkin E.V., Ivutin A.N. Dispatching in Embedded Systems //2016 5th Mediterranean Conference on Embedded Computing (MECO). - 12-16 June 2016, Bar, Montenegro - IEEE, 2016. - Pp. 215 - 217.

4. Larkin, E., Ivutin, A., Esikov, D. Recursive Approach for Evaluation of Time Intervals between Transactions in Polling Procedure // 8-th International Conference on Computer and Automation Engineering (ICCAE 2016). - March 3-4, 2016 - Melbourne, Australia -MATEC Web of Conferences, 56 (2016) 01004

5. Larkin E.V., Ivutin A.N., Kotov V.V., Privalov A.N. Interactive generator of commands // 7-th International Conference ICSI-2016. Bali, Indonesia, June 25 - 30. Proceedings. Part 2. Lecture Notes in Computer Science. LNCS Sublibrarv: SL1 - Theoretical Computer Science and General Issues Springer, 2016. Pp. 601 - 609.

6. Larkin E.V., Privalov A.N. Modeling of dialogue regimes of distance robot control // Proceedings of 5th International Workshop on Mathematical Models and their Applications Krasnoyarsk, Russia, November 7-9, 2016. - Pp/ 92 - 103.

7. Markov A.A. Extension of the law of large numbers to dependent quantities, Izvestiia Fiz.-Matem. Obsch. Kazan Univ., (2-nd Ser.), - 1906, - Pp. 135-156

8. Boos D.D. Stefanski L.A. Essentioal Statistical Inference. Theory and methods. - N.Y., Springer Verlag. 2013. - 568 (XVII) Pp.

9. Draper N.R., Smith H. Applied Regression Analysis 1998 by John WTilev k, sons, Inc. - 736 Pp.

10. Rank M.K. Correlation Methods. - Published by Charles Griffin k, Company, London, - 1955. - 196 Pp.

11. Ventsel E.S. Probability theory. - M.: Mir Publisher, 1986. - 86 Pp.

12. Ivutin A.N, Larkin E.V. Simulation of Concurrent Games // Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software. -Chelyabinsk, 2015. - Vol. 8, №2. - P. 43 - 54. DOI: 10.14529/mmpl50204

13. Larkin E.V., Ivutin A.N., Kotov V.V., Privalov A.N. Simulation of Relay-races // Bulletin of the South Ural State University. Mathematical Modelling, Programming k, Computer Software. - 2016. - Vol. 9. - No 4. - Pp. 117 - 128.

14. Glushkov V. M, Amosov N. M, Artemenko I. A. Encyclopedia of Cybernetics. Vol-ume 2. Kiev, 1974.

15. Grigelionis B. On the convergence of sums of random step processes to a Poisson process. Theory Probab. Appl. 1963. Pp. 177 - 182.

nojivHeno 20.02.2017 r. IlpHHaTO B nenaib 12.06.2017 r.