The comparison of maximum likelihood estimation and method of moments estimation of dead time value in a generalized sem.pdf Настоящая статья является непосредственным продолжением исследований обобщенного полусинхронного потока событий (далее - поток), начатых в статьях [1-5]. Изучаемый поток относится к классу дважды стохастических потоков событий и является одной из адекватных математических моделей информационных потоков сообщений, функционирующих в цифровых сетях интегрального обслуживания (ЦСИО) [6]. Дважды стохастические потоки делятся на два класса: к первому классу относятся потоки, интенсивность которых есть непрерывный случайный процесс; ко второму классу относятся потоки, интенсивность которых есть кусочно-постоянный случайный процесс с конечным числом состояний. Второй класс потоков в настоящее время принято называть МС-потоками либо МАР-потоками событий. В [7] приведена классификация МС-потоков событий и установлена связь между МС-потоками и МАР-потоками событий. Наиболее полная литература по изучаемым типам МС-потоков приведена в [1, 8]. В реальных ситуациях параметры, задающие входящий поток событий, известны либо частично, либо вообще не известны, либо (что еще более ухудшает ситуацию) изменяются со временем. В подобных случаях наиболее рациональным является применение адаптивных систем массового обслуживания, которые в процессе функционирования оценивают неизвестные параметры либо состояния входящих потоков событий и изменяют дисциплины обслуживания в соответствии с полученными оценками [9]. Вследствие этого возникают задачи оценки состояний [10, 11] и оценки параметров [12, 13] потока по наблюдениям за моментами наступления событий. Одним из искажающих факторов при оценке состояний и параметров потока событий выступает мертвое время регистрирующих приборов [14], которое порождается зарегистрированным событием. Другие же события, наступившие в течение периода мертвого времени, недоступны наблюдению (теряются). Можно считать, что этот период продолжается некоторое фиксированное время (непродлевающееся мертвое время). В качестве примера приведем CSMA/CD - протокол случайного множествен -ного доступа с обнаружением конфликта, широко используемого в компьютерных сетях. В момент регистрации (обнаружения) конфликта на входе некоторого узла сети рассылается сигнал «заглушки» («пробки»); в течение времени рассылки сигнала «заглушки» заявки, поступившие в данный узел сети, получают отказ в обслуживании и направляются в источник повторных вызовов. Здесь время, в течение которого узел сети закрыт для обслуживания заявок, поступающих в него после обнаружения конфликта, можно трактовать как мертвое время прибора, регистрирующего конфликт в узле сети. Для того чтобы оценить потери сообщений потока, возникающие из-за эффекта мертвого времени, необходимо оценить его длительность. Подчеркнем, что задачи оценки параметров и длительности мертвого времени рассматривались в статьях [15-18] в рамках полусинхронного потока событий, который является частным случаем обобщенного полусинхронного потока событий, изучаемого в настоящей статье. Для оценки длительности мертвого времени, как правило, используются два метода оценивания: метод максимального правдоподобия [19, 20] и метод моментов [16, 17]. На основании сравнения [21] по тем или иным критериям получаемых МП-оценок и ММ-оценок делается вывод о применимости в конкретных условиях упомянутых методов. В настоящей статье производится сравнение оценок длительности мертвого времени в обобщенном полусинхронном потоке событий, полученных методом моментов и методом максимального правдоподобия. 1. Постановка задачи Рассматривается обобщенный полусинхронный поток событий, интенсивность которого есть кусочно-постоянный случайный процесс A(t) с двумя состояниями A1 и A2 (Ai > A2 > 0). В течение времен -ного интервала, когда A(t) = A,-, имеет место пуассоновский поток событий с интенсивностью Аг-, i = 1,2. Переход из первого состояния процесса A(t) во второе возможен только в момент наступления события, при этом переход осуществляется с вероятностью р (0 < p < 1); с вероятностью 1 - p процесс A(t) остается в первом состоянии. Тогда длительность пребывания процесса A(t) в первом состоянии есть случайная величина с экспоненциальной функцией распределения F1 (т) = 1 - e-pAlX. Переход из второго состояния процесса A(t) в первое может осуществляться в произвольный момент времени. При этом длительность пребывания процесса A(t) во втором состоянии распределена по экспоненциальному закону: F2 (т) = 1 - e-ат. При переходе процесса A(t) из второго состояния в первое инициируется с вероятностью 5 (0 < 5 < 1) дополнительное событие. При этом блочная матрица инфинитезимальных коэффициентов примет вид (1 - Р )А рА1 5а А2 -А, 0 IN а|. D = (1 -5) а -(А2 +а) Элементами матрицы D1 являются интенсивности переходов процесса A(t) из состояния в состояние с наступлением события. Недиагональные элементы матрицы D0 - интенсивности переходов из состояния в состояние без наступления события. Диагональные элементы матрицы D0 - интенсивности выхода процесса A(t) из своих состояний, взятые с противоположенным знаком. 1 а а а 2 Процесс A(t) 5 5 -О-С> Обобщенный полусинхронный поток ... t -Qzl T i T i T \ Схема создания непродлевающегося мертвого времени -Оt3 t4 Наблюдаемый поток событий T t ... t Рис. 1. Формирование наблюдаемого потока событий В сделанных предпосылках A(t) - скрытый марковский процесс. После каждого зарегистрированного в момент времени tk события наступает время фиксированной длительности Т (мертвое время), в течение которого другие события исходного потока недоступны наблюдению. События, наступившие в течение мертвого времени, не вызывают продления его периода (непродлевающееся мертвое время). По окончании мертвого времени первое наступившее событие снова создает период мертвого времени Т и т.д. Вариант возникающей ситуации показан на рис. 1, где 1, 2 - состояния случайного процесса X(t); дополнительные события, которые могут наступать в момент перехода процесса X(t) из второго состояния в первое, помечены буквой 5; штриховка - периоды мертвого времени длительности Т; t1, t2 ,... -моменты наступления событий в наблюдаемом потоке. Подчеркнем, что если 5 = 0, то имеет место обычный полусинхнонный поток событий [15-18]. Отметим также, что в соответствии с классификацией МАР-потоков событий, приведенной в [7], обобщенный полусинхронный поток относится к классу МАР-потоков событий второго порядка. Процесс X(t) и типы событий (события пуассоновских потоков и дополнительные события) являются принципиально ненаблюдаемыми, а наблюдаемыми являются только временные моменты наступления событий ti, t2,... наблюдаемого потока. Рассматривается установившийся (стационарный) режим функционирования наблюдаемого потока событий, поэтому переходными процессами на интервале наблюдения (t0, t), где t0 - начало наблюдений, t - окончание наблюдений, пренебрегаем. Необходимо в момент окончания наблюдений (в момент времени t ) осуществить методом максимального правдоподобия и методом моментов оценку T длительности мертвого времени и произвести сравнение полученных оценок. 2. МП-оценка длительности мертвого времени Обозначим тк = tk+1 - tk (k = 1,2,...) - значение длительности k-го интервала между соседними событиями наблюдаемого потока (тк > 0). Так как рассматривается стационарный режим, то плотность вероятностей значений длительности k-го интервала pT (тк) = pT (т), т > 0, для любого к (индекс T подчеркивает, что плотность вероятностей зависит от длительности мертвого времени). В силу этого момент tk без потери общности можно положить равным нулю или, что то же самое, момент наступления события наблюдаемого потока есть т = 0. Тогда [4] плотность вероятностей примет вид Pt (т) = 0, 0 < т < T; Pt (т) = [1 - f (T)] V^} + f (T)(a + X2)e"(a+X2)(т-Т), (T) = p(a + X2XX1 -X2 -a8)[X + (a + p\ - XQe-(a+pX1)T] (1) (a + pX1)(X1 -X2 -a)F(T) F(T) = (a + X2) -[X2 - p(X2 +a8)]e-(a+pX1)T, 0 0 для любых T (0 < T < т). Рассматривается общий случай, т.е. (Х - Х2 - а) Ф 0. Подчеркнем, что (1) - одномерная плотность вероятностей. Пусть т1 = t2 - t1, т2 = t3 - t2, ..., тк = tk+1 - tk - последовательность измеренных (в результате наблюдения за потоком в течение интервала наблюдения (0, t)) значений длительностей интервалов между соседними событиями потока. Упорядочим величины т1,..., Tk по возрастанию: ттт = т(1) < т(2) ) = ]рт(т(J)) = ]]{[1 - f (Т)]V"Mт( 1)"Т} + 1=1 1=1 (2) +f (Т)(a + X2)e-(a+X2)(т( 1)-т^max, 0 0, > 0 (А1 > А2), 0 < р < 1, 0 < 5 < 1, а > 0 МП-оценка ?МП = Tmin . Таким образом, в процессе наблюдения (в течение временного интервала (t0, t)) потока событий вычисляются величины xk, k = 1,n, после чего находится xmin = min xk (k = 1, n) и полагается ?1МП = Tmin . 3. ММ-оценка длительности мертвого времени В [4] показано, что обобщенный полусинхронный поток событий, функционирующий в условиях мертвого времени, в общем случае является коррелированным потоком. Только в частных случаях поток становится рекуррентным. Пусть (tk, tk+i), (tk+i , tk+2) - два смежных интервала в наблюдаемом потоке с соответствующими значениями длительностей: тк = tk+1 - tk, xk+i = tk+2 - tk+i; их расположение на временной оси, в силу стационарности потока, произвольно. Тогда можно положить k = 1 и рассматривать соседние интервалы (ti, t2), (t2, t3) с соответствующими значениями длительностей: xi = t2 - ti , т2 = t3 - t2; xi > 0, т2 > 0. При этом т1 = 0 соответствует моменту t1 наступления события наблюдаемого потока, т2 = 0 - моменту t2 наступления следующего события наблюдаемого потока. Соответствующая совместная плотность вероятностей при этом есть pT (т1, т2), т1 > 0, т2 > 0 [4]: Pt (хь Х2) = 0; 0 T, x2 > T, где fT), рт (тк) определены в (1) для т = тк , k = 1,2. Теоретическая ковариация значений т1 и т2 имеет вид 2 JxpT (x)dx T X cov(x!,Х2) = J/хгХ2Рт(Х1,X2)dx^dХ2 - TT Подставляя в последнюю формулу рт (xj, x2) из (3), рт (x) из (1), находим явный вид теоретической ковариации: cov(x!, Х2) = f (т)[1 - f (T)](A! - A2 - a)2 A2 -((A2 +a§)p e-(a+pA1)T, (4) Ax (a + A2) где f(T) определена в (1). Пусть за время наблюдения (в течение временного интервала (t0, t)) реализовалось n интервалов (tk, tk+1) длительности Tk, k = 1, n . Введем статистику (5) _1 n-1 j 1 n cov(x1, x2) =-- X xkXk+1 - \- Z Xk n -1 k=1 I nk=1 являющуюся оценкой теоретической ковариации (4). Тогда, согласно методу моментов [22], уравнение моментов, учитывающее коррелированность потока событий, запишется в виде -a)2 A2 - (A 2 +a5) p (a+pA1)T = f (T) [1 - f (T )](A1 -A 2-a) = cov(x1, Х2). (6) и проделывая при Af(a + A 2)3 Подставляя в (6) выражение f(T) из (1), вводя новую переменную x = e~'(a+pA1)T этом необходимые преобразования, находим (6) в виде ax3 + bx2 + cx + d = 0, a = h |Aj(a + A2) - (a + pAj) [Aj (1 - p) + A2 ]}; b = -jh[2X1(a + X2)-(a + pX1)(X1 +X2 +a)] + [X2 -p(X2 +a8)]2C0 j; c = (a + X2) jX1h + 2[X2 -p(X2 +a8)]C0 j; d = C0(a + X2)2; h pa(X1 -X2-a8)[X1(1 -p + p8)-(a + X2)][X2 -p(X2 +a8)] (7) [X1 (a + X 2)(a + pX1)] Решение уравнения (7) определит три корня x, i = 1,2,3, которые, в свою очередь, определят три ММ-оценки длительности мертвого времени - (i) 1 Tmm =--ln x, i = 1,2,3. a + pX1 Алгоритм нахождения единственной оценки Тmm следующий [21]: 1) для определенного набора параметров Х-, i = 1,2, а, р, 5, Т ед. времени осуществляется в течение Tm ед. времени имитационное моделирование наблюдаемого потока событий; 2) результатом работы имитационной модели является оценка теоретической ковариации (5), где n принимает одно из целых значений (n > 2); 3) решается кубическое уравнение (7), т.е. находятся корни x1, x2, x3; 4) если все корни комплексные, то Tmm = Tmin; 5) выделяются вещественные корни; здесь возможны три случая: 5.1) вещественный корень один - x1, тогда: а) если Х1 < 0, то Tmm = Tmm; Т Т (1) Т Т (1) Т (1) 6) если Х1 > 0, то: б.1) Tmm = Tmin, если Tmm > Tmin, б.2) Tmm = Tmm , если 0 < Tmm < Tmin, Т Т (1) б.3) Tmm = Tmm, если Tmm < 0; 5.2) вещественных корня два - x1, x2 (x1 < x2) , тогда: а) если Х1 < x2 < 0 , то Tmm = Tmm; Т Т (2) Т Т (2) Т (2) б) если Х1 < 0 < X2, то: б.1) Tmm = Tmin , если Tmm > Tmin, б.2) Tmm = Tmm , если 0 < Tmm < Tmin, Т Т (2) б.3) Tmm = Tmm, если Tmm < 0; Т Т (2) Т (1) Т Т (2) Т (2) в) если 0 < Х1 < X2, то: в.1) Tmm = Tmin , если Tmm < Tmm < Tmm , в.2) Tmm = Tmm , если 0 < Tmm < Т (1) Т Т (2) Т (1) Т Т (1) Т (2) Т (2) < Tmin < Tmm , в.3) Tmm = Tmin, если TMM < 0 < Tmin < TMM , в.4) Tmm = (Tmm + Tmm )/2, если 0 < Tmm < Т (1) Т Т (1) Т (2) Т (1) Т Т (2) Т (1) < Tmm < Tmin, в.5) Tmm = Tmm , если Tmm < 0 < Tmm < Tmin, в.6) Tmm = Tmm, если Tmm < Tmm < 0; 5.3) вещественных корня три - x1, x2, x3 (x1 < x2 < x3), тогда: а) если x1< x2 < x3 < 0 , то T mm = Tmin; Т Т (3) Т Т (3) Т (3) б) если X1< x2 < 0 < X3, то: б.1) Tmm = Tmin, если Tmm > Tmin, б.2) Tmm = Tmm , если 0 < Tmm < Tmin, Т Т (3) б.3) Tmm = Tmm, если Tmm < 0; Т Т (3) Т (2) Т Т (3) Т (3) в) если X1< 0 < x2< X3, то: в.1) Tmm = Tmm , если Tmm < Tmm < Tmm , в.2) Tmm = Tmm , если 0 < Tmm < Т (2) Т Т (3) Т (2) Т Т (2) Т (3) Т (3) < Tmin < Tmm , в.3) Tmm = Tmin, если TMM < 0 < Tmin < TMM , в.4) Tmm = (Tmm + Tmm )/2, если 0 < Tmm < Т (2) Т Т (2) Т (3) Т (2) Т Т (3) Т (2) < Tmm < Tmin, в.5) Tmm = Tmm , если Tmm < 0 < Tmm < Tmin, в.6) Tmm = Tmm, если Tmm < Tmm < 0; Т Т (3) Т (2) Т (1) Т Т (3) г) если 0 < X1< x2< X3, то: г.1) Tmm = Tmm, если Tmin < Tmm < Tmm < Tmm , г.2) Tmm = Tmm , если Т (3) Т (2) Т (1) Т Т (3) Т (2) Т (1) 0 < Tmm < Tmin < Tmm < Tmm , г.3) Tmm = Tmin, если Tmm < 0 < Tmin < Tmm < Tmm , т т (2) т (3) т (3) т (2) т (1) т т (2) т (3) г.4) Tmm = (Tmm + Tmm )/2, если 0 < Tmm < Tmm < xmm < Tmm , г.5) Tmm = Tmm , если Tmm < 0 < T (2) T (1) T T (3) T (2) T (1) T < Tmm < Tmm < Tmm , г.6) Tmm = Tmm, если Tmm < Tmm < 0 < Tmm < Tmm , г.7) Tmm = T (1) 1 (2) 1 (3) 1 (3) 1 (2) 1 (1) 1 1 (1) 1 (2) 1 (3) = (Tmm + Tmm + Tmm )/3, если 0 < Tmm < Tmm < Tmm < Tmm, г.8) Tmm = (Tmm + Tmm )/2, если Tmm < 0 < i (2) i (1) i i (1) i (3) i (2) i (1) i i (3) < Tmm < Tmm < Tmm, г.9) Tmm = Tmm , если Tmm < Tmm < 0 < Tmm < Tmm, г.10) Tmm = Tmm, если Tmm < i (2) i (1) < Tmm < Tmm < 0 < Tmm. В результате работы алгоритма осуществляется один из описанных вариантов, тем самым определится единственная ММ-оценка Tmm длительности мертвого времени. 4. Численное сравнение МП- и ММ-оценок Для получения численных результатов разработан алгоритм вычисления МП- и ММ-оценок. Программа расчета реализована на языке программирования С++ в среде Builder 6. Первый этап расчета предполагает имитационное моделирование (при заданных значениях параметров Xi, i = 1,2, a, p, 5, T ед. времени и заданном времени моделирования Tm ед. времени) наблюдаемого потока событий. Описание алгоритма имитационного моделирования здесь не приводится, так как никаких принципиальных трудностей алгоритм не содержит. Результатом работы имитационной модели является последовательность значений длительностей временных интервалов ti, T2,...,Tn (n = 2, 3, ...). Второй этап расчета - непосредственное вычисление МП- и ММ-оценок. Коротко опишем второй этап: 1) находится оценка Tмп = Tmin( xmin = min тк, к = 1, n ); 2) вычисляется оценка (5); 3) решается уравнение (7); 4) осуществляется алгоритм нахождения единственной оценки Tmm ; 5) вычисляются величины аТмп = (T мп - T)2, AT мм = (Tmm - T)2 , где T - истинное значение длительности мертвого времени, заданное на первом этапе расчета при осуществлении имитационного моделирования. Для сравнения качества МП- и ММ-оценок проведен статистический эксперимент, состоящий из следующих этапов: 1) для заданного набора параметров Xi, i = 1,2, a, p, 5, T ед. времени осуществляется моделирование наблюдаемого потока событий для заданного Tm ед. времени (отдельный J-й эксперимент, J = 1, 2, .); 2) осуществляется расчет оценок TMm , TmM для J-го эксперимента; 3) вычисляются величины aTmmmjt , AT Mm для j-го эксперимента; 4) осуществляется повторение N раз (J = 1, N) шагов 1-3. T (1) T (2) T (N) Результатом выполнения описанного алгоритма являются две выборки (Tмп,Tмп,...,Tмп ), T (1) T (2) T (N) (Tmm Tmm ,...,Tmm ), на основании которых вычисляются выборочные вариации полученных оценок: VMn = (1/N) Z aTm^,Vmm = (1/N) Z ATmm . J =1 J =1 Путем сравнения значений выборочных вариаций устанавливается, какая из оценок при заданных параметрах лучше, какая хуже: если VMn T); ее несмещенность реализуется только в асимптотическом случае при Tm ^ да. Результаты статистического эксперимента приведены в табл. 1-8. В первой строке таблиц указана длительность имитационного моделирования Tm (Tm = 10,20, ..., 50 ед. времени в табл. 1-4; Tm = 600, 700, ..., 1 000 ед. времени в табл. 5-8). Во второй и третьей строках таблиц для каждой длительности имитационного моделирования Tm приведены численные значения для VMn и Vmm соответственно. В четвертой строке таблиц для каждой длительности имитационного моделирования приведены численные значения разности Vмп - Vмм . Численные результаты во всех таблицах получены для N = 100. Т а б л и ц а 1 Результаты статистического эксперимента Х1 = 1, Х2 = 0,7, а = 0,01, р = 0,02, 5 = 0,2, Т = 0,4 т * m 30 40 50 60 70 умм 0,02186 0,00421 0,00369 0,00314 0,00253 умп 0,02208 0,00447 0,00371 0,00314 0,00253 V мп - умм 0,00022 0,00025 2,62960-10-5 0 0 Т а б л и ц а 2 Результаты статистического эксперимента Х1 = 0,7, Х2 = 0,2, а = 0,1, р = 0,2, 5 = 0,2, Т = 1 Т m 30 40 50 60 70 Vmm 0,29872 0,09011 0,08394 0,07245 0,04156 Умп 0,29988 0,09965 0,10131 0,07568 0,04156 Умп - Vmm 0,00115 0,00953 0,01737 0,00323 0 Т а б л и ц а 3 Результаты статистического эксперимента Х1 = 0,9, Х2 = 0,2, а = 0,1, р = 0,2, 5 = 0,2, Т = 1 Т m 30 40 50 60 70 Vmm 0,47389 0,06118 0,05562 0,04330 0,04432 Умп 0,4759 0,06667 0,05884 0,04336 0,04432 Умп - Vmm 0,00201 0,00549 0,00322 6,38402-10-5 0 Т а б л и ц а 4 Результаты статистического эксперимента Х1 = 0,7 , Х2 = 0,3, а = 0,1, р = 0,2 , 5 = 0,7 , Т = 0,4 Т m 30 40 50 60 70 Vmm 0,06944 0,05062 0,01856 0,01747 0,012561 VMn 0,06957 0,05288 0,01942 0,01747 0,012561 V мп - Vmm 0,00012 0,00226 0,00085 0 0 Т а б л и ц а 5 Результаты статистического эксперимента Х1 = 1, Х2 = 0,7, а = 0,01, р = 0,02, 5 = 0,2, Т = 0,4 Т m 600 700 800 900 1 000 Vmm 3,4325-10-5 0,0011 0,0017 2,9796-10-5 9,2298-10-5 VMn 2,611810-5 2,0686-10-5 1,1477-10-5 1,0959 10-5 9,2298-10-5 VMn - Vmm -8,2068-10-6 -0,001 -0,0017 -1,8837-10-5 0 Т а б л и ц а 6 Результаты статистического эксперимента Х1 = 0,7, Х2 = 0,2, а = 0,1, р = 0,2, 5 = 0,2, Т = 1 T m 600 700 800 900 1 000 Vmm 0,0094 0,0327 0,0116 0,0376 0,0238 VMn 0,0002 0,0002 0,0001 0,0001 0,0001 VMn - V mm -0,0091 -0,0325 -0,0115 -0,0375 -0,0237 Т а б л и ц а 7 Результаты статистического эксперимента Х1 = 0,9, Х2 = 0,2, а = 0,1, р = 0,2, 5 = 0,2, Т = 1 т m 600 700 800 900 1 000 Vmm 0,01542 0,0354 0,05089 0,03118 0,06874 VMn 0,00017 0,0002 0,00011 0,00013 0,0001 VMn - Vmm -0,01524 -0,0352 -0,05078 -0,03105 -0,0686 Т а б л и ц а 8 Результаты статистического эксперимента Х1 = 0,7, Х2 = 0,3, а = 0,1, р = 0,2, 5 = 0,7, Т = 0,4 T m 600 700 800 900 1 000 Vmm 0,00093 9,5221-10-5 0,0007 0,00146 0,00481 VMn 0,00012 7,9655-10-5 0,0001 4,6246-10-5 5,4977-10-5 VMn - Vmm -0,00081 -1,5566-10-5 -0,0006 -0,0014 -0,0047 Анализ приведенных численных результатов показывает что: 1) при малых временах наблюдения за потоком (при малых Tm = 30, 40, ..., 70 ед. времени) ММ-оценки лучше МП-оценок (табл. 1-4) либо, по крайней мере, не хуже МП-оценок (когда разность Умп - Vmm равна 0), что является вполне естественным, так как при малых временах наблюдения оценка Тмп может быть достаточно сильно смещенной относительно Т; 2) при больших временах наблюдения за потоком (при больших Tm = 600, 700, ., 1 000 ед. времени) МП-оценки лучше ММ-оценок (табл. 5-8) либо не хуже ММ-оценок (когда разность Vмп - V мм равна 0), что также является естественным, так как при больших временах наблюдения смещение оценки Тмп относительно Т уменьшается. Заключение Результаты проведенного исследования МП-оценок и ММ-оценок длительности мертвого времени T показывают общую тенденцию, что при малых временах наблюдения за потоком предпочтительнее применять оценку Тмм , при больших временах наблюдения - оценку Тмп . Границу применимости той или иной оценки (при заданных значениях параметров Xj, i = 1,2, а, р, 5) можно определить только численно путем имитационного моделирования.

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