Оценка состояний дважды стохастических потоков событий

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ  
РОССИЙСКОЙ ФЕДЕРАЦИИ 
НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ 
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ 
 
 
 
 
 
 
Л.А. Нежельская 
 
 
ОЦЕНКА СОСТОЯНИЙ  
ДВАЖДЫ СТОХАСТИЧЕСКИХ  
ПОТОКОВ СОБЫТИЙ 
 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
Томск 
Издательство Томского государственного университета 
2020 

УКД 519.25(075.8) 
ББК 22.172я73 
         Н431 
 
Нежельская Л.А. 
Н431 Оценка состояний дважды стохастических потоков событий : учебное пособие. – Томск : Издательство Томского 
государственного университета, 2020. – 210 с. 

ISBN 978-5-94621-973-0 
 
В предлагаемом учебном пособии в систематизированном виде изложены наиболее распространённые типы дважды стохастических потоков событий, являющихся математическими моделями реальных информационных потоков сообщений в телекоммуникационных системах и сетях. Методом максимума апостериорной вероятности решены задачи по оцениванию 
состояний дважды стохастических потоков событий в условиях полной 
наблюдаемости и при наличии непродлевающегося мёртвого времени.  
В основу представленного материала положены оригинальные научные результаты автора. 
Для студентов высших учебных заведений, обучающихся по направлению «Прикладная математика и информатика» и смежным направлениям, а также для аспирантов специальности «05.13.01 – Системный анализ, 
управление и обработка информации» и широкого круга специалистов, 
занимающихся проблемами статистической обработки потоков событий с 
целью принятия оптимального решения. 
 
УКД 519.25(075.8) 
ББК 22.172я73 
 
Рецензенты: 
А.М. Кориков, доктор технических наук, профессор,  
заслуженный деятель науки РФ; 
С.Э. Воробейчиков, доктор физико-математических наук, профессор 
 
 
 
ISBN 978-5-94621-973-0 
© Нежельская Л.А., 2020 
© Томский государственный университет, 2020 

Предисловие 
 
Теория массового обслуживания (ТМО), имеющая англоязычное название queuing theory (теория очередей), возникла в начале 
20-го века и была представлена первыми работами датского инженера и математика А. К. Эрланга, связанными с решением задач в 
области телефонии – расчётом и проектированием телефонных 
сетей. Основные исследования А. К. Эрланга в этой области относятся к 1908–1922 гг. В его работах, в частности в первой статье, 
вышедшей в свет в 1909 г. [1], в качестве математической модели 
потока телефонных вызовов, поступающих на телефонную станцию, рассматривалась модель пуассоновского потока: телефонные 
вызовы носят случайный по времени характер, а длины интервалов 
между моментами их поступления имеют экспоненциальное распределение. 
К середине 20-го века к вопросам телефонного дела добавились 
разнообразные задачи ядерной физики, автоматизации и организации производства, эксплуатации аэропортов, железнодорожных 
станций, магазинов, пунктов проката и пр., что обусловило возросший интерес учёных к их решению методами ТМО. 
Основы и фундаментальные результаты по ТМО изложены в 
трудах советских учёных А. Я. Хинчина [2], Б. В. Гнеденко, 
И. Н. Коваленко [3] и др. 
Развитию ТМО, совершенствованию применяемого математического аппарата, основанного на методах теории вероятностей и 
теории случайных процессов, способствуют работы по проектированию, внедрению, эксплуатации и модернизации информационно-вычислительных систем и сетей разной конфигурации, компьютерных сетей, обладающих, как правило, ограниченным ресурсом и потоком заявок (событий, запросов) на его исследование. 

Первоначальные исследования в области компьютерных сетей 
основывались на предположениях о некоррелированном характере 
информационных потоков (пуассоновские потоки). Появление 
цифровых сетей интегрального обслуживания – ЦСИО (Integrated 
Service Digital Networks), беспроводных и мобильных сетей связи, 
предназначенных для передачи разнообразной и разнородной информации – видео, речи, больших массивов данных, послужило 
стимулом к появлению дважды стохастических потоков событий – новой математической модели, наиболее адекватно учитывающей коррелированный характер реальных информационных 
потоков в современных телекоммуникационных сетях. 
С конца 20-го века в теории очередей активно исследуются системы массового обслуживания (СМО) с коррелированными потоками. Имеется достаточное количество работ, в которых отражены 
данные исследования. 
Вместе с тем на сегодняшний момент времени упорядоченного 
и систематизированного изложения собственно теории дважды 
стохастических потоков событий и решаемых задач в современной 
литературе нет. 
Данное учебное пособие позволит отчасти восполнить этот 
пробел, предложив читателю ознакомиться с элементами теории 
дважды стохастических потоков событий. 
В списке литературы приведены отдельные статьи с оригинальными результатами автора, послужившими основой для написания 
учебного пособия. 

Глава 1 
Различные математические модели  
дважды стохастических потоков событий 
 
1.1. О дважды стохастических потоках 
 
Каждое исследование по ТМО начинается с изучения потока 
событий (запросов, заявок, сообщений, вызовов), который поступает на обслуживающий прибор, то есть с изучения входящего потока событий. До 80-х годов 20-го века основным потоком событий, исследуемым многими авторами работ по ТМО, был простейший, или стационарный, пуассоновский поток. 
Во входящем потоке события поступают в систему обслуживания в некоторые случайные моменты времени 
...
,
...,
,
, 2
1
kt
t
t
, обра
зуя случайную последовательность  
kt
.  

В дальнейшем изложении обозначение 
...
,
...,
,
, 2
1
kt
t
t
 используется применительно как к случайным величинам, так и к их значениям, различие между которыми следует из контекста. Например, наблюдаемые (измеряемые) моменты наступления событий 
есть значения случайных величин – моментов наступления событий [4]. 
На временной оси рассмотрим полуинтервал 


0
0, t
t
 дли
тельности  . Введём обозначение 


0
| t
Pk 
 – вероятность того, что 

на полуинтервале 


0
0, t
t
 длительности   с началом в точке 0t  
наступит ровно k  событий. Пусть этот поток однородных случайных событий обладает следующими тремя свойствами [2]. 
1. Стационарность. Каковы бы ни были 
0


 и целое 
0

k
, 
вероятность того, что на полуинтервале 


0
0, t
t
 наступит k  со

бытий, не зависит от местоположения 
0t  на временной оси, или 


 


k
k
P
t
P
0
|
. Стационарность потока выражает собой неизменность его вероятностного режима во времени. 
2. Ординарность. Для данного стационарного потока введём 

вероятность 
 
 







2
k
kP
 – вероятность того, что за промежуток 

времени   наступит по меньшей мере два события. Тогда 

 
0
lim
0







. 

Ординарность потока выражает собой практическую невозможность 
совмещения двух или более событий в один и тот же момент времени. 
3. Отсутствие последействия. Вероятность 
 
k
P
 наступления 

k  событий на полуинтервале 


0
0, t
t
 не зависит от чередования 

событий до момента 
0t . Отсутствие последействия выражает собой взаимную независимость поведения потока в непересекающихся между собой промежутках времени. 
Итак, простейшим потоком однородных событий называется 
всякий стационарный ординарный поток без последействия. 
Для простейшего потока число событий на полуинтервале 



0
0, t
t
 длительности   распределено по закону Пуассона с параметром  [2]: 

 







e
k
P

k

k
!
, 
...
,1
,0

k
. 

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

t
e
t
F



1
)
(
, 
0

t
. 
Определение. Интенсивностью  стационарного случайного 
потока называется математическое ожидание числа событий, 
наступивших в потоке в единицу времени: 

 
 
1

1
k
k

M
k
kP





 



 
,  
0


. 

Для простейшего потока величина  называется также параметром потока. Наличие одного только параметра предопределяет 
и недостатки стационарного пуассоновского (простейшего) потока, являющегося математической моделью реального потока. 
Появление 
компьютерных 
сетей 
послужило 
причиной 
возникновения новой математической модели потока – дважды 
стохастического потока событий, которая наиболее адекватно 
описывает реальные информационные потоки. События в потоке 
наступают в случайные моменты времени 
...
,
...,
,
, 2
1
kt
t
t
 (первая 
стохастика), интенсивность дважды стохастического потока событий является случайным процессом (вторая стохастика). Из анализа научной литературы следует, что М. Бартлетт (M. Bartlett) [5], 
Д. Кокс (D. Cox) [6] и Дж. Кингмен (J. Kingman) [7] первыми в 
своих статьях определяют дважды стохастический поток как поток 
событий с интенсивностью, представляющей собой случайный 
процесс. Названные авторы рассматривали модели дважды стохастических потоков с интенсивностью, представляющей собой непрерывный случайный процесс. 
В начале 80-х годов 20-го века, независимо друг от друга, модели дважды стохастических потоков событий, интенсивность 
которых является кусочно-постоянным случайным процессом, 
были предложены в Советском Союзе учёными Г. П. Башариным, 
В. А. Кокотушкиным, В. А. Наумовым [8, 9] и названы MCпотоками (Markov Chain), а в США – научным коллективом 
М. Ньютса (M. Neuts) [10]. Название этих потоков в США эволюционировало от MVP (Markov Versatile Process) [10] – «разносторонних потоков» до MAP (Markovian Arrival Process) [11] – 
марковских входящих потоков и их обобщений BMAP (Batch 
Markovian Arrival Process) – групповых марковских входящих 
потоков. 

Зарубежными и отечественными авторами работ при описании 
подобных входящих потоков событий в СМО используются термины: дважды стохастические потоки событий, MC-потоки, MAPпотоки. 
Дважды стохастический поток событий – коррелированный поток, так как обладает свойствами стационарности и ординарности, однако является потоком с последействием. В дальнейшем 
изложении рассматриваются различные модели дважды стохастических потоков событий, для которых вводится понятие сопровождающего случайного процесса 
)
(t

, являющегося кусочнопостоянным ненаблюдаемым случайным процессом с двумя состояниями. Первичными являются события потока, на основании 
которых строится математическая модель процесса 
)
(t

. В этой 
связи случайный процесс 
)
(t

 является сопровождающим (порождён потоком). Для отдельных моделей потоков сопровождающий 
случайный процесс 
)
(t

 имеет смысл интенсивности потока. 
Все исследуемые дважды стохастические потоки событий функционируют в стационарном режиме, поэтому переходными процессами на интервале наблюдения 
t
t ,
0
, где 
0t  – момент начала 
наблюдения, t  – момент окончания наблюдения, пренебрегаем. 
 
1.2. Асинхронный (MMPP – Markovian Modulated  
Poisson Process) поток 
 
Рассматривается поток событий, сопровождающий случайный 
процесс которого 
)
(t

 является кусочно-постоянным с двумя со
стояниями 
1S  и 
2
S ; если 
i
t


 )
(
, то имеет место i -е состояние 

(
iS ) процесса 
)
(t

, 
2
,1

i
, 
0
2
1




. Длительность пребывания 
процесса 
)
(t

 в i -м состоянии есть случайная величина с функци
ей распределения 
t
i
i
e
t
F



1
)
(
, 
0

t
, 
2
,1

i
. Если процесс 
)
(t

 

находится в состоянии 
1S , то в течение времени пребывания его в 

состоянии 
1S  имеет место пуассоновский поток событий с пара
метром 
1
 ; если в состоянии 
2
S , то имеет место пуассоновский 

поток с параметром 
2
 . 
Подчеркнём, что в асинхронном потоке событий переход процесса 
)
(t

 из состояния в состояние осуществляется в произвольный момент времени, не связанный с моментом наступления события; поэтому поток событий называется асинхронным [12]. 
Вариант возможного поведения случайного процесса 
)
(t

 и 

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

2
S  – состояния процесса 
)
(t

; 
...
,
...,
,
, 2
1
kt
t
t
 – моменты наступления событий в асинхронном потоке. 
 

t5
t3
t1

...

t6

α2

t
t2

t

t4
t7

Процесс λ(t)

...

...

S1

S2

...

...

α1
α1
α2
α2
α1

 

Рис. 1.1. Формирование асинхронного потока событий 
 
Лемма 1.1. Сопровождающий кусочно-постоянный случайный 
процесс 
)
(t

 для асинхронного потока является марковским. 

Доказательство. Пусть в момент времени t~ процесс 
)
(t

 
находится в первом состоянии, то есть значение процесса 

1
)
~
(


 t
. Длительность пребывания процесса 
)
(t

 в первом состоянии является случайной величиной с функцией распределения 

t
e
t
F
1
1
)
(
1




, 
0

t
. Поскольку экспоненциальное распределение 
обладает свойством отсутствия последействия, то оставшаяся после момента времени t~ часть длительности пребывания процесса 

)
(t

 в первом состоянии не зависит от того, как долго он в этом 
состоянии уже находился, а момент перехода процесса 
)
(t

 во 

второе состояние после t~ определяется моментом окончания длительности пребывания процесса 
)
(t

 в первом состоянии. Аналогичная ситуация имеет место для второго состояния процесса 
)
(t

. 
В силу этого процесс 
)
(t

 марковский. Лемма доказана. 
Процесс 
)
(t

 является принципиально ненаблюдаемым (скры
тый марковский процесс); наблюдаемыми на интервале 
t
t ,
0
 

являются только моменты времени 
...
,
...,
,
, 2
1
kt
t
t
 наступления 
событий. 
Лемма 1.2. Последовательность 
)
( kt

, образуемая совокупно
стью моментов наступления событий 
...
,
...,
,
, 2
1
kt
t
t
, является вложенной цепью Маркова. 
Доказательство. Асинхронный поток событий в условиях стационарного режима функционирования является стационарным 
ординарным потоком с последействием; в противном случае он 
являлся бы простейшим потоком. Поведение потока после момента kt  наступления события не зависит от предыстории, а опреде
ляется состоянием 
iS , 
2
,1

i
, процесса 
)
(t

 в момент времени kt . 
Действительно: 
1. В момент времени 
kt , 
...
,2
,1

k
, значение процесса 

i
kt



)
(
, то есть имеет место состояние 
iS , 
2
,1

i
, процесса 
)
(t

, длительность пребывания в котором является случайной величиной, 
распределённой 
по 
экспоненциальному 
закону 

t
i
i
e
t
F



1
)
(
, 
0

t
, 
2
,1

i
. Следовательно, оставшаяся часть 

длительности пребывания процесса 
)
(t

 в состоянии 
iS , 
2
,1

i
, 

после момента kt  не зависит от того, как долго процесс 
)
(t

 нахо
дился в этом состоянии до момента времени kt , 
...
,2
,1

k
.