The probability ofwrong decisions in the estimation of states of a generalized asynchronous flow of events.pdf Настоящая статья является непосредственным продолжением работы [1], в ко-торой рассматривается задача оценки состояний обобщенного асинхронного по-тока событий. Последний является достаточно адекватной математической моде-лью информационных потоков заявок (событий), функционирующих в современ-ных цифровых сетях интегрального обслуживания (ЦСИО) [2], и относится кклассу так называемых дважды стохастических потоков событий с интенсивно-стью, являющейся кусочно-постоянным случайным процессом. Достаточно об-ширная литература по исследованию подобных потоков событий (асинхронных,синхронных и полусинхронных) приведена в [1, 3, 4]. Вследствие этого в настоя-щей статье не акцентируется внимание на классификации дважды стохастическихпотоков событий и задачах, возникающих при их исследовании.В [1] решена задача оптимальной оценки состояний (задача фильтрации ин-тенсивности потока) обобщенного асинхронного потока событий по наблюдениямза потоком в течение конечного интервала времени. В качестве решающего пра-вила в [1] используется критерий максимума апостериорной вероятности, обеспе-чивающий минимум полной (безусловной) вероятности ошибки вынесения реше-ния о том или ином состоянии обобщенного асинхронного потока [5]. Путем ими-тационного моделирования в [1] найдены (для определенного набора параметров)оценки безусловной вероятности ошибки вынесения решения. В связи с этимпредставляет интерес получить аналитические результаты, связанные с нахожде-нием условной (безусловной) вероятности ошибки вынесения решения. Этомувопросу и посвящена настоящая статья.1. Постановка задачиРассматривается асинхронный дважды стохастический поток с инициировани-ем дополнительных событий (далее обобщенный асинхронный поток или простопоток), интенсивность которого есть кусочно-постоянный стационарный случай-ный процесс λ(t) с двумя состояниями λ1 и λ2 (λ1> λ2). В течение временного ин-тервала, когда λ(t) = λi , имеет место пуассоновский поток событий с интенсивно-стью λi , i = 1,2. Переход из первого состояния процесса λ(t) во второе (из второгов первое) может осуществляться в произвольный момент времени. При этом дли-тельность пребывания процесса λ(t) в i-м состоянии распределена по экспонен-цильному закону с параметром αi , i = 1,2. При переходе процесса λ(t) из первогосостояния во второе инициируется с вероятностью p (0 ≤ p ≤ 1) дополнительноесобытие во втором состоянии (т.е. сначала осуществляется переход, а затем ини-циируется дополнительное событие). Наоборот, при переходе процесса λ(t) извторого состояния в первое инициируется с вероятностью q (0 ≤ q ≤ 1) дополни-тельное событие в первом состоянии. Очевидно, что в сделанных предпосылкахλ(t) - марковский процесс. Вариант возникающей ситуации показан на рис. 1, где1, 2 - состояния случайного процесса λ(t); t1, t2,… - моменты наступления собы-тий; t2, t6,… - моменты инициирования дополнительных событий; t2 - моментинициирования с вероятностью p дополнительного события во втором состоянии;t6 - момент инициирования с вероятностью q дополнительного события в первомсостоянии.t1t2t3t4t5t6t7t12α1 α2 α1 α2 α1Процесс λ( ) tОбобщенный асинхронный потокtРис. 1. Формирование обобщенного асинхронного потокаЕсли p=q=0, то имеет место обычный асинхронный поток событий [6]. Так какпроцесс λ(t) и типы событий (события пуассоновских потоков и дополнительныесобытия) являются принципиально ненаблюдаемыми, а наблюдаемыми являютсятолько временные моменты наступления событий t1, t2,…, то необходимо по этимнаблюдениям оценить состояние процесса λ(t) (потока) в момент окончания на-блюдений и определить возникающую при этом безусловную (или условную) ве-роятность ошибки вынесения решения.Рассматривается установившийся (стационарный) режим функционированияпотока событий, поэтому переходными процессами на интервале наблюдения(t0, t), где t0 - начало наблюдений, t - окончание наблюдений (момент вынесениярешения), пренебрегаем. Тогда без потери общности можно положить t0=0. Пустьω(λi| t1,…, tm,t) - апостериорная вероятность того, что в момент времени t значе-ние процесса λ(t)= λi, i=1,2 (m - количество наблюденных событий за время t), приэтом21=1( | , , , )=1. i miΣω λ t t t … Вынесение решения о состоянии ненаблюдаемогопроцесса λ(t) (или потока) производится по критерию максимума апостериорнойвероятности: если ω(λ1| t1,…, tm,t) ≥ ω(λ2| t1,…, tm,t) (ω(λ1| t1,…, tm,t) ≥1/2), то оцен-ка состояния процесса λ(t) есть 1λˆ(t) =λ, в противном случае 2λˆ(t) =λ.2. Вероятность ошибочного решения о состоянииобобщенного асинхронного потока в общем случаеПусть полуинтервал наблюдения за обобщенным асинхронным потоком собы-тий есть (t0 , t]. Момент времени t зафиксирован, то есть длина полуинтервала на-блюдения есть t-t0. В силу того, что моменты наступления событий t1 ,…, ti (t1 ω1, то τi0 ≥ 0; при этом010 1 011 ( | ),0 ;( ( | 0), )1 ( | ), ;i i ii ii i iP t⎧⎪ −ω λ τ ≤ τ ≤ τω λ + τ = ⎨−ω λ τ τ > τ ⎪⎩(9)8) если ω1= ω(λ1|ti+0) = 1/2, то τi0 не существует и P0(ω(λ1|ti+0), τi ) = 1/2; дляданного варианта P0(ω(λ1|ti+0), τi) является безусловной вероятностью ошибки.Формулы (2), (3), (5) - (9) позволяют сформировать алгоритм расчета услов-ной вероятности вынесения ошибочного решения P0(ω(λ1|ti+0), τi) в любой моментвремени τi0 ≥ 0, i = 0, 1,… :1) в момент времени t0=0 задается ω(λ1|t0+0)=ω(λ1|t0=0)=π1;2) по формуле (5) для i=0 рассчитывается τi0, тем самым устанавливается по-ложение границы критической области на временной оси;3) находится один из восьми возможных вариантов соотношения величин ω1 иω(λ1|ti+0);4) для найденного варианта рассчитывается (с использованием формулы (2))вероятность P0(ω(λ1|ti+0), τ0) в любой момент времени τi (0≤ τi0 < ti+1 - ti); при этомдля третьего варианта (формула (7)) и седьмого варианта (формула (9)) может вы-полняться либо 0≤ τi0 < ti+1 - ti , либо τi0 > ti+1 - ti ;5) по формуле (2) рассчитывается вероятность ω(λ1|τi) в момент времениτi = ti+1 - ti , т.е. ω(λ1|ti+1-0); затем по формуле (3) производится пересчет апостери-орной вероятности в момент времени ti+1, т.е. находится ω(λ1|ti+1+0); i увеличива-ется на единицу и алгоритм переходит на шаг 2) и т.д.Сделаем важное замечание. В силу формулы пересчета (3) значение ω(λ1|ti+0)зависит от всех моментов t1,…, ti наступления событий в потоке, т.е. вся преды-дущая информация сосредоточена в вероятности ω(λ1|ti+0). Вследствие этого дляопределения безусловной вероятности ошибки необходимо усреднить условнуювероятность ошибки P0(ω(λ1|ti+0), τi) по моментам наступления событий t1,…, ti.Однако найти функцию распределения вероятностей моментов t1,…, ti наступле-ния событий в обобщенном асинхронном потоке в явном виде представляется за-труднительным или, вообще, невозможным. Как будет видно ниже, определитьбезусловную вероятность ошибки возможно только для некоторых частных иособых случаев.3. Частные случаиПредставляет интерес рассмотреть частные случаи соотношения параметровλi, αi , i=1,2, p, q.1. λ1+qα1 = λ2+pα2 , p ≠ q. Тогда ω1 = π1 = α2/(α1+α2), ω2 = (1 - q)/(p - q), a == (α1+α2)(p - q) ≠ 0. Так как ω(λ1|t0+0) = π1, то из (2) следует, что ω(λ1| τ0) = π1 для0 ≤ τ0 < t1 - t0, т.е. ω(λ1|t1 -0) = π1. Тогда из (3) вытекает, что ω(λ1|t1+0) = π1 и т.д.Таким образом, имеем ω(λ1|τi)=π1, τi ≥0, i=0,1,… . Последнее говорит о том, чтопри таком соотношении параметров информация о моментах наступления собы-тий t1,…, tm не оказывает влияния на апостериорную вероятность ω(λ1|τi), т.е. вконечном итоге не влияет на качество оценивания состояний процесса λ(t). Реше-ние о том или ином состоянии обобщенного асихронного потока выносится наосновании априорных данных. При этом вероятность P0(ω(λ1|ti+0), τi) = π2 , еслиπ1 ≥ π2 , либо P0(ω(λ1|ti+0), τi) = π1 , если π1 < π2, i = 0,1,… , т.е. в данном частномслучае P0(ω(λ1|ti+0), τi) является безусловной вероятностью ошибочного решения.2. Подкоренное выражение в (2) равно нулю:(λ1 - λ2 + α1 - α2)2 + 4α1α2 (1 - p)(1 - q) = 0.Данная ситуация возможна в двух случаях:2.1. p=1, 0≤ q 0, ω1=ω2=1. При этом [1][ ][ ]1 2 112 1( | 0) (1 ) 1 ( | 0)( | ) = , 0, 0,1,... ;1 (1 ) 1 ( | 0)i i ii ii it q tiq tω λ + + − α −ω λ + τω λ τ τ ≥ =+ − α −ωλ + τ2 1 2 112 2 2 1( ) ( | 0)( | 0)= , 1,2,....(1 ) ( | 0)iiiq q tt iq q tα + λ − α ω λ −ω λ + =λ + α + − α ωλ −(10)Подставляя (10) в (1), находим границу критической области[( ) ][ ]0 12 12 12 ( | 0)= , 0,1,... .(1 ) 1 ( | 0)iiitiq t−ω λ +τ =− α −ωλ +Тогда, если ω(λ1|ti+0) > 1/2, то τi0 1 π либо 1/2 > ω1 ≥ 1 π , то τ0 не существует и P0 определяетсявыражением (23);6) если 1/2 > 1 π > ω1, то τ0 < 0 и P0 определяется выражением (23);7) если 1 π ≥ 1/2 > ω1, то τ0 ≥ 0; при этом[ ]0000 01 200 1 1020 01 21 2 1 0 2 2( ) 1 ( | ) ( ) ( | )1 111 1i iz zz zi c ciP d de eB e B e D d dz z b e b eτ ∞ττ − τ ∞ − τ− τ − τ− τ − τ=τ= ωτ −ωλ τ τ+ ωτωλ τ τ=⎛ ⎞ ⎛ ⎞ ⎡ τ τ ⎤= − ⎜ +τ⎟ − ⎜ +τ⎟ − ⎢ τ− τ⎥+⎝ ⎠ ⎝ ⎠ ⎢⎣ − − ⎥⎦∫ ∫Σ ∫ ∫02 20( ) ( )1 20 2 2,1 1c z c zc ce eb A d db e b eτ − + τ ∞ − + τ− τ − ττ⎡ τ τ ⎤+ ⎢ τ− τ⎥⎢⎣ − − ⎥⎦∫ ∫ (24)где τ0 определяется формулой (17);8) если ω1= 1 π = 1/2, то τ0 не существует и P0 = 1/2.Интегралы, входящие в (21) - (24), могут быть вычислены только численно.2. λ1+pα1= λ2+qα2 , λ1=qα2, λ2=pα1, p≠q, 0≤ p ≤1, 0< q ≤1. Тогда a=0 и в рамкахтретьего частного случая (раздел 3) и формулы пересчета (13) следует, что1 1 2 1 2 ( | 0)= ( ), 1,2,.... iω λt+ π =qα pα +qα i = (25)Из (25) вытекает (аналогично первому особому случаю), что апостериорная веро-ятность ω(λ1|τi) не зависит от предыстории и для данного соотношения парамет-ров обобщенный асинхронный поток событий является рекуррентным потоком.Формула (12) при этом приобретает вид1 1 ( | )= ( )e , 0.ω λ τ ω+ π −ω −βτ τ≥ (26)Здесь величины ω, β определены в (12). Подставляя (26) в (1), находим границукритической области τ0 для любого интервала (ti , ti+1), i=0,1,… , в виде( )[ ]0 1 0 121 2 1 21 1 2 ( )= ln = ln .1 2 (1 ) (1 )q pp q p qω−π⎛ α α − ⎞τ β ω− ⎜⎝τ β α + α − α − − α⎟⎠(27)Из (27) следуют варианты положения τ0 на временной оси, аналогичные вариан-там 1) - 7) для первого особого случая. При этом можно показать, что плотностьвероятностей p(τ) (аналогичная плотности, определяемой выражением (19)) вы-пишется в виде( ) ( 1 2)1 2 ( ) , 0. p q p p q e− α + α τ τ = α + α τ≥ (28)Подставляя (28) в (18), находим( ) ( 1 2)21 2 ( ) , 0. p qp q e− α + α τω τ = α + α τ τ≥ (29)Учитывая (26), (29), получаем выражения безусловных вероятностей ошибокP0 для различных вариантов соотношения величин ω и 1 π :1) если 1/2 ≤ ω< 1 π , то τ0 не существует и( )21 20 11 21 ;p qP⎛ α + α ⎞= −ω−⎜ ⎟ π −ω⎝ α +α ⎠ (30)2) если 1/2 < 1 π < ω, то τ0 < 0 и P0 определяется выражением (30);3) если 1 π ≤ 1/2 < ω, то τ0 ≥ 0; при этом( )1 200 1 211 2(1 2 ) 1p qP p qα + α⎛ ω− ⎞ β= ω+ − ω⎡⎣+ α + α τ⎤⎦⎜⎝ω−π ⎟⎠ + ( ) ( )1 2 21 2 01 1 21 2 11 21 2 1 ( ) ,p qα +αβ⎡ ⎤+⎛⎜⎝ αα ++αα ⎞⎟⎠ π−ω ⎢⎢ − + α + α τ ⎛⎜⎝ ωω−−π ⎞⎟⎠ ⎥⎥⎢⎣ ⎥⎦ (31)где τ0 определяется формулой (27);4) если ω=1/2, ω> 1 π , то τ0 не существует; при этом( )21 20 11 2;p qP⎛ α + α ⎞= ω+⎜ ⎟ π −ω⎝ α +α ⎠ (32)5) если 1/2 ≥ ω> 1 π , то τ0 не существует и P0 определяется выражением (32);6) если 1/2 > 1 π > ω, то τ0 < 0 и P0 определяется выражением (32);7) если 1 π ≥ 1/2 > ω, то τ0 ≥ 0; при этом( )1 200 1 211 21 (1 2)1p qP p qα + α⎛ ω− ⎞ β= −ω− − ω⎡⎣+ α + α τ⎤⎦⎜⎝ω−π ⎟⎠ − ( ) ( )1 2 21 2 01 1 21 2 11 21 2 1 ( ) ,p qα +αβ⎡ ⎤−⎜⎝⎛ αα ++αα ⎟⎠⎞ π−ω ⎢⎢ − + α + α τ ⎛⎜⎝ ωω−−π ⎞⎟⎠ ⎥⎥⎢⎣ ⎥⎦ (33)где τ0 определяется формулой (27);5. Результаты численных расчетовДля получения численных результатов разработан алгоритм вычисления ус-ловной вероятности ошибки P0(ω(λ1|ti+0), τi) для общего случая, а также для част-ных и особых случаев. Программа расчета реализована на языке программирова-ния С++ в среде Builder 6. Первый этап расчета предполагает имитационное мо-делирование обобщенного асинхронного потока событий. Описание алгоритмаимитационного моделирования здесь не приводится, так как никаких принципи-альных трудностей алгоритм не содержит. Второй этап расчета - непосредствен-ное вычисление условной вероятности ошибки P0(ω(λ1|ti+0), τi) по формулам (6) -(9). Расчеты произведены для общего случая и для следующих значений парамет-ров : λ1=2, λ2=1, α1=0,01, α2=0,02, p=0,1, q=0,9 и времени моделирования T=100 ед.времени. В качестве иллюстрации на рис.2 приведена траектория (верхняя частьрис. 2) случайного процесса λ(t), полученная путем имитационного моделирова-ния (истинное поведение ненаблюдаемого процесса λ(t)), где 1, 2 - состоянияпроцесса λ(t), и траектория (нижняя часть рис. 2) оценки λˆ(t) , полученной покритерию максимума апостериорной вероятности, где 1, 2 - состояния оценкиλˆ(t) . Вынесение решения о состоянии процесса λ(t) производилось с шагомΔt=0,05. На рис.2 штриховкой на оси времени обозначены временные промежут-ки, на которых оценка состояния не совпадает с истинным значением процессаλ(t) (области ошибочных решений). На рис. 3 приведена траектория поведенияапостериорной вероятности ω(λ1|τi), i=0,1,…., соответствующая полученной приимитационном моделировании последовательности моментов наступления собы-тий t1, t2,… . На рис. 4 приведена траектория условной вероятности ошибкиP0(ω(λ1|ti+0), τi), i=0,1,…, соответствующая той же последовательности моментовнаступления событий.Таким образом, предложенный алгоритм осуществляет оценку состояний про-цесса λ(t) в любой момент времени t и одновременно в этот же момент временивычисляет условную вероятность сделанной при вынесении решения ошибки.0 1 2 3 4 5 t12λ( ) t0 1 2 3 4 5 t12λ( ) tРис. 2. Траектории процесса λ(t) и оценки λˆ(t)0 t 1 2 3 4 5 t1t2t3t4t5t6t7t8t9ω(λ1|τi)0,51Рис. 3. Траектория апостериорной вероятности ω(λ1|t)0t 1 2 3 4 5 t1t2t3t4t5t6t7t8t9P t 0(ω(λ1| i-0, τi)0,51Рис. 4. Траектория условной вероятности ошибки P0(ω(λ1|ti+0), τi), i=0,1,….Для особых случаев (раздел 4) получены графики безусловной вероятностиошибки P0. На рис. 5 приведены графики безусловной вероятности ошибки P0 дляпервого особого случая. Алгоритм расчета выглядит следующим образом: 1) зада-ется α1; 2) вычисляется ω1 и 1π ; 3) определяется один из восьми возможных вари-антов 1) - 8) и вычисляется P0 для этого варианта; 4) α1 заменяется на α1 + Δα1;5) алгоритм переходит на шаг 1 и т.д. Графики рассчитаны для следующих значе-ний параметров: λ2 = 0,05, α2 = 0,5, p = 1, q = 0,5. Параметр α1 изменяется по осиабсцисс от 0,01 до 2 с шагом Δα1=0,001 для различных значений λ1 = 0,5; 1; 1,5 (нарис. 5 каждому значению λ1 соответствует отдельная кривая).0 0,5 1 1,5 2 α1P00,20,4Рис. 5. Графики безусловной вероятности ошибки P0 для первого особого случаяНа рис. 6 приведены графики безусловной вероятности ошибки P0 для второгоособого случая. Алгоритм расчета аналогичен алгоритму для первого особогослучая. Графики рассчитаны для следующих значений параметров: λ2=0,009,α2=0,1, p=0,9, q=1. Параметр α1 изменяется по оси абсцисс от 0,01 до 2 с шагомΔα1=0,001 для различных значений λ1 = 0,1; 0,6; 1,1 (на рис. 6 каждому значениюλ1 соответствует отдельная кривая).0 0,5 1 1,5 2 α1P00,20,4Рис. 6. Графики безусловной вероятности ошибки P0 для второго особого случая5. ЗаключениеПредложенный алгоритм оптимального оценивания состояний обобщенногоасинхронного потока событий осуществляет оценку состояний по результатам те-кущих наблюдений за потоком. Параллельно с этим в момент оценки состоянияпотока вычисляется условная вероятность ошибки вынесения решения.Для особых случаев, когда поток событий является рекуррентным, выражениябезусловной вероятности ошибки выписаны в явном виде. Последнее позволяетдо начала наблюдений определить, при заданном наборе параметров, значениебезусловной вероятности ошибки, не привлекая методов имитационного модели-рования.

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