Совместная плотность вероятностей длительности интервалов обобщенного полусинхронного потока

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

2012 Управление, вычислительная техника и информатика № 2

УДК 519.21

А.М. Горцев, А.А. Калягин

СОВМЕСТНАЯ ПЛОТНОСТЬ ВЕРОЯТНОСТЕЙ ДЛИТЕЛЬНОСТИ ИНТЕРВАЛОВ ОБОБЩЕННОГО ПОЛУСИНХРОННОГО ПОТОКА

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

Ключевые слова: обобщенный полусинхронный поток событий, плотность вероятностей, совместная плотность вероятностей, рекуррентность потока событий.

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

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

1. Постановка задачи

Рассматривается обобщенный полусинхронный поток событий, интенсивность которого есть кусочно-постоянный случайный процесс X(t) с двумя состояниями X и X2 (X > X2). В течение временного интервала, когда X(t) = X , имеет место пу-ассоновский поток событий с интенсивностью X , i = 1,2. Переход из первого состояния процесса X(t) во второе возможен только в момент наступления события, при этом переход осуществляется с вероятностью p (0 < p < 1); с вероятностью 1 -p процесс X(t) остается в первом состоянии. Тогда длительность пребывания про-

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

А =

-X! 0 (1 - р)Х[ Рх 1

(1 -8) а -(X 2 + а) 8а Х 2

Элементами матрицы Б1 являются интенсивности переходов процесса Х(г) из состояния в состояние с наступлением события. Недиагональные элементы матрицы О0 - интенсивности переходов из состояния в состояние без наступления события. Диагональные элементы матрицы О0 - интенсивности выхода процесса Х(г) из своих состояний, взятые с противоположенным знаком. В сделанных предположениях Х(г) - марковский процесс. Вариант возникающей ситуации приведен на рис. 1, где 1,2 - состояния случайного процесса Х(г); г1 , г2 ,... - моменты наступления событий; г4 ,... - моменты инициирования дополнительных событий с вероятностью 5. Если 5 = 0, то имеет место обычный полусинхронный поток событий [4].

1 - р

—6-

t

1 - р

1 - р

1 *2 *3 *4 *5 *6 *7 *8 *9 *10

Рис. 1. Формирование обобщенного полусинхронного потока

2

*

Процесс Х(г) и типы событий (события пуассоновских потоков и дополнительные события) являются принципиально ненаблюдаемыми, а наблюдаемыми являются только временные моменты наступления событий г1 , г2 ,. . Рассматривается установившийся (стационарный) режим функционирования потока событий. В силу предпосылок последовательность моментов наступления событий г1 , г2 ,., 4 , ... образует вложенную цепь Маркова, т.е. обобщенный полусинхронный поток обладает марковским свойством, если его эволюцию рассматривать с момента 4 (момент наступления события), к = 1, 2, ... . Обозначим тк = 4+1 - 4 (к = 1, 2, .) - значение длительности к-го интервала между соседними событиями потока. Так как рассматривается стационарный режим, то плотность вероятностей значений длительности к-го интервала р(тк) = рт), т > 0, для любого к. В силу этого момент 4 без потери общности можно положить равным нулю, или, что то же самое, мо-

мент наступления события есть т = 0. Пусть теперь (4 , гк+1), (гк+1 , 4+2) - два смежных интервала с соответствующими значениями длительностей: тк = 4+1 - & , тк+1 = 4+2 - 4+ь их расположение на временной оси, в силу стационарности потока, произвольно. Тогда можно положить к = 1 и рассматривать соседние интервалы (г1, г2), (г2, г3) с соответствующими значениями длительностей: т1 = г2 - г1 , т2 = г3 - г2 ; т1 > 0, т2 > 0. При этом т1 = 0 соответствует моменту г1 наступления события потока; т2 = 0 - моменту г2 наступления следующего события потока. Соответствующая совместная плотность вероятностей при этом есть р(т1 , т2), т1 > 0, т2 > 0.

Задача заключается в нахождении явного вида р(т) и явного вида _р(т1,т2), а также в установлении условий рекуррентности обобщенного полусинхронного потока событий.

2. Вывод плотности вероятностей р

Введем в рассмотрение вероятности р. (т) того, что на интервале (0, т) нет событий потока и в момент времени т имеет место Х(т) = Х/ при условии, что в момент времени т = 0 значение процесса Х(0) = Х, (г, у = 1,2). При этом, в силу предпосылок, р12 (т) = 0 для любого т. Тогда, в соответствии с определением потока, ^11(т)Х1Ат(1- р) + о(Дт) - совместная вероятность перехода на интервале (0, т) процесса Х(т) из первого состояния в первое, наступления события потока на полуинтервале [т. т + Ат), где Ат - достаточно малая величина, и перехода на этом полуинтервале процесса Х(т) из первого состояния в первое. Аналогичные совместные вероятности примут вид

^11(т)Х1Ат^ + о(Дт); _р22(т)Х2Дт + о(Дт); _р22(т)аДт5 + о(Дт); _р21(т)Х1Дт(1-р) + о(Дт); _р21(т)Х1Дт^ + о(Дт).

Соответствующие плотности вероятностей выпишутся в виде

Ри

Р21 (т) = (1 - Р)\Р2\(т) + а8Р22 (т); Р22 (т) = Р^1Р21(т) + ^2^22 (т)-Составляя дифференциальные уравнения относительно неизвестных р. (т), г, у = 1,2 , (р12 (т) = 0) и решая полученные уравнения с соответствующими граничными условиями: _р11(0) = _р22(0) = 1, _р21(0) = 0, находим

А1

А<1 ^2 а

Подставляя (2) в (1), получаем явный вид плотностей вероятностей р. (т), г, У = 1,2.

Введем в рассмотрение вероятность л,(0) - условную стационарную вероятность того, что процесс Х(т) в момент времени т = 0 находится в г -м состоянии при условии, что в момент т = 0 событие потока наступило, г = 1,2 (п1(0) + п2(0) = 1). Тогда, так как моменты наступления событий образуют вложенную цепь Маркова, справедливы следующие уравнения для вероятностей лг(0):

П1

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

p i = Ihi(T)d т =(1 - р)\ |Pi i(T)d т; Ри = {Pu(T)d T = px i {Pi i(T)d T;

0 0 0 0

_P2i = { p 2i

0 0 0

го ro ro

_P22 = { P 22 (T)d T = Mi I P2i(T)d T + X2 | P22 (T)^ T,

0 0 0

где p g (т) определены в (1), pj (т) - в (2). Подставляя (2) в (4), находим

Р11 = 1 -p;P12 = p; P21 = a(1 -p + j?5)/(a + ^2); ^22 = [^2 + Ml - 5)]/(a + ^2). (5) Подставляя (5) в (3), получаем

ni

Тогда плотность вероятностей p(T) примет вид

2 2

ж»=Z п

i=1 j=1

Подставляя в (7) сначала (1), затем (2) и (6), проделывая при этом необходимые преобразования, получаем явный вид плотности вероятностей _p(x):

p(т) = ykle^Xl% + (1 -у)(a +A,2)e-(a+X2^т, т - 0;

рХх

a

Y ='

1 --

a + р(Х 2 + aS) где ^1 - А2 - a Ф 0. Для случая ^1 - А2 - a = 0 имеем

^а

1 —

Х<2 a

м

ее, т > 0.

Отметим, что если 5 = 0, то получаем (8) и (9) для обычного полусинхронного потока [4].

3. Вывод совместной плотности вероятностей р

В силу того, что последовательность моментов наступления событий потока образует вложенную цепь Маркова, совместная плотность вероятностей _р(т1,т2) примет вид

2 2 2

Т2 ) = X П

/=1 _/=1 к=1

где р (т;), р (т2) определены в (1). При этом в выражениях для р (т), г,у = 1,2,

нужно произвести замену т на т1 и т на т2. Тогда подставляя в (10) сначала р (т;),

Рц (т2), определенные в (1), затем р..(т;), р у (т2), определенные в (2), для т =т1 и

т = т2, затем л;(0), определенные в (6), г, у = 1,2, и проделывая необходимые преобразования, находим

Ж , т2 ) = Ж1)Р(т2 ) +

Х2 - (X2 + а8)р а + Х2

у

где ^(т1), рт2), у определены в (В) для т =т1 и т = т2 и Х1 - Х2 - а Ф 0. Для случая Х1 - Х2 - а = 0 имеем

Р(ті, т2 ) = Р(ті) Р(т 2 ) + xi [а(1 - Р + Р5) -\(1 - P)]x

pa

a(1 - p) + p( X1 + a 8) _

где _р(Хі), _р(х2) определены формулой (9) для Х =Х1 и т = т2.

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

1. Вариант Х1 - Х2 - а Ф 0:

12

1-Y

Х-1 а + Л<2

1-Y

_LT_____________

Y_ + _1-Y

Xi a + 'K')

cov

2 X2 -

2. Вариант X1 - X2 - a = 0:

MT = (1 + C)/, DT = (1 + 2C-C2)/X?,

cov(t1,t2) = C2 [a(1 -p + bp)-Xj(1 -p)]/Xj,

C = pa{\-8) [a(1 - p) + p(X1 +a8) ] 1.

В рассматриваемом потоке присутствуют события трех типов:1) события пуас-соновского потока интенсивности Х1; 2) события пуассоновского потока интенсивности Х2; 3) дополнительные события. Типы событий являются неразличимыми. Обозначим qj - стационарные вероятности того, что наступившее событие потока есть событие j-го типа, j = 1,2,3. Тогда, используя вышеприведенные результаты, нетрудно получить явные выражения для qj :

a pX2 pad

а + (A 2 +а8) p

92 =

a + (A 2 + a8) p

9з =

a + (X2 +a8) p

Отметим, что п1(0) = д1(1 - р)+ д3 , п2(0) = ц1р+ д2 . Полагая в (11), (12) 5 = 0, получаем формулы _р(т1,т2) для обычного полусинхронного потока [4].

4. Условия рекуррентности обобщенного полусинхронного потока событий

Рассмотрим частные случаи, при которых обобщенный полусинхронный поток становится рекуррентным.

1. Вариант Х1 - Х2 - а Ф 0. Тогда для ситуаций: а) у = 1 (данное условие реализуется, если Х1 - Х2 - а5 = 0); б) у = 0 (данное условие реализуется, если Х1(1 - р + р5) - Х2 - а = 0); в) Х2 - (Х2 + а5)р = 0; г) р = 1, 5 = 0, совместная плотность (11) факторизуется. Так как последовательность моментов наступления событий есть вложенная цепь Маркова, то нетрудно показать, что факторизуется и совместная плотность рть...,тк). Последнее означает, что для этих ситуаций

обобщенный полусинхронный поток является рекуррентным [5]. При этом из (8) вытекает, что:

для ситуации а)

р(т) = 'kle~Xl%, т > 0, А1 = А2 + a5;

для ситуации б)

р(т) = (а + Х2)е-(а+Л2)т, т > 0, a + А2 = А1 (1 -p + pS);

для ситуации в)

р(т) = y1A1e-XlT + (1 -y1 )(а + X2 )e-a+x> ^т, т > 0, a + А2 = a(1 -p - Sp)/(1 -p),

Y1 = (1 -P (^1 - a -p^1>[(1 -p)( ^1 - a) - a5p]-1 ;

для ситуации г)

Р(т) = Y2 V"V +(1 - Y2 )(a + x2 )e~(a+Xl}T, Y2 = -a /(^ -A2 - a).

2. Вариант A1 - A2 - a = 0. Тогда для ситуаций: а) 5 = 1; б) p = 1, 5 = 0; в) a(1 - p + p5) = A1(1 - p), p Ф 1, совместная плотность (12) факторизуется. Последнее означает, аналогично варианту 1, что факторизуется и совместная плотность рть...,тк), так что для перечисленных ситуаций поток является рекуррентным. При этом из (9) вытекает, что:

для ситуации а) р(т) = Xle—"1%, т > 0, А1 = a + А2;

для ситуации б)р(т) = (Xt - a + XlaT)e~XlZ, т > 0, А1 = a + А2;

для ситуации в) р(т) = [ - ap(1 - 8)(1 - А1х)] е-Л'т, т > 0, А1 = a + А2.

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

1. Вариант 1 (А1 - А2 - a Ф 0):

1.а. Апостериорная вероятность w(A1 | t) первого состояния процесса A(t) (не смотря на то, что поток рекуррентный и плотность р(т) экспоненциальная) зависит от предыстории, т.е. зависит от моментов наступления событий t1, ..., tk . Если здесь ввести дополнительное ограничение А2 = pX1 (p Ф 1), то вероятность w(A1 | t) не будет зависеть от предыстории, а будет зависеть только от её значения в момент наступления события потока, т.е. от w(A1 | tk + 0) = 1 -p, к = 1, 2, ...; так что при дополнительном ограничении имеется некоторая близость обобщенного по-лусинхронного потока к простейшему потоку.

1.б. Вероятность w(A1 | t) = п1 , t > 0, где п1 = a/(a + pX1) - априорная стационарная вероятность первого состояния процесса A(t). То есть для этой ситуации апостериорная вероятность w(A1 | t) вообще не зависит от моментов наступления событий, так что здесь имеет место наибольшая близость обобщенного полусин-хронного потока к простейшему потоку.

1.в. Вероятность w(A1 | t) не зависит от предыстории, а зависит только от её значения в момент наступления события, т.е. от w(A1 | tk + 0) = 1 -p, к = 1, 2, ... , так что для этой ситуации, аналогично ситуации а), имеется некоторая близость обобщенного полусинхронного потока к простейшему потоку.

1.г. Вероятность w(A1 | t) не зависит от предыстории, а зависит только от её значения в момент наступления события, т.е. от w(A1 | tk + 0) = 0, к = 1, 2, ... , так что и для этой ситуации обобщенный полусинхронный поток в некоторой степени близок к простейшему потоку.

2. Вариант 2 (А1 - Х2 - a = 0):

2.а. Вероятность w(A1 | t) = п1 , t > 0. То есть для этой ситуации апостериорная вероятность w(A1 | t) вообще не зависит от моментов наступления событий и обобщенный полусинхронный поток наиболее близок к простейшему потоку.

2.б. Вероятность w(A1 | t) не зависит от предыстории, а зависит только от её значения в момент наступления события, т.е. от w(A1 | tk + 0) = 0, к = 1, 2, ... , так что для этой ситуации наблюдается некоторая близость обобщенного полусин-хронного потока к простейшему потоку.

2.в. Вероятность w(A1 | t) не зависит от предыстории, как и для ситуации 2.б., при этом w(A1 | tk + 0) = 1 -p, к = 1, 2, ... . При этом имеется некоторая близость обобщенного полусинхронного потока к простейшему потоку.

Заключение

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

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

ЛИТЕРАТУРА

1. Горцев А.М., Калягин А.А., Нежельская Л.А. Оптимальная оценка состояний обобщенного полусинхронного потока событий // Вестник ТГУ. Управление, вычислительная техника и информатика. 2010. № 2(11). С. 66-81.

2. Горцев А.М., Калягин А.А. Оптимальная оценка состояний обобщенного полусинхронного потока событий в условиях непродлевающегося мертвого времени // Вестник ТГУ. Управление, вычислительная техника и информатика. 2010. № 4(13). С. 50-60.

3. Дудин А.Н., Клименок В.И. Системы массового обслуживания с коррелированными потоками. Минск: Изд-во БГУ, 2000. 175 с.

4. Горцев А.М., Нежельская Л.А. Полусинхронный дважды стохастический поток событий при продлевающемся мертвом времени // Вычислительные технологии. 2008. Т. 13. № 1. С. 31-41.

5. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания. М.: Высшая школа, 1982. 256 с.

Горцев Александр Михайлович Калягин Алексей Андреевич Томский государственный университет

E-mail: amg@tsu.fpmk.ru redall@inbox.ru Поступила в редакцию 26 декабря 2011 г.

Gortsev Alexander M., Kalyagin Aleksey A. (Tomsk State University). The joint probability density of duration of the intervals in a generalized semi-synchronous flow.

Keywords: generalized semi-synchronous flow of events, probability density, joint probability density, recurrence of the event flow.

Generalized semi-synchronous flow of events which intensity is piecewise constant stochastic process X(t) with two values Xj and X (Xj > X2) is considered. During the time interval when X(t) = X, , Poisson flow of events takes place with the intensity X, , i = 1,2. Transition from the first state of the process X(t) into the second is possible only at the moment of event occurrence, thus, the transition is carried out with probability p (0 < p < 1); with probability 1 - p process X(t) remains in the first state. In this case the duration of process stay X(t) in the first state is a random variable

with exponential distribution function F1

from the second state into the first one an additional event in the first state is initiated with probability 8 (0 < 8 < 1).

We find the explicit form of the probability density p(i) of duration of the interval between two successive events in generalized semi-synchronous flow and the explicit form of p(Tj,x2) -the joint probability density of the length of two adjacent intervals. The conditions for the recurrence of generalized semi-synchronous flow of events are given.