Maximum likelihood estimation of dead time value at a generalized asynchronous flow of events.pdf Настоящая статья является непосредственным продолжением исследований обобщенного асинхронного потока событий (далее - поток), начатых в статьях [1-4]. Изучаемый поток относится к классу дважды стохастических потоков событий и является одной из адекватных математических моделей информационных потоков сообщений, функционирующих в ЦСИО [5]. Подчеркнем, что в последнее время дважды стохастические потоки используют при построении моделей входящих потоков - клиентов в страховых компаниях и банках [6]. Дважды стохастические потоки делятся на два класса: к первому классу относятся потоки, интенсивность которых есть непрерывный случайный процесс; ко второму классу относятся потоки, интенсивность которых есть кусочно-постоянный случайный процесс с конечным числом состояний. Второй класс потоков в настоящее время принято называть МС-потоками либо МАР-потоками событий. В [7] приведена классификация МС-потоков событий и установлена связь между МС-потоками и МАР-потоками событий. Наиболее полная литература по изучаемым типам МС-потоков приведена в [8]. В реальных ситуациях параметры, задающие входящий поток событий, известны либо частично, либо вообще неизвестны, либо (что ещё более ухудшает ситуацию) изменяются со временем. В подобных ситуациях наиболее рациональным является применение адаптивных систем массового обслуживания, которые в процессе функционирования оценивают неизвестные параметры либо состояния входящих потоков событий и изменяют дисциплины обслуживания в соответствии с полученными оценками [9]. Вследствие этого возникают задачи: 1) оценки состояний потока (задача фильтрации интенсивности потока) по наблюдениям за моментами наступления событий [10, 11]; 2) оценки параметров потока по наблюдениям за моментами наступления событий [12]. Одним из искажающих факторов при оценке состояний и параметров потока событий выступает мертвое время регистрирующих приборов [13], которое порождается зарегистрированным событием. Другие же события, наступившие в течение периода мертвого времени, не продляют его периода и недоступны наблюдению (теряются). Можно считать, что этот период продолжается некоторое фиксированное время (непродлевающееся мертвое время). Подобные ситуации возникают в компьютерных сетях, например, при использовании протокола случайного множественного доступа с обнаружением конфликта (протокол CSMA/CD). Для того чтобы оценить потери сообщений потока, возникающие из-за эффекта мертвого времени, необходимо оценить его длительность. В настоящей статье для решения задачи оценивания длительности мертвого времени применяется метод максимального правдоподобия [14], так как оценки, построенные на основе этого метода, как правило, обладают привлекательными свойствами. 1. Постановка задачи Рассматривается обобщенный асинхронный дважды стохастический поток событий, интенсивность которого есть кусочно-постоянный случайный процесс X(t) с двумя состояниями X1 и X2 (Х1> X2). В течение временного интервала, когда X(t) = Xt, имеет место пуассоновский поток событий с интенсивностью X,, i=1,2. Переход из первого состояния процесса X(t) во второе (из второго в первое) может осуществляться в произвольный момент времени. При этом длительность пребывания процесса X(t) в i-ом состоянии распределена по экспоненцильному закону с параметром а; , i=1,2. При переходе процесса X(t) из первого состояния во второе инициируется с вероятностью p (0< p 0). Доказательство. Так как тт - любое неотрицательное число (тт > 0), то p'o (тт) можно рассматривать как функцию переменной тт. Подставляя T = 0 в (3), получаем p0 (Tm) = C [z2(C _ az1 )e~z2V _ z1(C _ az2 )e"z1Tm ]/a2(z2 _ z1), C = Xj2 a2 + pqaJa2(aJ +a2) + (p + q)(X1 + X2)a1a2. (4) Рассмотрим (на предмет существования корней) уравнение p'0 (тт) = 0, которое, с учетом (4), преобразуется к виду B = e-(z2_21)тт, b = _(1/4X)(z1zJz2)2, z+ = b + (a1 +a2 _X2 + a1 _a2)2 + 4a1a2(1 _ p)(1 _q), b = (X1 _ X2 )(a1 _ a2) + (a1 + a2 )2 _ 2(p + q)a1a2. (5) В (5) знак B определяется знаком X. Так как X > 0, то B < 0, и поэтому уравнение (5) корней не имеет. Производная [p'0 (тт)]' функции (4) по переменной тт примет вид [p0 (Тт)]= C[z2(C _ az2)e-гЛт _ z22 (C _ a^ )e"гЛт ]/a2 (z2 _ z). (6) Рассмотрим (на предмет существования экстремума функции p'0 (тт)) уравнение [p'0 (тт)]' = 0, которое, с учетом (6), преобразуется к виду e4 z2 _ "1)хт = (z1/ z2) B, (7) где B определена в (5). Так как для рассматриваемого случая (X > 0) имеет место B < 0, то уравнение (7) решения не имеет, т. е. функцияpc^v) - безэкстремальная. Кроме того, из (4) следует p'0(0) = (C/a)2, p'0(®) = lirn p'0 (тт) = 0 при тт ^ Тогда p'o (тт) - убывающая функция переменной тт (тт > 0), не имеющая нулей. Лемма 1 доказана. Лемма 2. Производная p^v) - неотрицательная функция переменной тт при X < 0, b > 0 (p^v) > 0). Доказательство. Так как X < 0, то в (5) B > 0. Величина B в (5) представима в виде B = (Уz2 )2 (z+/z_),_ z_=b _(a1 + a2)^/(X1 _X2 + a1 _a2)2 + 4a1a2(1 _p)(1 _q), (8) где b определена в (5). Тогда B > 1 и уравнение (5) корней не имеет. 1) Если величина (z1 + z2)C > az1z2 , то (z1 / z2)B > 1, и поэтому уравнение (7) корней не имеет. Тогда p^v) убывает от (C/a)2 до нуля (тт ^ ®) и при этом не имеет корней, т. е. в этом случае p^v) - неотрицательная функция (тт > 0). 2) Если величина (z1 + z2)C < az1z2 , то (z1 / z2)B < 1, и тогда уравнение (7) имеет единственный корень т0 = - [1/(z2 - z1)] ln[(z1 / z2)B]. При этом в точке т0 реализуется единственный максимум функции p'0(v). Тогда производная p 0(тт) сначала возрастает от p'0(0) = (C/a)2 до p'0(T0), затем убывает до нуля (тт ^ ®), так что и во втором случае p'oCcm) - неотрицательная функция (тт > 0). Лемма 2 доказана. Лемма 3. Неравенства X < 0, b < 0 несовместны. Доказательство. Обозначим x = X1 _X2, x1 = [1/(a2 _a1)] |^(a-1 +a2 )2 _ 2(p + q)a1a2 ] . Если b < 0, то а1 < а2, x1 > 0 и x > x1. Если X < 0, то имеет место либо а) А1 + pа1 - Х 2 - qа 2 < 0 , А1 + qа1 - Х 2 - pа 2 > 0 , либо б) А1 + pа1 - Х 2 - qа 2 > 0, А1 + qа1 - Х2 - pа2 < 0 . Пусть выполняется а). Тогда p < q и pa2 - qa1 < x < qa2 -- pa1 (qa2>pa1). Обозначим x2=qa2 - pa1 (x2>0). Тогда x2 - x1 = -[[(а2 -а1 )]|(1 - p)а^ +(1 - q)а2 +а1а2 (2 - p - q)- < 0 . Таким образом, x2 < x1 и неравенства X < 0, b < 0 несовместны. Аналогично доказывается случай б). Тем самым лемма 3 доказана. Лемма 4. Производная p'T (v) при T = v (v > 0) строго больше нуля (p'^m) > 0). Доказательство. Подставляя T = v в (3), получаем {С+Хш2(т) Г(Х1 +Х2) z1z2 +(z1 + z7)(a-z^e4^2^ —(a1+a2)Tm } p'(Tm)^-m Г 1 212 ( ) 12---L,Tm >0, (9) (а1 +а2 ) где z1, z2, а, X, у (v) определены в (1). Рассмотрим (9) как функцию v . Имеем p'(0) = (С/а)2 , p'(®) = С/(а1 + а2). Знак разности p'(0) - p'(®) = XC / (а1 + а2) а2 определяется знаком X: если X > 0, то p'(0) > p'(®); если X < 0, то p'(0) < p'(®). Исследуем производную p''Ctm) функции p'(тm). Производная p"(v), с учетом (9), примет вид p"(Tm) = -Х^3(т m) У (Oe^1+^4 y(Tm) = (Х1 +Х2)z1z2 -(Х1 +Х2 + 2а1 + 2а2)(А1А2 -pqa1a2)e4a1 +а2)тт, Tm > 0. Функция у (v) > 0 при любых значениях (X1X2 - pqa1a 2) Ф 0, так что знак p''(f) определяется знаками X и y(v). Пусть X > 0: 1.1) (X1X2 - pqa1a 2) < 0. Тогда yCrm) > 0, так что p''Ctm) < 0. Отсюда следует, что p'Ccm) убывает от p'(0) до p'(®), оставаясь при этом строго больше нуля (p'Crm) > 0); 1.2) (X1X2 - pqa1a 2) > 0, С > (а1+а2)(X1X2 -pqа1а2). Тогда yCtm) > 0, причем y(тm) = 0 возможно только в точке v = 0 при выполнении равенства С = (а^аг)^^ - pqа1а2), так что p''Ccm) < 0. Результат идентичен результату предыдущего пункта; 1.3) (X1X2 - pqa1a2) > 0, С < (а^аг)^^ - pqа1а2). Тогда y(v) < 0, 0 < V < т0; y(Tm) = 0, V = т0; y(Tm) > 0, V > т0 , где 1 (а1 +а2) l { (Х1 + Х2)[а + (Х1Х2 -pqa1a2)] (Х1 + Х2 + 2а1 + 2а2)(Х1Х2 - pqa1a2) В точке т0 достигается единственный максимум функции p'Ccm). Тогда p'Ccm) > 0. Пусть X < 0: 2.1) (X1X2 - pqa1a 2) < 0. Тогда yCrm) > 0, так что p'^v) > 0. Отсюда следует, что p'Ccm) возрастает от p'(0) до p'(®), поэтому p'(тm) > 0; 2.2) (X1X2 -pqa1a2) > 0, С > (а^аг)^^ - pqа1а2). Тогда y(тm) > 0, так что p''(тm) > 0. Выполнение равенства yCcm) = 0 аналогично пункту 1.2. Результат идентичен результату предыдущего пункта; 2.3) (X1X2 - pqa1a2) > 0, С < (а^аг)^^ - pqа1а2). Тогда поведение y(v) идентично поведению y(тm) в пункте 1.3. В точке т0 при этом имеет место единственный минимум функции p'Ccm), причем p'Cco) > 0, и тогда p'Ccm) > 0. Суммируя результаты пунктов 1.1-1.3, 2.1-2.3, получаем утверждение леммы 4. Изучим поведение производной p^v) как функции T на отрезке [0, v]. Рассмотрим (на предмет существования корней) уравнение p'T (v) = 0, которое, с учетом (3), приводится к виду e^2 _z1)T = 0; 2) для X > 0, (X1X2 - pqa1a2) < 0 существуют совместные системы ограничений: а) (a1+a2 - z1) > 0, (a1+a2 - z2) < 0, p1 > 0; б) (a1+a2 - z1) > 0, (a1+a2 - z2) > 0, p1 > 0, 0 < P2 < 1; 3) для X < 0, b > 0, (X1X2- pqa1a2) < 0 существует совместная система ограничений: (a1+a2 - z1) > 0, (a1+a2 - z2) > 0, p1 > 0, p2 > 0; 4) для X < 0, b > 0, (X1X2 - pqa1a2) > 0 существуют совместные системы ограничений: а) (a1+a2 - z1) > 0, (a1+a2 - z2) > 0; б) (a1+a2 - z1) < 0, (a1+a2 - z2) > 0, 0 < p1 < 1; в) (a1+a2 - z1) > 0, (a1+a2 - z2) < 0, 0 < p2 < 1; г) (a1+a2 - z1) < 0, (a1 + a2 - z2) < 0, 0 < p1 < 1, 0 < p2 < 1, при которых имеют место реализуемые варианты поведения функций F1(T) и F2(T) и при которых F1(T), F2(T) не имеют нулей (T > 0). Таким образом, функция ф(7), определенная в (10), не имеет нулей и особых точек. Лемма 5. Уравнение (10) либо не имеет корней, либо имеет один корень, либо - два корня. Доказательство. Рассмотрим уравнение (10), которое преобразуется к виду (b1 _a1u)v2 +(b2 _a2u)v + (b3 _a3u) = 0, v = e4a1 +a2)T, u = e_(z2_z1)T, 0 < T 0 уравнение (10) корней не имеет. Доказательство. Из (11) следует ф(0) < 0. Пусть (X1X2 - pqa1a2) > 0, тогда из (11) вытекает ф'(0) < 0, то есть в точке T* реализуется минимум функции ф(7), и тогда ф(7) < 0, T > 0. Пусть (X1X2 -pqa1a2) < 0, тогда из (11) вытекает ф'(0) > 0, т.е. в точке T* реализуется максимум функции ф^. В силу пунктов 1, 2 утверждения, ф(7) нулей не имеет, поэтому ф(7) < 0, T > 0. С учетом леммы 5, лемма 6 доказана. Лемма 7. При X < 0, (X1X2 - pqa1a2) < 0, b > 0 уравнение (10) корней не имеет. Доказательство. Ограничения леммы 7 соответствуют пункту 3 утверждения. Из (5), (11) следует ф(0) > 0, ф'(0) < 0, т. е. в точке T* реализуется минимум функции ф(7). Тогда, в силу пункта 3 утверждения, ф(T) > 0, T > 0. Из (5) вытекает B > 0, из (8) следует B > 1. Тогда учитывая (11), получаем ф(0) < 1, и (с учетом леммы 5) получаем утверждение леммы 7. Лемма 8. При X < 0, (X1X2 - pqa1a2) > 0, b > 0 уравнение (10) корней не имеет. Доказательство. Ограничения леммы 8 соответствуют пункту 4 утверждения. Рассмотрим вариант а). Из (5), (11) следует ф(0) > 0, ф'(0) > 0, так что в точке T* реализуется максимум функции ф(7). Тогда, в силу пункта 4 утверждения, ф(7) > 0, T > 0. Из (5) вытекает B > 0, из (8) следует B > 1. Тогда ф(0) < 1, и уравнение (10) (с учетом леммы 5) корней не имеет. Аналогичный результат устанавливается для вариантов б), в), г). Лемма 8 доказана. Лемма 9. При X > 0, производная p'T (v) - положительная функция переменной T, 0 < T < V , 0 < V < ® (p'T(V) > 0). Доказывается последовательным применением лемм 1, 4, 6. Лемма 10. При X < 0, b > 0 производная p'T (v) - положительная функция переменной T, 0 < T < v , 0 < v < ® (p'T (v) > 0). Доказывается последовательным применением лемм 2, 4, 7, 8. Леммы 9, 10 позволяют сформулировать и доказать следующие теоремы. Теорема 1. При: 1) X > 0, 0 < v < да; 2) X < 0, b > 0, 0 < v < да, функцияpT(v) -возрастающая функция переменной T, 0 < T < v . Доказывается для варианта 1 применением леммы 9; для варианта 2 применением леммы 10. Теорема 2. При любых значениях параметров p (0 < p < 1), q (0 < q < 1), X,- > 0 (X1 > X2), a,- > 0, i = 1, 2, функция pT (v) переменной T (0 < T < v ) достигает своего максимального значения в точке T = v , 0 < v < да. Доказательство вытекает из результата теоремы 1. Следствие 1. Из теоремы 1 вытекает, что функции pT (т(,)), j = 2, к, являются возрастающими функциями переменной T (0 < T < v). Следствие 2. Из теоремы 2 вытекает, что функция правдоподобия L(T | т(1),...,т(к)) достигает своего глобального максимума в точке T = Tm, то есть решением оптимизационной задачи (2) является оценка длительности мертвого времени T = Tm. Заключение Полученный результат делает возможным решение задачи оценки длительности мертвого времени без привлечения численных методов: в процессе наблюдения (в течение временного интервала (t0, t)) потока событий вычисляются величины тк, к = 1, n, после чего находится v = min тк (к = 1, n) и полагается T = Tm .

Скачать электронную версию публикации