Поток событий

Глава 1. Потоки событий. Иллюстрация от Эва Эриксон (Н. Ульф. День с мышиной пожарной командой. – М.: «Самокат», 2016) • Потоком событий называется последовательность однородных событий, появляющихся одно за другим в случайные моменты времени. Примеры: поток вызовов на телефонной станции; поток забитых шайб при игре в хоккей; поток сбоев ЭВМ; поток заявок на проведение регламентных работ в вычислительном центре и т.п. h • • • Поток событий наглядно изображается рядом точек с абсциссами Θ1, Θ2,… с интервалами между ними: Т1= Θ2- Θ1, Т2= Θ3- Θ2,…, Тn= Θn+1- Θn. При его вероятностном описании поток событий может быть представлен как последовательность случайных величин: {Θ1, Θ2= Θ1+T1, Θ3= Θ1+T1+T2,…} либо как {Θ1, T1, T2, …}. • Заметим, что термин «событие» в понятии «поток событий» совершенно отличен по смыслу от ранее введенного термина «случайное событие». В частности, не имеет смысла говорить о вероятностях «событий», образующих поток (например, о «вероятности вызова» на телефонной станции; ясно, что рано или поздно вызов придет, и не один). Заметим также, что на рисунке в виде ряда точек можно изобразить не cам поток событий (он случаен),а только какую-то его конкретную реализацию. • • • • Поток событий называется стационарным, если его вероятностные характеристики не зависят от выбора начала отсчета или, боле конкретно, если вероятность попадания того или другого числа событий на любой интервал времени зависит только от длины h этого интервала и не зависит от того, где именно на оси 0t он расположен. Поток событий называется ординарным, если вероятность попадания на элементарный интервал времени ∆t двух или более событий пренебрежимо мала по сравнению с величиной интервала. П. с. называется потоком без последействия, если число событий, попадающих на любой интервал времени т, не зависит от того, сколько событий попало на любой другой непересекающийся с ним интервал. Практически отсутствие последствия в потоке означает, что события, образующие поток, появляются в те или другие моменты времени независимо друг от друга. • Определение. П. с. называется простейшим, если он стационарен, ординарен и не имеет последействия. • Для формализации этих понятий введём следующие математические объекты. Пусть pk: R×R → R – семейство двумерных функций, таких что pk(t, Δt) - вероятность того, что «за время Δt, примыкающего к моменту времени t, появилось k событий» (высказывание, характеризующее событие в некотором вероятностном пр-ве), k = 0,1,2,… Очевидно, что сумма всех таких событий равна всему вероятностному пространству: Σpi(t, Δt) = 1 (1) • • • • • • • • • • ∞ Введем обозначение p>1(t,Δt) = Σpi(t, Δt) - вероятность того, что за время i=2 Δt появилось более одного события. Тогда формула (1) примет вид: p0(t, Δt) + p1(t, Δt) + p>1(t, Δt) = 1 и свойство ординарности можно записать как p>1(t, Δt) = o(Δt) , где o(Δt) – бесконечно малая по отношению к Δt величина, т.е. o(Δt) /Δt → 0 при Δt → 0 (и, напротив, O(Δt) означает, что O(Δt)/ Δt → Const ) Обозначим через a(t, Δt) математическое ожидание числа событий, появившихся за время Δt, тогда ∞ a(t, Δt) = Σi pi(t, Δt) = 0* p0(t, Δt) + 1* p1(t, Δt) + Σ i pi(t, Δt) = p1(t, Δt) + o(Δt) i=2 для ординарного потока, так как последняя сумма равна o(Δt). Это тривиальный факт, если взять дополнительное ограничение на число событий за малый отрезок. Если не ограничивать число событий, то это следует из одного из свойств сходимости по вероятности, если считать, что матожидание a(t, Δt) существует и конечно для любого Δt. Ещё одно свойство сходимости по вероятности Пусть Xn → X при n → ∞. Тогда для сходимости EXn → EX достаточно выполнения любого из следующих условий : 1. Все члены послед-ти ограничены одной и той же постоянной: |Xn| ≤ C 2. Все члены послед-ти огранич. одной и той же случ. величиной с конечным первым моментом: |Xn| ≤ Y, EY < ∞. 3. Существует α > 1 такое, что E|Xn|α ≤ C = const для любого n. • • • • • • • • Действительно, рассмотрим последов-ть Δtk ≡ Δt / k → 0 и соответствующую ей послед-ть случайных величин Xk = <число событий на интервале (t, Δtk) >, имеющих распределения P(Xk= i) = pi(t, Δtk) и определим послед-ть {Zk (ω) = Xk (ω) для люб. исхода ω, такого что Xk(ω) > 1, иначе Zk (ω)=0} Тогда послед-ть Zk → 0 при k → ∞ по свойству ординарности, и рассмотрим послед-ть | | Zk ≡ Zk / Δtk → 0 (имеем P (Zk = i / Δtk ) = o(Δtk) для любого k) Воспользуемся вышепривед. свойством сходимости по вероятности, пункт 3: | Рассмотрим i –й член суммы математического ожидания EZk i pi(t, Δtk) / Δtk = i o(Δtk) / Δtk → 0 (при k → ∞) Каждый след. интервал Δtk меньше предыдущего, поэтому с некоторого | k=n+1 i-й член суммы EZk постоянно уменьшается, и, учитывая, что | | | | pj+1(t, Δtk) < pj(t, Δtk) , вся сумма меньше EZn ➔ E|Zk | = EZk < EZn = Const ∞ | | Следовательно, EZk → 0 ➔ EZk * Δtk ≡ EZk = Σ i pi(t, Δtk) = o(Δtk) i=2 Определение Интенсивностью (плотностью) потока событий в момент t будем называть функцию | λ(t) = lim a(t, Δt) ≡ (a(t, h)) h Δt→0 Δt ТЕОРЕМА Интенсивность (плотноcть) ординарного потока равна λ(t) = lim p1(t, Δt) Δt→0 Δt По смыслу плотность выражает среднее число событий, приходящихся на единицу времени (и, обычно, можно говорить о её значении на конкретном малом участке Δt, примыкающем к моменту t). • • • • Среднее число событий, наступающих на интервале времени h, следующем непосредственно за моментом t равно t+h a(t,h) ≡ EX(t,h) = ∫ λ(τ) d τ t Как видно из определения стационарности, если поток событий стационарен, то pk(t, h) = pk (h), и а(t,h) = а(h) Cледовательно λ(t) = λ = const, т.е. интенсивность стационарного потока постоянна и h а(h) = ∫ λ dt = λh. • • Наконец, отсутствие последействия можно формализовать так: Пусть pn-k,n (t,т) - вероятность того, что за время т, примыкающего к моменту времени t, появилось k событий при условии, что в момент времени t было n-k событий. Тогда условие отсутствия последействия означает, что p0,n (0,t+т) = p0,n-k (0,t) pn-k,n (t,т). Более просто отсутствие последействия можно записать, если рассматривать случайные величины вида ( Кстати,почему? ) X(t,h) ≡ X(t,t+h) ≡ <число событий на интервале (t,t+h) > = X[t,t+h] Тогда отcутствие последействия будет означать независимость X(a,b) и X(c,d) для любых непересекающихся (a,b) и (c,d) . • ТЕОРЕМА. Если поток событий- простейший, то распределение длин • интервалов Tn между любой парой соседних событий (т.е. для любого n)показательное (экспоненциальное) с параметром λ, равным интенсивности потока. T € Eλ ► Следующие постулаты вытекают из определения простейшего потока: 1) для всякого малого Δt > 0 существует ненулевая вероятность появления события; 2) если система начинает функционировать с момента t = 0 , то первое появление события имеет место в момент t > 0 . Рассмотрим функцию t p (t) = 1 - ∫ f(τ) dτ (2) Если f(τ) 0– плотность распределения интервала Tn, то p(t) = P { первое событие появилось после момента t}. Из свойства отсутствия последействия имеем: p (t +∆t) = p(t) p(∆t) Вычитая из обеих частей формулы p(t), получим p (t +∆t) - p(t) = - p(t) (1 - p(∆t)). Разделим обе части на Δt и перейдем к пределу по Δt: p (t +∆t) - p(t) 1 - p(∆t) lim = -p(t) lim ∆t ∆t ∆t →0 ∆t →0 Если пределы существуют, то полагая λ = lim 1 - p(∆t) > 0 , будем иметь p’(t) = - λ p(t), где p(0) = 1 t ∆t ∆t →0 t ➔ p(t) = e-λt ➔ e-λt = 1 - ∫ f(τ) dτ ➔ ∫ f(τ) dτ = 1 - e-λt ➔ f(τ) = λ e-λτ • • • • • • • • • • • • подставляя в (2) • Теперь соталось показать, что параметр распределения λ - не что иное, как интенсивность потока. Рассмотрим введённую в доказательстве функцию p(t) = 1 – FT(t) = p0(t) (вероятность, что в отрезке длины t не будет событий). Тогда в силу ординарности 1 - p(∆t) = p≥1(∆t) = p1(∆t) + o(∆t), и a(∆t) = p1(∆t) + o(∆t) - матожидание числа событий. Поэтому введённая ранее величина - равна интенсивности потока. ◄ λ = lim 1 - p(∆t) = lim a(∆t) ∆t →0 ∆t →0 ∆t ∆t ТЕОРЕМА Случайная величина числа событий на отрезке длины h в простейшем потоке распределена по закону Пуассона с параметром λh: X(h) € Пλh Д-ВО P (X(h)=k) ≡ pk(h) = P {T0+T1+…+Tk-1 < h, T0+T1+…+Tk > h} = | Рассмотрим T(n) = T0+…+ Tn - сумма n независимых случайных величин с показательным распределением с параметром λ. Мы знаем, что T(n) имеет распределение Гλ,n (Следствие из теоремы о свёртке.) Обозначим Ahn ≡ {T(n) < h} ⊂ Ahn-1 . Тогда P(Ahn) = Гλ,n (h) . | = P(Ahk-1(Ω\Ahk)) = P (Ahk-1\Ahk)= P(Ahk-1) – P(Ahk) = h h . λk λk+1 k -λt k-1 -λt =∫ t e dt - ∫ t e dt = Г(k)=(k-1)! k! h λ k-1 = - λ tk-1 e-λt +∫ k! (k-1)! = ∫ λe-λt tk-2 e-λt dt m dt - Σ (λh) e-λh m=1 m! Замечание. u = tn-1 / (n-1)! ( ) k+1 k-1 * интегрируем по частям, такие замены: h (∫ du = tn-2 / (n-2)! - (*) = dv = λn e-λt dt , v = -λn-1e-λt k λe-λt dt - Σ n=1 (λh)ne-λh ) = n! (λh)k e-λh k! ▄ Теперь можно легко доказать обратное утверждение: если в потоке число событий на любом интервале распределено по такому закону, то поток простейший. (Кстати, как?) Опр Потоком Пуассона называется ординарный поток без последействия. Простейший поток является частным случаем пуассоновского, а именно когда характеристика интенсивности постоянна λ(t) = λ. ТЕОРЕМА (о преобразовании временной оси простейшего потока). Пусть поток Пуассона {Θ1,Θ2,…} имеет интенсивность λ(t). Тогда подействуем на него преобразованием t Λ(t) = ∫λ(τ)dτ , которое переводит произвольно взятый интервал (a,b) временной оси в b (Λ(a), Λ(b)) ≡ (Λ(a), Λ(a) + Λ(a,b-a)) , где Λ(a,b-a) ≡ ∫λ(t)dt . a Полученный поток событий {Λ(Θ1), Λ(Θ2),…} будет простейшим с единичной интенсивностью, и существует обратное преобразование Λ-1. Д-ВО • • • • • Рассмотрим произвольный пуассоновский поток. Заметим, что при «искажении времени» под действием Λ для любого ω (эл.исх.) Θn+1(ω) Λ(Θn+1(ω)) - Λ(Θn(ω)) = ∫ λ(t) dt ≡ Λ(Θn(ω), Θn+1(ω)) Θn (ω) Также заметим, что Λ(x) – монотонно возрастает, если всюду кроме счётного числа точек λ(t)>0. Но если бы было λ(t) = 0 на некотором интервале, то это бы означало наличие последействия. (Почему?) Поэтому λ(t) >0 почти всюду, и в силу этого существует Λ-1(x), и Θn+1(ω) – Θn(ω) = τ ➔ Λ(Θn+1(ω)) - Λ(Θn(ω)) = tt+τ∫ λ(t) dt Θn ∈ (a,b) ➔ Λ(Θn(ω)) ∈ (Λ(a), Λ(b)) = (Λ(a), Λ(a) + Λ(a,b-a)), следовательно (*) pk(t,h) = p’k(Λ(t), Λ(t+h)≡ Λ(t) + Λ(t,h)) - вероятность в преобразованном потоке, из чего легко показать сохранение отсутствия последействия. Также p>1(t, ∆t) = p’>1(Λ(t), Λ(t, ∆t)) ➔ Для ординарности остаётся показать, что для любого t o(∆t) = o(Λ(t, ∆t)) Λ(t, ∆t) = t ∆t ∫ λ(t) dt ➔ • • • • ➔ ∆t min λ(t) = c1 ∆t ≤ Λ(t, ∆t) ≤ c2 ∆t = ∆t max λ(t) , o(c1∆t) ≤ o(Λ(t, ∆t)) ≤ o(c2 ∆t) = o(∆t). Заметим, что эти рассуждения работают и в обратную сторону, т.е. Λ-1(t) тоже сохраняет эти свойства, • т.е. пуассоновость потока. Теперь рассмотрим простейший поток с интенсивностью 1. Для произвольно выбранного интервала между двумя соседними событиями T(t) (t - начало) P (T(t) ≥ h) = P(T ≥ h) = 1 - FT = e-h P (T(t) ≥ Λ(t,h)) = e-Λ(t,h) В силу (*) это равносильно P (Λ-1(T(t)) ≥ h) = e-Λ(t,h) - вероятность для соответствующего интервала в новом пуассоновском потоке, полученном преобразованием времени Λ-1(t). • • • • • • t+∆t В силу (*) в новом потоке p’1 (Λ-1(t), ∆t) = p1 (t, Λ(t, ∆t)) ≈ 1 · Λ(t, ∆t) = ∫λ(τ)dτ - в старом потоке. Поэтому интенсивность нового t+∆t потока λ’(Λ-1(t)) = lim p’ (Λ-1(t),∆t) = lim ∫ λ(τ)dτ = λ(t) 1 t ∆t →0 ∆t ∆t →0 ∆t ординарность И тогда t+h Λ(t,h) = ∫λ(τ)dτ =a(t,h) - среднее число событий на интервале в новом t пуассоновском потоке, и число событий на интервале в нём распределено по закону Пa(t,h) Преобразованием Λ(t) получим из этого пуассоновского потока исходный простейший поток с единичной интенсивностью ▄ СЛЕДСТВИЕ 1 Число событий на интервале времени в потоке Пуассона имеет распределение Пуассона с параметром a(t,h) ( ≡ EX(t,h) ) k P( X(t,h)=k) = (a(t,h)) e-a(t,h) k! СЛЕДСТВИЕ 2 В пуассоновсом потоке вероятность отсутствия событий на интервале (t, t+h) p0(t,h) = e-a(t,h) • ТЕОРЕМА Cумма (суперпозиция) n пуассоновских потоков с интенсивностями λ1(t),…,λn(t) есть пуассоновский поток с интенсивностью λ(t) = Σ λi(t) . (В сумме все события из всех потоков в те же моменты времени) Д-ВО: Достаточно доказать для n = 2 . Покажем ординарность суммы, ввиду p1(t,∆t) ≤ O(∆t) : (порассуждать почему, от противного) pΣk (t,∆t) = p1k(t,∆t) p20(t,∆t) + p1k-1(∆t) p21(∆t) + …+ p11(∆t) p2k-1(∆t) + p10(∆t) p2k(∆t) = = o(∆t) p20(t,∆t) + o(∆t) p21(∆t) + o(∆t) o(∆t) +…+ o(∆t) o(∆t) +p11(∆t) o(∆t) + p10(∆t) o(∆t) = o(∆t) для любого k ≥ 2 (Отсутствие послед-я можно доказать, если расписать в условной вероятности i P(XΣ(a,b)=n | XΣ(c,d)=m) события «XΣ… = i » как « U (XI = k , XII = i - k) » ) k=0 ▄ • • СЛЕДСТВИЕ Сумма n простейших потоков с интенсивностями λ1, …, λn есть простейший поток событий с интенсивностью λ = λ1+ …+ λn . Замечание Стационарность суммы простейших потоков следует из постоянства его интенсивности. Также можно доказать это утверждение самостоятельно, исследовав распределение для числа событий на интервале. • • ТЕОРЕМА (p-преобразование, оно же - расщепление простейшего потока) В простейшем потоке интенсивности λ последовательно проделаем следующее: каждому событию с вероятностью p будем присваивать цифру 1 (как новый индекс). Всем не переименованным данной операцией событиям присвоим цифру 2. Из событий с цифрой 1 составим новый поток событий, а из событий с цифрой 2 другой поток событий. Утверждается, что таким образом поток разбивается на два независимых простейших потока с интенсивностями pλ и (1-p)λ. • • Д-ВО – домашняя работа, семинар #4. • УТВЕРЖДЕНИЕ Если в простейшем потоке известно, что за время (0,t] произошло ровно n событий (это событие A вероятностного пр-ва), то моменты наступления этих событий Θ1(ωϵA), Θ2(ω), … Θn(ω) соответствуют статистической выборке равномерного распределения Uo,t. Проще говоря, апостериорное (условное) распределение FΘi | X(0,t) = n = U0,t для каждого 1≤ i ≤ n. УТВЕРЖДЕНИЕ Рассмотрим два независимых простейших потока с интенсивностями λ1 и λ2 соответственно. Вероятность, что n событий первого потока наступит раньше m событий второго потока равна n+m-1 P(Θ(1)n< Θ(2)m) = Σ Ckn+m-1( k=n λ1 .)k ( λ2 . )n+m-1-k λ1+λ2 λ1+λ2 • • • Опеделение. Ординарный поток событий называется потоком с ограниченным последствием, если интервалы времени Tn между последовательными событиями представляют собой независимые случайные величины. Если эти случайные величины одинаково распределены, то такой поток называется потоком Пальма, или рекуррентным потоком. В связи с одинаковостью распределений T поток Пальма всегда стационарен. Простейший поток является частным случаем потока Пальма; в нём интервалы между событиями распределены по показательному закону Eλ,где λ—интенсивность потока. УТВЕРЖДЕНИЕ 1. Поток Пальма стационарен. • УТВЕРЖДЕНИЕ 2. Поток Пальма ординарен. • • ТЕОРЕМА. (выражение интенсивности в рекуррентном потоке (Пальма)) В потоке Пальма λ = 1/ET. СЛЕДСТВИЕ То же верно для интенсивности простейшего потока. • Д-ВО теоремы основано на законе больших чисел: • Действительно, давайте рассмотрим предел отношения отрезка времени к числу событий в потоке, произошедших за этот отрезок: T1 +…+ Tn = ET T→∞ n -1 n→∞ С другой стороны, если помножить левую и правую части на интенсивность λ lim T / X(T) = lim • • lim λT / X(T) = lim EX(T) / X(T) = T→∞ T→∞ снова ЗБЧ • = lim • • n→∞ ➔ • EX(T1+...+Tn) = lim nEX(T1) X(T1) +…+ X(Tn) n → ∞ X(T1) +…+ X(Tn) λ = 1 ET ▄ = EX(T1) EX(T1) = 1 = λ ET • Опр. • Потоком Эрланга k-го порядка называется поток событий, получающийся «прореживанием» простейшего потока, когда сохраняется каждая k-я точка (событие) в потоке, а все промежуточные выбрасываются. (На рис. показано по лучение потока Эрланга 4-гопорядка из простейшего потока). Интервал времени T между двумя соседними событиями в потоке Эрланга k-го порядка представляет собой сумму k независимых случайных величин Т1,Т2 ,... ,Тк, имеющих показательное распределение с параметром λ – интенсивность простейшего потока. Из этого следует, что поток Эрланга является пальмовским потоком и стационарен. • • • • • Найдём плотность закона распределения T ≡ T(k) для потока Эрланга k-го порядка. Для этого рассмотрим простейший поток с интенсивностью λ и найдём элемент вероятности fT(k)(t)dt = P ((T(k) = ΣTi) ∈ (t, t+dt)) Событие в скобках произойдёт, когда на интервал от [0,t] попадёт k-1 точка (событие) и на интервал (t, t+dt) - k-я точка. Поэтому, и в виду отсутствия последействия k-1 fT(k)(t)dt = pk-1(t) p1(dt) = (λt) e-λt · λdt (k-1)! k-1 ➔ fT(k)(t) = λ(λt) e-λt (t>0) . (k-1)! • • • • • • • • • Так как интервал T(k) между соседними событиями в потоке Эрланга k-го порядка, полученном из простейшего интенсивности λ c интервалами Ti равен j+k T(k) = Σ Ti = k T ➔ ET(k) = kETi = k / λ ➔ i= j+1 Интенсивность потока Эрланга k-го порядка λ(k) = 1/ET(k) = λ / k → 0 (при k → ∞ ) Теперь заметим, что если произвести с потоком «операцию увеличения масштаба в k раз», то есть сопоставить каждой реализации потока {Θ1(ω), Θ2(ω), …} бесконечномерный вектор {Θ1(ω) = Θ1(ω)/k , Θ2(ω) = Θ2(ω)/k , … }, то так же пропорционально уменьшатся интервалы T(k), и ET(k) = ET(k)/ k = 1/λ. Назовём такой поток нормированным потоком Эрланга k-го порядка. fT(k)(t) = λk(λkt)k-1e-λkt (k-1)!(k) и дисперсия T(k) равна DT = 1 / kλ2 (= DT(k) / k2 = kDT / k2 = (k / λ2) /k2 = 1 / kλ2) В виду того, что DT(k) → 0 при k → ∞ , длины интервалов стремятся к постоянному значению T(k) → C = ET = 1/λ. Это свойство потоков Эрланга удобно в практических применениях: оно даёт возможность, задавая различные k, получать потоки с разной степенью последействия: от полного отсутствия при k = 1, до жесткой функциональной зависимости между моментами появления событий (k = ∞) • • • • • • • В целях упрощения часто бывает удобно приближенно заменить реальный пальмовский поток событий - потоком Эрланга с той же степенью последействия. Это делают, согласовывая характеристики реального потока – матожидание и дисперсию интервала между событиями - с теми же характеристиками заменяющего потока Эрланга. Пример Исследуется срок эксплуатации ламп уличного освещения. В процессе статистической обработки (за десятилетия наблюдений) интервалов между событиями в потоке выходов из строя (и замены) получены следующие характеристики: - среднее значение интервала между событиями Tсредн. = 2 года ~ ЕT. - среднее квадратическое отклонение интервала σT = 0,9 лет ~ √DT. Подобрать нормированный поток Эрланга, обладающий приблизительно теми же характеристиками, что и этот поток. Каков порядок потока Эрланга, какова интенсивность? Решение λ = 1 / ET = 1/2 , с другой стороны ½ = λ = 1 / √ (k DT) Подставляем вместо дисперсии среднеквадратич. откл –е σT = 0,9 лет ➔ √ k = 2 / 0.9 ➔ k = (20 / 9)2 = 400 / 81 Подбираем самое близкое натуральное значение k = 5 Замечание Потоки с ограниченным последействием также иногда называют потоками восстановления. (Смысл этого термина раскрывает постановка задачи, когда событием на потоке является очередной отказ оборудования (системы) и замена его на новое с известной функцией распределения времени безотказной работы.) • Далее решим несколько задачек, углубляющих понимание нашего курса. • Задача (о футболе). (частный случай одного из утверждений про простейшие потоки) • Две футбольные команды A и B играют матч. Команда A забивает голы подобно простейшему потоку событий интенсивности λA=2, а команда B подобно простейшему потоку интенсивности λB=3. Какова вероятность того, что команда B забьёт гол первой в этом матче? • Решение (не является единственно возможным) – след. слайд • • • • • • • Введём события C1 : «первый гол забивает команда B», C2 : «первый гол успеют забить за 90 минут». Очевидно, что условная вероятность P(C1|C2) есть искомая вероятность. Заметим, что С1 C2 означает что «во втором потоке первое событие наступит раньше, чем в первом, и хотя бы в одном из потоков первое событие произойдёт в течение 90 минут». Здесь может возникнуть соблазн заменить С2 на С2’ : «команда В успевает забить гол за 90 минут». Тогда C1C2 = C1C2’ , но тогда будет совершенно другая условная вероятность. Знаем, что вероятность одного события на малом интервале ∆t в простейшем потоке равна p1(t, ∆t) = λ∆t + o(∆t), т.е. приблизительно равна p1(t, ∆t) ≈ λ∆t . Отсутствие события на том же интервале имеет вероятность p0(t, ∆t) ≈ 1-λ∆t . А вероятность того, что событий не будет на заданном интервале p0(t, h) = e-λh . Рассмотрим последовательность несовместных событий вида: { Ak: «вплоть до момента времени kΔt никто не забил ни одного гола, а в интервале [kΔt, (k+1)Δt) гол забила команда В, а команда A так и не забила» }. Очевидно, что сумма (объединение) всех событий UAk при Δt → 0 приближается по вероятности к событию C1C2, т.е. при переходе к пределу при Δt → 0 сумма становится интегралом и он равен вероятности P(C1C2) . По тому же принципу можно вычислить и P(C2) (вспомнить теорему о сумме простейших потоков). • 90 P(C1C2) P(C1|C2) = = P(C2) ∫ e--λAt (1-λAdt) e--λBt λBdt 90 ∫ e--(λA+λB) t (λ +λ )dt A B = λB = 3 (λA +λB) 5 Заметим, что при раскрытии скобок членом с dt2 пренебрегаем как малым слишком высокого порядка, который даст после интегрирования величину порядка O(dt). Задача (о пожарной станции). На пожарную станцию поступают звонки с вызовами как простейший поток с интенсивностью λ = ½ за час. Каждый раз пожарной бригаде нужно определённое время, чтобы разобраться с вызовом и приготовиться к следующему. Приходящие в это время вызовы перенаправляются на другие станции. Длительности этих периодов работы распределены равномерно на интервале от получаса до часа и независимы. Найти какая часть от общей массы вызовов (в длительной перспективе) будет перенаправлена на другие пожарные станции. Решение а = Начало, когда последний вызов и конец когда закончили тушить пожар Для наглядности удобно сделать следующий рисунок-схему tF Имеет распределение U1/2;1 Tc имеет распределение E1/2 лямбда=1/2 a на которой сверху изображён простейший поток событий, где событиями являются все звонки-вызовы, адресованные на пожарную станцию, а снизу поток принятых вызовов, в котором интервалы между событиями состоят из времени борьбы с огнём и времени ожидания: T = tF + tw Если учесть, что интервалы между вызовами в простейшем потоке распределены по экспоненциальному закону, то воспользовавшись свойством отсутствия памяти для экспоненциального распределения легко покажем, что промежутки времени ожидания tw распределены по тому же экспоненциальному закону(поэтому нижний поток будет пальмовским!). • • • Итак, свойство отсутствия памяти экспоненциального распределения (см. утверждение из Гл. 0) означает, что для любой случайной величины X, подчиняющейся этому закону: P(X ≥ a+b | X ≥ a) = P (X ≥ b) Тогда, пользуясь экспоненциальностью интервалов между событиями в потоке всех звонков имеем: P(Tc ≥ a+b | Tc ≥ a) = P (Tc ≥ b) ➔ P[ (Tc- a) = tw ≥ b | (Tc- a) = tw ≥ 0 ] = F Tc(y) - равно вероятности что Tc меньше y в силу неотрицательности времени ожидания = P(tw ≥ b) = P (Tc ≥ b) - эквивалентно равенств функций распределений => Ftw = FTc С другой стороны, это равносильно равенству функций распределения tw и Tc • После этого легко видеть, что поток принятых вызовов является пальмовским, из чего немедленно следует его стационарность, а в стационарном потоке ожидаемое число событий на интервале равно произведению длины интервала на интенсивность, и, поэтому долю принятых вызовов найдём как отношение интенсивностей двух потоков. А интенсивность потока принятых вызовов вычислим по известной нам формуле λпр.выз. = 1/ET = 1/ (EtF +Etw). • Как далее станет ясно, в этой задаче мы имеем дело с примером самой настоящей системы массового обслуживания(и, кстати, не самым тривиальным) Задача (#3, про магазин) Магазин работает с 1000 до 1800. Посетители прибывают в магазин соответственно потоку Пуассона с функцией интенсивности λ(t), равной нулю в момент открытия магазина, 4-ём (посетителям/час) в полдень, 6 в 1400, 2 в 1600 и снова 0 в момент закрытия. Функция линейна всюду между этими моментами. Найти: а) распределение для числа посетителей в данный день; б) вероятность того, что до полудня не будет посетителей; в) ожидаемые моменты прибытия первых двух посетителей, если дополнительно предполагается, что до полудня будут двое и только двое; г) ожидаемое число покупок, если известно, что только каждый третий посетитель делает покупку. Решение. а) знаем, что число посетителей за 8 часов рабочего дня (обозначим его X) 18 имеет распределение Пуассона с параметром a(10,8) = ∫λ(t)dt 10 18 12 14 16 18 EX(10,8) = a(10,8) = ∫λ(t)dt = ∫λ(t)dt + ∫λ(t)dt + ∫λ(t)dt + ∫λ(t)dt = 10 10 12 14 16 интеграл линейной функции как площадь трапеции ½ (λ(10)+ λ(12))(12-10) + ½ (λ(12)+ λ(14))(14-12) + …+ ½ (λ(16)+ λ(18))(18-16) = = ½ ( (0+4)*2 + (4+6)*2 + (6+2)*2 + (2+0)*2 ) = ½ ( 8 + 20 + 16 + 4 ) = 24 ➔ X € П24 б) p0(10, 2) = e–a(10,12) = e–4 ≈ 0,018 a(10,2)= ∫λ(t)dt = знаем,что λ(t) линейна на этом интервале 10a+b = 0 12a+b = 4 a=2 ➔ b = -20 = ∫(2t-20)dt = -4 = в) чтобы найти матожидание момента прибытия второго посетителя Θ2 , найдём функцию распределения и плотность для Θ2 (при условии, что N(12)=2) для краткости введём Так как P (Θ2 < y) = P( N(y) ≥ 2) обозначение P (N(y) ≥ 2 , N(12)=2) F Θ2 | N(12)=2 (y) = P (N(y) ≥ 2 | N(12)=2) = = N(y) ≡ X(10,y-10) P(N(12)=2) т.е.«всего ранее y» ∞ ΣP (N(y) = i , X(y,12-y) =2-i) P (N(y) = 2 , X(y,12-y) =0) P(N(y)=2)P(X(y,12-y) =0) = = = i=2, P(N(12)=2) P(N(12)=2) P(N(12)=2) (2-i) ≥ 0 ( a(10,y-10) = ∫λ(t)dt )2 = - a(10,y-10) · 2! e t2-20t - a(y,12-y) · e 2 t= y t= 10 - a(10,2) · = 42 / 2! · e –a(10,2) e –a(10,2) · ( a(10,2) )2 / 2! e = 2 2 4 = ( y – 20y -100+200 ) = (y-10) 16 FΘ2 -10 | N(12)=2 (y) = 16 y4 16 fΘ2 -10 | N(12)=2 (y) = E(Θ2 -10 | N(12)=2) = ∫ t · t3/4 dt = t5/20 t= 2 t= 0 = 8 5 ➔ y3 4 E(Θ2 | N(12)=2) = 10+8/5 = 11:36 F Θ1 | N(12)=2 (y) = P (N(y) ≥ 1 | N(12)=2) = = P (N(y) = 1 , N(12)- N(y) =1) +P (N(y) = 2 , N(12)- N(y) =0) = P(N(12)=2) (y-10)2 (y-10)4 2 16 • ➔ F Θ1-10 | N(12)=2 (t) = t2 t4 2 - 16 E(Θ1 -10 | N(12)=2) = 1 1/15 г) подумать над этим ➔ f Θ1-10 | N(12)=2 (t) = t - t3 4 E(Θ1 | N(12)=2) = 11:04 • Лемма. p-преобразование стационарного потока сохраняет стационарность. Утверждение. После p–преобразования поток событий Пальма интенсивности λ переходит в поток Пальма интенсивности λp. • • Задача (#4, про инспекторов) На предприятии есть оборудование, которое согласно технике безопасности каждый год должно проходить частичное обновление (замену определённого модуля, либо иные профилактические работы). Периодически приезжает инспектор с проверкой, а именно через интервал, равномерно распределённый между 1 и 2,5 годами. Если обнаруживается, что профработы не проводились более года, то владелец предприятия платит штраф, равный 105 неких денежных единиц. Владелец предприятия считает требования инспекции завышенными, поэтому стратегия на предприятии сводится к следующему: заменять модуль ровно спустя год после очередной проверки. Посчитать среднее значение штрафных выплат в год. • Решение Рассмотрим два потока событий в совокупности:«поток инспекторов» и «поток инспекторов с чемоданчиками» (те, когда выписывают штрафы). • Сразу видим, что поток инспекторов – пальмовский. И если рассматривать его как последовательность событий , то каждое следующее за Θi событие Θi+1 переходит в «поток инспекторов с чемоданчиками», если и только если следующий заΘi интервал Ti > 2, и вероятность этого равна 2,5 2,5 • P(Ti > 2) = ∫ u1 ; 2,5 dτ = ∫ 2/3 dτ = 1/3 • Но такое преобразование «потока инспекторов» нельзя путать с p-преобразованием, потому что тут выбор события зависит от длины предшествующего интервала. Тем не менее, из рисунка легко видеть, что сдвиг потока «инспекторов» относительно оси координат к обозначенной черте влияет лишь на выбор первого после черты события, поэтому поток «инспекторов с чемоданчиками» наследует стационарность пальмовского потока «инспекторов». • В силу стационарности, для любого периода времени T 2 | | λ = 2 t+T EX (T) E[BX(T),p] E[X(T) p] p E[X(T)] p t∫ λ dτ pλT Здесь нужно пояснить, = = = = = = λp T T T T T T что p–преобразование можно рассматривать как серию из двух вероятностных экспериментов: первый определяет «поток инспекторов», а второй – «п. инспекторов с ч.» ➔ Отсюда t+1 | | 3 105 { EX (1) = ∫ λ dτ = λp = (1/ET) p = ( 1 / 1 ) 1/3 = 4 /21 }«матожидание матожидания» 4 = 20 t • «Матожидание матожидания» требует дополнительного обоснования. Если избегать «матожидания матожидания», то можно говорить о соотношении | | | E[T1+…+Tk] и E[X (k)] , где X (k) ≡ X (T(k)) означает число событий в потоке «с чемоданчиками», которое соответствует k событиям из п.с. «инспекторов» | Здесь легко видеть, что X (k) – снова биномиальная величина Bk,p и, по определению • X ( T1+…+Tk) ≤ X (k) ≡ X (T(k)) ≤ X ( T1+…+Tk+1) , также заметим, что для любого m | | | | | | | X (k + m) ≤ X ( T(k) +T1+…+Tm ) ≤ X (k + m + 1) И мы можем всегда вычислить | • E[X (n)] = E[Bn,p] = np = n/3 этому количеству событий-чемоданчиков в среднем (в некотор. смысле) предшествует E[T1+…+Tn] = n ET = n (1+2,5)/2 = 7/4 n лет работы инспекторов. • Тогда в силу стационарности п.с. «с чемоданчиками» предел отношения n = k+m | | | | 4 = lim E[X (n)] EX (T(k) + Tk+1+…+Tk+m) = lim EX (T(k)) + EX (Tk+1+…+Tk+m) ≤ lim m→∞ m→∞ 21 n → ∞ E[T +…+T ] E[T1+…+Tk+m] (k+m)ET 1 n | | | | EX (ET1) λ ET1 E[X (n+1)] (n+1) /3 4 = = = λ ≤ lim = lim = ET ET 21 n → ∞ E[T1+…+Tn] n → ∞ 7/4 n ЗБЧ и стационарность ▄ • Утверждение Пусть дан поток Пуассона P c интенсивностью λ(t), тогда P ∩ (T,+∞) – это поток | Пуассона с интенсивностью λ (t) = λ(t+T). (Просто «отрезали начало») • • Задача (#5, про нашествие зомби). Интенсивность пуассоновского потока λ(t)= 1/1+t . Найти распределения первых двух интервалов T0 и T1. (Если ET1 > 2 , то ружьё) • y Решение. 1 -∫1+u du 1 – FT0(y) = P (T0≥y) = P (T0>y) = P( N(y)=0 ) = e = ➔ fT1(t) = 1 (1+t)2 -v(t) Находим безусловную вероятность: y ∞ ∞ = ∫ (1 0 ∫ ∞ y fT1 | T0(s | t) fT0 (t) dt ds = 0 0 ∞ 1+ t ) fT0 (t) dt = 1 - ∫ 1+ t +y ➔ fT1 (t) = (1+t) ln(1+t) - t t2(1+t) 2 P(T1 < 2 ) = ∫ fT1 (t) dt ≈ 0,45 = 1+y ➔ . Тогда, учитывая утверждение на прошлой странице 1 – FT1 | T0(y) = P(T1 ≥ y | T0) = P (T1 > y | T0) = P(X(T0,y)=0) = exp FT1 (y) = ∫ 1 v’(t) =1+t ∫ ∫ fT1 | T0(s | t) fT0 0 0 ∞ 1+ t f (t) dt = 1 1+ t +y T0 Матожидание - ? ∫ T0+y dt (- 1+t T0 ∫ )= 1+T0 1+T0+y ln 1+T0+y 1+T0 (t) ds dt = 1 . dt = 1 - ln(1+y) (1+t)(1+ t +y) y