Оценка длительности непродлевающегося мертвого времени в коррелированном обобщенном синхронном потоке второго порядка | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 48. DOI: 10.17223/19988605/48/3

Оценка длительности непродлевающегося мертвого времени в коррелированном обобщенном синхронном потоке второго порядка

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

Estimation of the unextendable dead time duration in correlated synchronous generalized flow of the second order.pdf В настоящей статье проводится дальнейшее исследование относящегося к классу дважды хастических потоков [1-8] и являющегося математической моделью поступающих в системы и массового обслуживания (СМО и СеМО) информационных потоков заявок [9] обобщенного хронного потока событий второго порядка (далее потока), начатое в работах [10-12]. Режим функционирования как СМО, так и СеМО непосредственно зависит от параметров потока и состояния сопровождающего его процесса. Зачастую в реальных ситуациях эти характеристики либо лишь частично известны, либо неизвестны, либо изменяются со временем случайным образом, вследствие чего возникают задачи оценивания в произвольный момент времени состояний входящего потока (фильтрации его интенсивности) [10, 11, 13] и его параметров [12, 14, 15] по наблюдениям за ним. Математическая модель может также содержать искажающие факторы, к числу которых, в частности, относится мертвое время регистрирующих приборов [16, 17], порождаемое каждым зарегистрированным событием так, что последующие события исходного потока, наступившие в течение обозначенного периода времени, не вызывают его продления (непродлевающееся мертвое время) [11, 14] и теряются для наблюдения. На предмет установления количества потерянных событий потока, возникающих ввиду эффекта мертвого времени, необходимо оценить его длительность; с этой целью в данной работе применяется метод моментов, обеспечивающий построение оценок, обладающих достаточно хорошими свойствами при больших объемах выборок наблюдаемых моментов наступления событий. 1. Математическая модель потока Рассматривается обобщенный синхронный поток событий второго порядка, сопровождающий случайный процесс которого λ(t) является кусочно-постоянным с двумя состояниями и ; здесь и далее Si понимается как і-е состояние λ(t) и имеет место при λ(t) = λi, i = 1,2 , λ1 > λ2 ≥ 0. Длительность интервала между событиями потока в і-м состоянии определяется случайной величиной = min(^(1),ξi(2)), где случайные величины (1) и "ζi^((2') независимы и распределены по 21 Л.А. Нежельская, Е.Ф. Сидорова законам ^1*(t) = 1 -e и ^^^(t) = 1 - e соответственно. В момент наступления события потока процесс λ(t) либо переходит из i-го состояния в /-е, i ≠ j, либо остается в i-м состоянии, i = j , с вероятностью Р/1^ (λ j | λ) или р/2^ (λ j | λi), i, j = 1,2, в зависимости от значения ηi, i = 1,2 . При этом P1(1)(λj | λj) + P1(1)(λi | λi) = 1, P1-^'')(Xj | λj) + P11'^'^(λj | λi) = 1, i, j = 1,2, i ≠ j . Процесс λ(t) является скрытым марковским [10] с матрицами инфинитезимальных характеристик λ1P1(1)(λ1 | λ1) + α1P1(2)(λ1 | λ1) λ1P1(1)(λ| Xj) + α1P1(2)(λ| λ1) λ2P1(1)(X1 | λ2) + α2P1(2)(X1 | λ2) λ2P1(1)(X| λ2) + α2P1(2)(Xг | λ2) . D0 = - (λ 1 +а1) 0 0 - (λ 2 +α 2) , D1 = Элементами матрицы D выступают интенсивности сопряженных с наступлением события потока переходов процесса λ(t) из состояния в состояние. Недиагональные элементы D имеют смысл интенсивностей переходов из состояния в состояние без наступления события; диагональные - интенсивностей выхода λ(t) из своих состояний, взятые с противоположным знаком [5]. Имеет место ситуация недоступности наблюдению всех событий потока - каждое зарегистрированное в момент времени t событие порождает непродлевающееся мертвое время фиксированной длительности T , в течение которого другие события исходного потока теряются, а по его окончании первое наступившее событие вновь вызывает период ненаблюдаемости длительности T и т.д. Вариант возникающей ситуации приведен на рис. 1, где S1, S2 - состояния случайного процесса λ(t), t ,t ,...,t , ... - моменты наступления событий в наблюдаемом потоке, штриховкой показаны периоды мертвого времени; черными кружками обозначены потерянные события обобщенного синхронного потока второго порядка, белыми - наблюдаемые события. S1 S2 P1(2)(λ1|λ1) 9 , ζ≤- ¾ P1(2)(λ2∣λ2) P1(^)(λ1|λ1) д' > _≤. о P12W1) -t-^- -- ... t Процесс λ(t) t Обобщенный синхронный поток событий второго поряДка T \\ T '' T '' T t Схема созДания мертвого времени t1 t2 t4 t5 ⅛t6 -⅛--------------⅛ ⅛ t7 t8 t9 t Наблюдаемый поток событий Рис. 1. Формирование наблюдаемого потока событий Fig. 1. Formation of the observed event flow Поскольку рассматривается установившийся (стационарный) режим функционирования исследуемого дважды стохастического потока событий (наблюдение за ним начинается тогда, когда он функционирует бесконечно долго), в силу сформулированных предпосылок последовательность заключающих в себе всю доступную информацию о потоке наблюдаемых моментов t1,t2,...,tk ,... образует вложенную цепь Маркова {λ(⅛)} , т.е. наблюдаемый поток событий обладает марковским свойством, если его эволюцию рассматривать с момента tk , k = 1,2,.... 22 Оценка длительности непродлевающегося мертвого времени 2. Вывод плотности вероятности значений длительности интервала между событиями в потоке Определим значение длительности k-го интервала между событиями tk и tk+1, k = 1,2,..., как ^^k = tk+1 - tk, τk ≥ 0. Для плотности вероятности значения τk, ввиду рассмотрения стационарного режима, справедливо р^, (τ,) = (τ) , τ ≥ 0, k ≥ 1, что позволяет без ограничения общности положить t равным нулю или, что то же самое, момент наступления события в наблюдаемом потоке есть τ=0; индекс T подчеркивает зависимость плотности от длительности мертвого времени. Рассмотрим интервал (0, τ) длительности τ = T +1 между соседними событиями наблюдаемого потока; t - значение длительности интервала между моментом окончания мертвого времени фиксированной длительности T и моментом наступления следующего события, t > 0. Введем " (T) - вероятность того, что за мертвое время длительности T процесс λ(τ) перейдет из /-го состояния Sj (имеет место в момент τ = 0) в j-е Sj (имеет место в момент τ = T), i, j = 1,2; (0 | T) - условную стационарную вероятность того, что процесс λ(τ) в момент времени τ = 0 пребывает в состоянии S , i=1,2, при условии, что τ=0 есть момент наступления события наблюдаемого потока и порождения мертвого времени длительности T . На интервале (0, t), когда обобщенный синхронный поток событий второго порядка вновь наблюдаем, его поведение описывается условной вероятностью pjk(t) того, что на (0,t) нет событий потока и λ(t) = λk при условии, что λ(0) = λ j , j,k =1,2; соответствующую p jk(t) плотность запишем как ~pjk(t), j,k =1,2. Тогда искомая плотность вероятности p (τ) запишется в виде: 0, 0 ≤ τ < T, (τ) = J 2 2 2 _ (1) Pτ (τ) = ^ 2 PT ( ) π, (0|T) (T) ∑Pjk (τ-T), τ≥ T. k=1 i=1 j=1 k=1 Для исследуемого потока справедливы следующие леммы. Лемма 1. Переходные вероятности "ij(T), i, j =1,2, в коррелированном обобщенном синхронном потоке событий второго порядка с мертвым временем имеют вид: (2) Q11(T} = π1 + , q12(T} = π2 -K2e~-^T, q21(T} = К1 -K1e"^T, q22(T^ = Кз + K1e"^T, где φ, = λiP1(1) (,λJ 1 λ,) + a,p1^''^ (,λJ 1 λi) , i, j = 1,2, i ≠ j, φ = Ф1 + φ2 , К1 = φ2φ-1, π2 = Ф1ф-1. Доказательство. Для введенных вероятностей имеют место дифференциальные уравнения q',1 (τ) = -φ1q,1 (τ) + φ2qi2 (τ), q',2 (τ) = φ1q∏ (τ) - φ2qi2 (τ), i = 1,2, с начальными условиями q11(0) = q22(0) = 1, q12(0) = q21(0) = 0 . Интегрируя полученные системы [19] и заменяя в решении момент времени τ на T , приходим к (2). Лемма 1 доказана. Найдем pjk - вероятность перехода процесса λ(τ) из состояния Sj в состояние Sk, j,k =1,2, за время, которое пройдет от момента t = 0 до момента наступления следующего события потока. Лемма 2. В потоке с мертвым временем вероятности p jk , j,k =1,2, определяются формулами p11 =1- φ1z1 , p12 = φ1z1 , p21 = φ2z2 , p22 =1- φ2z2 , (3) где z1 = λ1 + a1, z2 = λ2 + a2 ; φ1, φ2 определены в (2). Доказательство. Условные вероятности p jk(t), j,k =1,2, идентичны по своему смысловому значению вероятностям pij(τ) , i, j =1,2, для исследуемого потока в случае отсутствия мертвого времени, т.е. определяются теми же формулами [12] при τ=t . Согласно определению потока установ- 23 Л.А. Нежельская, Е.Ф. Сидорова лена величина pjj(t)(λ jP*"(λk | λ.) + aу■P1(2)(λk | λ.))∆t + o(∆t), которая является совместной вероятностью того, что без наступления события наблюдаемого потока на интервале (O, t) процесс λ(t) переходит на этом интервале из состояния S. в состояние Sk, J, k = 1,2, на полуинтервале [1, t + ∆t) происходит окончание состояния S процесса λ(t) , и в результате розыгрыша пар в момент наступления события λ(t) переходит из Sk в Sj , J,k = 1,2. Эта величина представима в виде: Pjj (t)(λJP1(1)(λk 1 λJ) + ajP1^''^(λk | λ. ))∆t + o(∆t') = ∫~.k(u)du =~.k (1 )∆t + o(∆t), t где ~p Jk(t) - соответствующая вероятности pJk(t) плотность вероятности, J, k =1, 2. Тогда плотности ~p Jk(t) того, что без наступления события на (O, t) и наступления события в момент t процесс λ(t) перейдет из состояния S J в состояние Sk , J, k =1, 2, запишутся в виде [12]: ~pJk(t) = (λ JP1(1)(λk ∣ λJ) +a JP1(2)(λk ∣ λ J))e-zJt . (4) В силу произвольности момента t вероятности перехода pJk , J, k =1, 2, определяются как pJk = ∫ ~pJk(t)dt . O Подставляя (4) в (5) и выполняя интегрирование, получим (3). Лемма 2 доказана. Лемма 3. Условные стационарные вероятности πi(O∣T) , i =1,2, задаются выражениями π (O | t) = ^1Φ2 + π1(z1z2 - z1Φ2 - z2Φ1k(1 - e^φτ k 1 z1φ2 + z2φ1 + (z1z2 - z1φ2 - z2ф1k(1 - e^φτ k где φ1, φ2, φ, π1, π2 определены в (2), z1, z2 - в (3). Доказательство. Поскольку в моменты t ,t ,...,t , ... последовательность {λ(t )} представляет собой вложенную цепь Маркова, для вероятностей πi(O∣T) , i =1,2, справедливы уравнения π1(O∣T) = π1(O ∣T)π11(T) + π2(O∣T)π21(T), π2(O ∣T) = π1(O∣T)π12(T) + π2(O∣T)π22(T), (7) где πk (T) - переходная вероятность того, что за время, которое пройдет от момента τ = O до наступления следующего события потока, λ(τ) перейдет из состояния S^ в состояние Sk, i, k = 1,2 . В силу марковости λ(t) вероятности qiJ(T) и pJk , определенные в (2) и (3) соответственно, i, J,k =1,2 , позволяют записать для πik (T) , i,k =1,2 , следующие выражения: π11(T) = q11(T ) p11 + q12(T)p21, π12 (T ) = q11(T)p12 + q12(T)p22, π11(T) + π12 (T ) =1, π21(T) = q21(T)p11 + q22(T)p21, π22(T) = q21(T)p12 + q22(T)p22, π21(T) + π22(T) =1. Подставляя в (8) переходные вероятности qiJ(T) , i, J =1, 2 , найденные в виде (2), получим π1k (T ) = p1k -π2(p1k - p2k)(1-e-φT), π2k(T) = p2k +π1(p1k - p2k)(1-e-φT ). Далее, подставляя (9) и (3) в уравнения (7), приходим к (6). Лемма 3 доказана. На основании лемм 1-3 сформулируем теорему. Теорема. В коррелированном потоке, функционирующем в условиях непродлевающегося мертвого времени, плотность вероятности длительности интервала между событиями имеет вид: O, O ≤ τ < T, pT ( τ) = I [γ(T)z1e-Z1(τ-T) + (1 - γ(Tkkz2e-z2(τ-T), τ ≥ T, где γ(T) = π1 -π1φ1(z1 -z2)(z1z2 -z1φ2 -z2φ1 -z1z2e'φτ)-1; φ1,φ2,φ, π1 определены в (2), z1, z2 - в (3). Доказательство. Подставляя в (1) сначала (4), затем (2) и, наконец, (6), проделывая достаточно трудоемкие преобразования с учетом t = τ -T , приходим к (10). Теорема доказана. -ф , π2(O∣T) = 1 -π1(O∣T), 24 (5) (6) (8) (9) (10) Оценка длительности непродлевающегося мертвого времени Замечание 1. Равенство z = z = z, которое вполне может выполняться в силу того, что λ , λ удовлетворяют условию λ1 >λ2 ≥ 0, а α1, а 2, вообще говоря, произвольные неотрицательные числа, приводит к (τ) = ze^z^-'^-T'); поток вырождается в простейший. В дальнейшем принимается z . Отметим, что приведенная в [12] формула для плотности - частный случай (10) при T = 0. Нетрудно по p(τ) [12] и p (τ) вида (10) получить выражения для среднего числа событий в единицу времени в обобщенном синхронном потоке второго порядка в условиях полной наблюдаемости Л и при непродлевающемся мертвом времени Л соответственно. На их основе при φ, , φ, и z1, z2, определенных в (2) и (3), запишем среднее число потерянных событий в единицу времени: Д _ Д _ Д _ к1к 2(z1 - z 2) (1 - ) + T(z1K1 + z 2К 2)(z1 'z 2 - z1φ2 - Z2 φ1 - Z1 'z2 ) q і ∖ = Л T = . (C,T . , ( ) (+ к)(1 - e) + T(^¾ - - ^¾e) - φ φT Z1^2 - Z1φ2 - z2φ1 - z1z2eφ где Л - Z1K1 + Z2K2, Лт - ψ T . (^1к2 + z2K1)(l - eφ ) + T (z1z2 - z1φ2 - z2φ1 - z1z2eφ )-φ 3. Оценка длительности мертвого времени в наблюдаемом потоке Для оценки периода ненаблюдаемости обратимся к методу моментов [18]: рассмотрим выборку τ1, τ2,..., τn из распределения рт (τ) = y(T)z1eΓz1^-'τ-τ'') + (1 -y(T))z2e^Z2^■'τ-T'), τ≥ T, зависящего от параметра T . В силу близости теоретической и эмпирической функций распределения (неограниченного сближения их значений при достаточно большом n ) следует ожидать близости теоретического начального момента первого порядка Mτ = ∫ τp^ (τ) dτ и статистики Cj =1 'Lτk , т.е. чтобы найти T , необхо- T n k =1 димо решить уравнение моментов Mτ = C , принимающее вид: t + (z2 - Z1')y(T)z1-1z2-1 + z2-1 = c1 . (12) Решение (12) возможно только с применением численных методов. Замечание 2. Для f (T) = Mτ : f '(T) = 1 + φ1φ2(z1 -z2)'^eφτ(z1z2 -z1φ2 -z2φ1 -z1z2eφτ)-2 > 0, f (0) = (z1K1 + z2 π2)^1 > 0. Тогда f (T) - возрастающая функция переменной T , T ≥ 0. Согласно замечанию 2 оценка длительности мертвого времени T^ (численное решение (12)) на полуинтервале (0, τmin], где τmin = min τk , k =1,2,...,n , определяется единственным образом: t4m = ^t, если f (0) < c1 < f (τmin) ; ТЧМ = τmin , если f(0) < f (τmin) ≤ c1 ; t4m = 0 , если f (0) ≥ c1 . Рассмотрим подход, обеспечивающий аналитическое решение T: воспользуемся замечанием, сформулированным в [18] и позволяющим использовать одноименные центральные моменты - дисперсию Dτ = ∫τ2pτ (τ)dτ-{Mτ)z и выборочную дисперсию C2 - C, где C2 - ∑τ. В данном T n k =1 k случае преобразованное уравнение моментов Dτ = C2 -C 2 для оценивания T запишется в виде: (z2 - z1)2У^(Т) - 2z2(z2 - z1)y(T) - z12(1 + c12zl - c2zl} = 0 . (13) При решении (13), с учетом замечания 1, возможны следующие варианты. 1. z 2 + z 2(1+C 2z 2 -C2z 2) > 0: 1.1) z1 > z2 , 1 + C12z22 - C2z22 > 0, тогда γ(T) = ^z2 -^z2 + z2 (1 + C z2 - C2z2 ) j^z2 - z1)-1; 1.2) z2 > z1 , тогда γ(T) = (z2 z^ + z12(1 + C^ z^ - C2z22) j^z2 - z1)-1; 25 Л.А. Нежельская, Е.Ф. Сидорова 1.3) Z2 > Z1, 1 + C12Z22 - C2Z22 < 0, тогда γ1,2(T) = (z2 z^ + z12(1 + C12z22 -C2z^) jfz2 -z1) 1. 2. z 2 + z 2(1+ C 2z 2 -C2z 2) = 0 : 2.1) Z1 > Z2 , тогда γ(T) = z2(z2 - z1)-1 < 0 и корень исключается из рассмотрения; 2.2) Z2 > Z1, тогда γ(T) = z2(z2 -Z1)-1. 3. Z 2 + Z 2(1+ C 2Z 2 -C2Z 2) < 0 : действительных корней нет, увеличивается выборка. Так, T = φ-1ln 11 -φ1z^1 -φ2¾^1 -π1φ1(z1 -z2)z1-1z2^1(π1 -γ(T))-11 при единственном корне (13), и полученная аналитически оценка мертвого времени Ta есть: Ta = T , если 0 < T ; Ta = 0 , если T < 0. При двух действительных корнях уравнения моментов T1,2 =φ-1ln∣1 -φ1z1-1 -φ2z2-1 -π1φ1(z1 - z2)z1-1z-1(π1 -γ1,2(T))-1∣, и оценка Ta устанавливается как Ta = 0,5 (T1 + T2}, если 0 < T2 < T1

Ключевые слова

обобщенный синхронный дважды стохастический поток второго порядка, непродлевающееся мертвое время, плотность вероятности, оценка параметра, метод моментов, synchronous generalized doubly stochastic flow of the second order, unextendable dead time, probability density, parameter estimation, method of moments

Авторы

ФИООрганизацияДополнительноE-mail
Нежельская Людмила АлексеевнаТомский государственный университетдоцент, доктор физико-математических наук, профессор кафедры прикладной математики Института прикладной математики и компьютерных наукludne@mail.ru
Сидорова Екатерина ФилипповнаТомский государственный университетаспирант кафедры прикладной математики Института прикладной математики и компьютерных наук Нkatusha_sidorova@mail.ru
Всего: 2

Ссылки

Cox D.R. The analysis of non-Markovian stochastic processes by the inclusion of supplementary variables // Proc. of the Cam bridge Philosophical Society. 1955. V. 51, No. 3. P. 433-441.
Kingman J.F.C. On doubly stochastic Poisson process // Proc. of the Cambridge Philosophical Society. 1964. V. 60, is. 4. P. 923-930.
Cox D.R., Miller H.D. The theory of stochastic processes. New York : Wiley, 1965. 398 p.
Башарин Г.П., Кокотушкин В.А., Наумов В.А. О методе эквивалентных замен расчета фрагментов сетей связи. Ч. 1 // Известия АН СССР. Техническая кибернетика. 1979. № 6. С. 92-99.
Башарин Г.П., Кокотушкин В.А., Наумов В.А. О методе эквивалентных замен расчета фрагментов сетей связи. Ч. 2 // Известия АН СССР. Техническая кибернетика. 1980. № 1. С. 55-61.
Neuts M.F. A versatile Markovian point process // Journal of Applied Probability. 1979. V. 16. P. 764-779.
Snyder D.L., Miller M.I. Random point processes in time and space. Heidelberg : Springer-Verlag, 1991. 481 p.
Lucantoni D.M. New results on the single server queue with a batch markovian arrival process // Communications in Statistics Stochastic Models. 1991. V. 7. P. 1-46.
Дудин А.Н., Клименок В.И. Системы массового обслуживания с коррелированными потоками. Минск : Изд-во Белорус. гос. ун-та, 2000. 175 с.
Nezhelskaya L., Sidorova E. Optimal estimation of the states of synchronous generalized flow of events of the second order under its complete observability // Communications in Computer and Information Science. 2018. V. 912. P. 157-171.
Нежельская Л.А., Сидорова Е.Ф. Оптимальная оценка состояний обобщенного синхронного потока событий второго порядка в условиях неполной наблюдаемости // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2018. № 45. С. 30-41.
Нежельская Л.А., Сидорова Е.Ф. Оценивание параметров плотности вероятности значений длительности интервала между событиями в коррелированном обобщенном синхронном потоке второго порядка // Информационные технологии и математическое моделирование (ИТММ-2019) : материалы XVIII Междунар. конф. им. А.Ф. Терпугова. Томск : Изд-во НТЛ, 2019. Ч. 2. С. 358-363.
Nezhelskaya L. Optimal state estimation in modulated MAP event flows with unextandable dead time // Communications in Computer and Information Science. 2014. V. 487. P. 342-350.
Nezhel'skaya L. Probability density function for modulated MAP event flows with unextandable dead time // Communications in Computer and Information Science. 2015. V. 564. P. 141-151.
Okamura H., Dohi T., Trivedi K.S. Markovian arrival process parameter estimation with group data // IEEE/ACM Transactions on Networking (TON). 2009. V. 17, No. 4. P. 1326-1339.
Апанасович В.В., Коляда А.А., Чернявский А.Ф. Статистический анализ случайных потоков в физическом эксперименте. Минск : Университетское, 1988. 256 с.
Normey-Rico J.E. Control of dead-time process. London : Springer-Verlag, 2007. 462 p.
Малинковский Ю.В. Теория вероятностей и математическая статистика. Гомель : УО «ГТУ им. Ф. Скорины», 2004. Ч. 2: Математическая статистика. 146 с.
Камке Э. Справочник по обыкновенным дифференциальным уравнениям. М. : Наука, 1976. 576 с.
 Оценка длительности непродлевающегося мертвого времени в коррелированном обобщенном синхронном потоке второго порядка | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 48. DOI: 10.17223/19988605/48/3

Оценка длительности непродлевающегося мертвого времени в коррелированном обобщенном синхронном потоке второго порядка | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 48. DOI: 10.17223/19988605/48/3