<<
>>

ГЛАВА 10потоки событий. марковские случайные процессы

Потоком событий называется последовательность однородных событий, появляющихся одно за другим в случайные моменты времени. Примеры: поток вызовов на телефонной станции; поток забитых шайб при игре в хоккей; поток сбоев ЭВМ; поток заявок на проведение регламентных работ в вычислительном центре и т.п.

Поток событий наглядно изображается рядом точек с абсциссами 61? G2,..., 6П,...

(рис. 10.0.1) с интервалами между ними: 7] = ©2 — ©1? Т2 = ©З — ©2, ..., ТП = ©п+1 — ©п.При его вероятностном описании поток событий может быть представлен как последовательность случайных величин: ЄГ; ©2 = ©j + 7J; ©з = ©j + ТХ + Т2; ... .

Заметим, что термин «событие» в понятии «поток событий» совершенно отличен по смыслу от ранее введенного термина «случайное событие». В частности, не имеет смысла говорить о вероятностях «событий», образующих поток (например, о «вероятности вызова» на телефонной станции; ясно, что рано или поздно вызов придет, и не один). С «потоком событий» можно связывать различные случайные события, например: А = {в течение времени от t0 до ^ 4- т придет хотя бы один вызов}

или

В = {в течение того же времени придут ровно два вызова}.

Вероятности таких событий можно вычислять.

Заметим также, что на рисунке в виде ряда точек можно изобразить не сам поток событий (он случаен), а только какую-то его конкретную реализацию.

В гл.

5 упоминалось о потоках событий и некоторых их свойствах; здесь осветим их более подробно. Поток событий называется стационарным, если его вероятностные характеристики не зависят от выбора начала отсчета или, более конкретно, если вероятность попадания того или дру- Тх Т2 Т3 Т4

Тп

Рис. 10.0.1

0©1 ©2 ©з епе

t

п+1 т 1

1 ¦ • 1 1 1 1

1 1 1 1

j 0 ©1 ©2@3 " ©п Рис. 10.0.2

гого числа событий на любой интервал времени зависит только от длины т этого интервала и не зависит от того, где именно на оси Ot он расположен.

Поток событий называется ординарным, если вероятность попадания на элементарный интервал времени At двух или более событий пренебрежимо мала по сравнению с вероятностью попадания одного события.

Практически ординарность потока означает, что события в нем появляются «поодиночке», а не группами по два, по три и т.д. (точное совпадение моментов появления двух событий теоретически возможно, но имеет нулевую вероятность).

Ординарный поток событий можно интерпретировать как случайный процесс X(t) — число событий, появившихся до момента t (рис. 10.0.2). Случайный процесс X(t) скачкообразно возрастает на одну единицу в точках61? 02,©п.

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

Поток событий называется простейшим, если он стационарен, ординарен и не имеет последействия.

Интервал времени Г между двумя соседними событиями простейшего потока имеет показательное распределение

f(t) = Хе~х' (при t> 0), (10.0.1)

где X = 1 / М[Т) — величина, обратная среднему значению интервала Т.

Ординарный поток событий без последствия называется пуассонов- ским. Простейший поток есть частный случай пуассоновского (а именно стационарный пуассоновский поток).

Интенсивностью X потока событий называется среднее число (математическое ожидание числа) событий, приходящееся на единицу времен- ни. Для стационарного потока X = const; для нестационарного потока интенсивность в общем случае зависит от времени: \ = \(t).

Мгновенная интенсивность потока \(t) определяется как предел отношения среднего числа событий, которые произошли за элементарный интервал времени (t, t + At), к длине At этого интервала, когда она стремится к нулю. Среднее число событий, наступающих на интервале времени т, следующем непосредственно за моментом t0 (см. рис. 10.0.1), равно

t о+т

a т) = J \(t) dt Если поток событий стационарный, то а т) =

to

= а (т) = Хт.

Ординарный поток событий называется потоком Пальма (или рекуррентным потоком, или потоком с ограниченным последствием), если интервалы времени Tv Т2,...между последовательными событиями (см.

рис. 10.0.1) представляют собой независимые, одинаково распределенные случайные величины. В связи с одинаковостью распределений Tv Т2,... поток Пальма всегда стационарен. Простейший поток является частным случаем потока Пальма; в нем интервалы между событиями распределены по показательному закону (10.0.1), где X — интенсивность потока.

Потоком Эрланга k-го порядка называется поток событий, получающийся «прореживанием» простейшего потока, когда сохраняется каждая к-я точка (событие) в потоке, а все промежуточные выбрасываются (на рис. 10.0.3 показано получение потока Эрланга 4-го порядка из простейшего потока).

Интервал времени между двумя соседними событиями в потоке Эр-ланга к-то порядка представляет собой сумму к независимых случайных величин Ту, Т2,..., Тк, имеющих показательное распределение с параметром X:

Т = J2Ti- (10.0.2)

і =і

Закон распределения случайной величины Тназывается законом Эр-ланга k-го порядка (см. задачу 8.3) и имеет плотность

№ = 7Г^ТГ е"Х' 1 > V- (10-0-3) (fc-І)!

Математическое ожидание, дисперсия и среднее квадратическое отклонение случайной величины Т (10.0.2) соответственно равны:

mt —k/\ Dt = k / X2; a, = Jk / X. (10.0.4)

Коэффициент вариации случайной величины (10.0.2) равен

Ц =Gt / mt =1/ ylk; (10.0.5)

vt —> 0 при k —> оо, т.е. при увеличении порядка потока Эрланга «степень случайности» интервала между событиями стремится к нулю.

Если одновременно с «прореживанием» простейшего потока изменять масштаб по оси 0t (делением на к), получится нормированный поток

Т

х <=)—• 1

-М '

о '—r-M-r-V

тх т2 т3 т4 Чпг,

^(настоящее) Рис. 10.0.4

Эрланга А;-го порядка, интенсивность которого не зависит от к. Ин-тервал времени Т между соседними событиями в нормированном потоке Эрланга А;-го порядка имеет плотность Ш) = (при (10-0-6)

Числовые характеристики случайной величины

і к

к ^

К і =1

равны:

М\Т\=1/\ D\T\=l/k\2] dt=l /(Хл/fc); vt=l/yfk.

(10.0.7)

При увеличении А; нормированный поток Эрланга неограниченно приближается к регулярному потоку с постоянным интервалом I = 1 / X между событиями.

Случайный процесс, протекающий в какой-либо физической системе 5, называется марковским (или процессом без последствия), если он обладает следующим свойством: для любого момента времени ^ (рис. 10.0.4) вероятность любого состояния системы в будущем (при t > і^) зависит только от ее состояния в настоящем (при t=t^) и не зависит от того, когда и каким образом система S пришла в это состояние (иначе: при фиксированном настоящем будущее не зависит от предыстории процесса — от прошлого). «1

Рис. 10.0.5

В данной главе будем рассматривать только марковские процессы с дискретными состояниями sl, s2, ...sn. Такие процессы удобно иллюстрировать с помощью графа состояний (рис. 10.0.5), где прямоугольниками (или кружками) обозначены состояния sv s2, ... системы 5, а стрелками — возможные переходы из состояния в состояние (на графе отмечаются только непосредственные переходы, а не переходы через другие со-стояния). Иногда на графе состояний отмечают не только возможные переходы из состояния в состояние, но и возможные задержки в прежнем состоянии; это изображается стрелкой («петлей»), направленной из данного состояния в него же (рис. 10.0.6), но можно обходиться и без этого. Число состояний системы может быть как конечным, так и бесконечным (но счетным).

4

Рис. 10.0.7

Марковский случайный процесс с дискретными состояниями и дискретным временем обычно называют марковской цепью. Для такого процесса моменты tv t2, ..., когда система 5 может менять свое состояние, удобно рассматривать как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, рассматривать не время t, а но-мер шага: 1, 2,.., к, • • • • Случайный процесс в этом случае характеризуется последовательностью состояний

5(0), 5(1), 5(2),...,5(*),..., (10.0.8)

если 5(0) — начальное состояние системы (перед первым шагом); 5(1) — состояние системы непосредственно после первого шага; ...; S(k) — со-стояние системы непосредственно после к-то шага ....

Событие {S(k) = s{ } = {сразу после к-то шага система находится в состоянии st) (г = 1, 2,...) является случайным событием, поэтому последовательность состояний (10.0.8) можно рассматривать как последовательность случайных событий. Начальное состояние 5(0) может быть как заданным заранее, так и случайным. О событиях последовательности (10.0.8) говорят,что они образуют марковскую цепь.

Рассмотрим процесс с п возможными состояниями sl5 s2,..., sn. Если обозначить X(t) номер состояния, в котором находится система 5 в момент t, то процесс (марковская цепь) описывается целочисленной случайной функцией X(t) > 0, возможные значения которой равны 1,2,..., п. Эта функция совершает скачки от одного целочисленного значения к другому в заданные моменты tv t^,... (рис. 10.0.7) и является непрерывной слева, что отмечено точками на рис. 10.0.7.

Рассмотрим одномерный закон распределения случайной функции X(t). Обозначим через р{(к) вероятность того, что после А;-го шага [и до (к + 1)-го] система 5будет в состоянии s{ = (г = 1, 2,..., п). Вероятности Pi(k) называются вероятностями состояний цепи Маркова. Очевидно, для любого к

1>, (*) = !• (Ю.0.9)

і =1

Распределение вероятностей состояний в начале процесса

Р1(0),Р2(0),...,РД0),...,Р„(0) (10.0.10)

называется начальным распределением вероятностей марковской цепи. В частности, если начальное состояние 5(0) системы 5 в точности известно, например 5(0) = s{, начальная вероятность р{ (0) = 1, а все остальные равны нулю.

Вероятностью перехода на к-м шаге из состояния s{ в состояние s. называется условная вероятность того, что система 5 после к-то шага окажется в состоянии Sjf при условии, что непосредственно перед этим (после к — 1 шагов) она находилась в состоянии s{. Вероятности перехода иногда называются также «переходными вероятностями».

Марковская цепь называется однородной, если переходные вероятности не зависят от номера шага, а зависят только от того, из какого состояния и в какое осуществляется переход: (10.0.11)

Р {S(*) = e,|S (*-!) = в,} = Р«,. Переходные вероятности однородной марковской цепи Ру образуют квадратную таблицу (матрицу) размером п хп: Рп Р\2-- P\j••• Р\ П

ч

(10.0.12)

Рц ^22* ^2п

Рц Р{2'" Pij-" Pin

Р Р Р Р

п\ гп2nj''' пт (10.0.13)
= 1 (Г = 1, ..., П).
J=I Матрицу, обладающую таким свойством, называют стохастической. Вероятность Ри есть не что иное, как вероятность того, что система, пришедшая к данному шагу в состояние s{, в нем же и задержится на очередном шаге.

Если для однородной цепи Маркова заданы начальное распределение вероятностей (10.0.10) и матрица переходных вероятностей (10.0.12), то вероятности состояний системы Pi (к) (і = 1, 2,..., п) могут быть определены по рекуррентной формуле

Pi (*) = ? Pj(k - 1) P{j (і = 1, n; j = 1,..., n). (10.0.14)

j=і

Для неоднородной цепи Маркова вероятности перехода в матрице (10.0.12) и формуле (10.0.14) зависят от номера шага к.

Для однородной цепи Маркова, если все состояния являются существенными, а число состояний конечно, существует предел lim Р{ (и) = Р{:,

определяемый из системы уравнений ^^ «1 s4 п п

S2 23 Pi =Y1 pjpji и pi =1- сУмма переходів і =1 ных вероятностей в любой строке матрицы равна единице.

При фактических вычислениях по формуле (10.0.14) надо в ней учитывать не все состояния Sjt а только те, для которых пе- рис> Ю.0.8

реходные вероятности отличны от нуля,

т.е. те, из которых на графе состояний ведут стрелки в состояние s{.

Марковский случайный процесс с дискретными состояниями и непрерывным временем иногда называют «непрерывной цепью Маркова». Для такого процесса вероятность перехода из состояния s{ в s- для любого момента времени равна нулю. Вместо вероятности перехода P{j рассматривают плотность вероятности перехода \ij9 которая определяется как предел отношения вероятности перехода из состояния S- в состояние Sj за малый промежуток времени At, примыкающий к моменту t, к длине этого промежутка, когда она стремится к нулю. Плотность вероятности перехода может быть как постоянной (\{j = const), так и зависящей от времени [\„ = В первом случае марковский случайный процесс с дискрет

ными состояниями и непрерывным временем называется однородным. Типичный пример такого процесса — случайный процесс X(t), представляющий собой число появившихся до момента t событий в простейшем потоке (см. рис. 10.0.2).

При рассмотрении случайных процессов с дискретными состояниями и непрерывным временем удобно представлять себе переходы системы S из состояния в состояние как происходящие под влиянием некоторых по-токов событий; при этом плотности вероятностей перехода получают смысл интенсивностей \{j соответствующих потоков событий (как только происходит первое событие в потоке с интенсивностью \{j, система из состояния Si скачком переходит в Sj). Если все эти потоки пуассоновские (т.е. ординарные и без последствия, с постоянной или зависящей от времени интенсивностью), то процесс, протекающий в системе S, будет марковским.

Рассматривая марковские случайные процессы с дискретными состояниями и непрерывным временем, очень удобно пользоваться графом состояний, на котором против каждой стрелки, ведущей из состояния Si в Sj f проставлена интенсивность \{j потока событий, переводящего систему по данной стрелке (рис. 10.0.8). Такой граф состояний называют размеченным1*.

Вероятность того, что система S, находящаяся в состоянии sf, за элементарный промежуток времени (?, t+ dt) перейдет В состояние Sj (элемент вероятности перехода из s{ в s), есть вероятность того, что за это вреНа ірафе состояний системы с непрерывным временем мы не будем проставлять петли, соответствующие задержке системы в данном состоянии, так как такая задержка всегда возможна.

мя ^появится хотя бы одно событие потока, переводящего систему 5из s{ в SJ. С точностью до бесконечно малых высших порядков эта вероятность равна Xydt.

Потоком вероятности перехода из состояния s{ в Sj называется величина (t) (здесь интенсивность Ху может быть как зависящей, так и независящей от времени).

Рассмотрим случай, когда система S имеет конечное число состояний 52,..., 5П. Для описания случайного процесса, протекающего в этой системе, применяются вероятности состояний

•..,?„(*), (10.0.15)

где р{ (t) — вероятность того, что система SB момент t находится в состоя-нии S-:

Р,-(і) = Р {?(*) = *}. (Ю.0.16)

Очевидно, для любого t

?>i(t) = l- (10.0.17)

і =1

Для нахождения вероятностей (10.0.15) нужно решить систему дифференциальных уравнений (уравнений Колмогорова), имеющих вид

^ = Е4-^(0 - РІ (*)ЕЧ- = г>2'

at j=і j=i

или, опуская аргумент t у переменных pit

% = Е \pj - РІ Е Ч = і. - *)• (10-0-18)

at j=і І=І

Напомним, что интенсивности потоков Х^- могут зависеть от времени t (аргумент t для краткости написания опущен).

Уравнения (10.0.18) удобно составлять, пользуясь размеченным графом состояний системы и следующим мнемоническим правилом: производная вероятности каждого состояния равна сумме всех потоков вероятности, переводящих из других состояний в данное, минус сумма всех потоков вероятности, переводящих из данного состояния в другие. Например, для системы S, размеченный граф состояний которой дан на рис. 10.0.8, система уравнений Колмогорова имеет вид

dpx / dt = Х31р3 + Х41р4 - (Х12 + Х14) р1;

dp2 / dt = X12pj - Х23р2; dp3 /dt = \23p2 - (X31 + X34 4- X35) p3; (10.0.19)

dp4 / dt = \ырг 4- X34p3 4- X51p5 - X41p4; dp § / dt= \-Pl - X54p5.

Так как для любого t выполняется условие (10.0.17), можно любую из вероятностей (10.0.15) выразить через остальные и таким образом уменьшить число уравнений на одно.

Чтобы решить систему дифференциальных уравнений (10.0.18) для вероятностей состояний Pi(t), p2(t),..., pn(t),нужно задать начальное распределение вероятностей (10.0.20)

pl(0),p2(0),...,pi(0),...,pn(0), сумма которых равна единице:

Ел (°) = 1Если, в частности, в начальный момент t = 0 состояние системы S в точности известно, например, S(0) = s{, то р{ (0) = 1, а остальные веротно- сти (10.0.20) равны нулю.

Во многих случаях, когда процесс, протекающий в системе, длится достаточно долго, возникает вопрос о предельном поведении вероятностей р{ (Ї) при і —> сх). Если все потоки событий, переводящие систему из состояния в состояние, являются простейшими (т.е. стационарными пуассоновскими с постоянными интенсивностями \{j), в некоторых случаях существуют финальные (или предельные) вероятности со-стояний 1,..., n),

(10.0.21)

Pi = lim Pi (і) (і

t —> oo не зависящие от того, в каком состоянии система S находилась в начальный момент. Это означает, что с течением времени в системе S устанавливается предельный стационарный режим, в ходе которого она переходит из состояния в состояние, но вероятности состояний уже не меняются. В этом предельном режиме каждая финальная вероятность может быть истолкована как среднее относительное время пребывания системы в данном состоянии.

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

/ч,

л о ^

JrL^ Тл.

«г

Для существования финальных вероятностей состояний одного условия X» = const недостаточно, требуется выполнение еще некоторых условий, проверить которые можно по графу состояний, выделив на нем «существенные» и «несущественные» состояния. Состояние s( называется существенным, если нет другого состояния Sj такого, что, перейдя однажды каким-то способом из s. в sj7 система уже не может вернуться в s{. Все состояния, не обладающие таким свойством, называются несущественными.

Например, для системы S, граф состояний которой дан на рис. 10.0.9, со- рис ю q 9

S2 стояния sv s2 несущественны (из Sj можно уй 53 55 54 ти, например, в s2 и не вернуться, а из s2 в s4 или s5 и не вернуться), а состояния s4, s5, 53, 5g, s7 — существенны (существенные состояния обведены жирными линиями).

Рис 10 0 10 конечном числе состояний п для су

ществования финальных вероятностей необходимо и достаточно, чтобы из каждого существенного состояния можно было (за какое-то число шагов) перейти в каждое другое существенное. Граф, представленный на рис. 10.0.9, этому условию не удовлетворяет (например, из существенного состояния s4 нельзя перейти в существенное состояние 56); для графа, показанного на рис. 10.0.10, финальные вероятности существуют (из каждого существенного состояния возможен переход в каждое другое существенное).

Несущественные состояния потому так и называются, что из каждого такого состояния система рано или поздно уйдет в какое-то из существенных и больше не вернется. Естественно, финальные вероятности для несущественных состояний равны нулю.

Если система Sимеет конечное число состояний , s2,..., sn, то для существования финальных вероятностей достаточно, чтобы из любого состояния системы можно было (за какое-то число шагов) перейти в любое другое. Если число состояний , s2,..., sn,... бесконечно, то это условие перестает быть достаточным, и существование финальных вероятностей зависит не только от графа состояний, но и от интенсивностей \{j.

Финальные вероятности состояний (если они существуют) могут быть получены решением системы линейных алгебраических уравнений, они получаются из дифференциальных уравнений Колмогорова, если положить в них левые части (производные) равными нулю. Однако удобнее составлять эти уравнения непосредственно по графу состояний, пользу-ясь мнемоническим правилом: для каждого состояния суммарный выходящий поток вероятности равен суммарному входящему. Например, для системы S, размеченный граф состояний которой дан на рис. 10.0.11, уравнения для финальных вероятностей состояний имеют вид

(\12 + Х13) рг = Х21р2; (\21 + \24)р2 = Х^ + Х42р4; *2 і ^12 13 X 42 s ^34 5 3 4 /Г

(\a + \s)Pz = \zPv (Ю.0.22)

Х42 Ра = \аР2 + \аРъ + \аРь>

X,

Х54 Ръ = \ъРъ'

Рис. 10.0.11

Таким образом, получается (для системы S с п состояниями) система п линейных однородных алгебраических уравнений с п неизвестными р1, р2,..., рп. Из этой системы можно найти неизвестные рг, р2,..., рп с точностью до произвольного множителя. Чтобы найти точi—л——и-l М-2 М-з 4-1 X, Ni-i k^ ^ sk-1 sk 5n-1 5n М-п

Рис. 10.0.12

ные значения р1,..., рп, к уравнениям добавляют нормировочное условие Р\ + Р2+ ••• + Рп = 1» пользуясь которым можно выразить любую из ве-роятностей р{ через другие (и соответственно отбросить одно из уравнений).

На практике очень часто приходится встречаться с системами, граф состояний которых имеет вид, показанный на рис. 10.0.12 (все состояния можно вытянуть в цепь, причем каждое из них связано прямой и обратной связью с двумя соседними, кроме двух крайних, каждое из которых связано только с одним соседним). Схема, изображенная на рис. 10.0.12, называется схемой гибели и размножения. Это название заимствовано из биологических задач, где состояние популяции sk Означает наличие в ней к единиц. Переход вправо связан с «размножением» единиц, а влево — с их «гибелью». На рис. 10.0.12 «интенсивности раз-множения» (\0, Xj,..., Хп-1) проставлены у стрелок, ведущих слева направо, «интенсивности гибели» (м-и М-2» •••» M-n-l) ~~ У стрелок, ведущих справа налево; каждая из них отмечена индексом того состояния, из которого исходит соответствующая стрелка.

Для схемы гибели и размножения финальные вероятности состояний выражаются формулами: х0\

MХ0

Pi = — Ро,

И-1

(к= 0,..., тг);...;

\\ • • • X-L1

Рк = —Р0

\іг\і2...\хк W j j W-Vi

1 + ^+ М-1

. (10.0.23)

Ро =

_ \)У"\>-1 .

M'lM'2

M-lM-2-И-п

Рп — Ро»

M-lM-2-M-n Обратим внимание на правило вычисления любой вероятности состояния (при А; = 1, 2,..., тг)

Рк = W'-^k-і Ро>

M-iM-2—M-ifc

которое можно сформулировать так: вероятность любого состояния в схеме гибели и размножения (см. рис. 10.0.12) равна дроби, в числителе которой стоит произведение всех интенсивностей размножения, стоящих левее sh а в знаменателе — всех интенсивностей гибели, стоящих левее sh умноженной на вероятность крайнего левого состояния р0.

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

и дисперсии случайной функции X(t) — числа единиц в системе в момент времени t:

= (Ю.0.24)

at к=о

^- = Е Iх» + ^ + 2к (V - - - Vk)] РШ 10.0.25)

аг к=0

В этих формулах нужно полагать Хп = р0 =0. Интенсивности \-(0 < к < п — 1) и\хк (1 < к < п) могут быть любыми неотрицательными функциями времени.

При достаточно больших значениях mx(t) (> 20) и выполнении условия 0 < mx(t) ± 3^Dx(t) < п можно приближенно полагать, что сечение

случайной функции X(t) представляет собой нормальную случайную величину с параметрами mx(t), y/Dx(t), полученными решением уравнений

(10.0.24), (10.0.25). Формулы (10.0.24) и (10.0.25) остаются справедливыми при п —> оо, если верхний предел в суммах заменить на оо.

Производится наложение («суперпозиция») двух простейших потоков: 1) потока I с интенсивностью \г и 2) потока II с интенсивностью Х2 (рис. 10.1). Будет ли поток III, получившийся в результате суперпозиции, простейшим, и если да, то с какой интенсивностью?

f f f f f f 1

її і її і її і її і її і її і

II-?—ґгігі—f—! t t—* ! t f f—!-t—t

і ¦ і 11 і ¦ і і і ¦ ¦ і 11 і і

і і і 11 ¦ і 11 і і

і ¦ і 11 і ¦ і і і ¦

і ¦ і 11 і ¦ і і і ¦ ¦ і 11 ¦ і

III;

Hi 4* 4* * * * ^

Рис. 10.1

Решение. Да, будет, так как свойства стационарности, орди-нарности и отсутствия последействия сохраняются; интенсив-ность потока III равна \х + Х2.

Производится случайное прореживание простейшего потока событий с интенсивностью X; каждое событие, независимо от других, с вероятностью р сохраняется в потоке, а с вероятностью 1 — р выбрасывается (в дальнейшем такую операцию будем называть ^-преобразованием потока). Каким будет поток, получающийся в результате ^-преобразования простейшего потока?

Решение. Поток будет простейшим с интенсивностью \р. Действительно, все свойства простейшего потока (стационарность, ординарность, отсутствие последействия) при ^-преобразовании сохраняются, а интенсивность умножается на р.

10.3. Интервал времени Т между событиями в ординарном потоке имеет плотность Хе-М^о) 0

t >t t при при

05

(10.3)

/(0 =

о

Рис. 10.3

Интервалы между событиями независимы. 1) Построить график плотности f(t). 2) Является ли данный поток простейшим? 3) Является ли он потоком Пальма? 4) Какова его интенсивность X? 5) Каков коэффициент вариации vt интервала между событиями?

Решение. 1) См. рис. 10.3; распределение такого вида назовем «сдвинутым на t0 показательным».

Нет, не является, так как распре-деление (10.3) непоказательное.

Да, является в силу ординарности потока, независимости интервалов и одинакового их распределения.

4)Х = 1/М[Г]; М[Г] = 1/\ + *0; Х = (1 / X + t,)'1 =Х/(1 + \*0). 5)D[T] = i;

1/X

М[Г] 1 / X + «о 1 + Х*С 10.4. На оси 0t имеется простейший поток событий с интенсив-ностью X. Из этого потока формируется другой следующим образом: интервал между каждыми двумя соседними событиями делится пополам и в точку деления вставляется еще одно событие (на рис. 10.4 где кружками обозначены основные, крестиками — вставленные события). Найти плотность распределения f(t) интервала Т между соседними событиями в новом потоке. Будет ли этот поток простейшим? Будет ли он потоком Пальма? Каков коэффициент вариации интервала Т между событиями?

Решение. Т = X /2, где X имеет показательное распределение с параметром Х:/х(х) = \е~Хх(х > 0). Пользуясь решением задачи 8.1 и полагая в формуле (8.1) а = 1/2; 6 = 0, получаем (10.4)

f(t) = 2\e~2Xt (t> 0). 10.5. Это есть показательное распределение с коэффициентом вариации vt = 1. Тем не менее новый поток не будет ни простейшим, ни даже потоком Пальма. Докажем сначала, что он не будет потоком Пальма. Хотя интервалы между событиями распределены одинаково по закону (10.4), они не являются независимыми. Рас-нэ-жэ х 0Х0--*-<*Ь-Х-<*Н*) X © X—®—t

О

Рис. 10.4

смотрим два соседних интервала между событиями потока. С вероятностью 1/2 они независимы, с вероятностью 1/2 равны друг другу, следовательно, зависимы. Таким образом, новый поток событий — не пальмовский. Естественно, он не будет и простейшим, так как простейший поток — частный случай пальмовского.

Таким образом, показательное распределение интервала между событиями — недостаточное условие для того, чтобы поток был простейшим.

Условия те же, что и в предыдущей задаче, с той разницей, что преобразованный поток состоит только из «крестиков» (середин интервалов). Ответить на те же вопросы, что и в предыдущей задаче.

Решение. Очевидно, что интенсивность нового потока по сравнению с интенсивностью исходного не изменится и останется равной X. Интервал между двумя соседними крестиками (рис. 10.5) равен

Т = (Х, +Xi+1)/2, (10.5)

где ХІУ X • +1 — два соседних интервала исходного потока. Величины ХІУ Xi+l распределены обе по показательному закону с параметром

X, а их полусумма (10.5) — по нормирован- X X. ному закону Эрланга 2-го порядка, так как

ф' ** ->Ф—^ t интервал Травен сумме двух независимых

' »—' показательно распределенных случайных

Т величин, деленной на два. Таким образом,

Рис. 10.5 интервал Т между двумя крестиками име

ет плотность/(0 = 4\Че~2™ (t> 0).

В преобразованном потоке все соседние интервалы времени будут зависимы, так как в состав этих интервалов входят одни и те же случайные величины. Однако эта зависимость распространяется только на соседние интервалы времени. Такие потоки иногда называют потоками со слабым последействием.

Коэффициент вариации vt для случайной величины Т будет

равен [см. формулу (10.0.7)] vt = 1 / л/2 < 1.

Поток автомобилей, движущихся по шоссе в одном направлении, представляет собой простейший поток с интенсивностью X. Человек выходит на шоссе, чтобы остановить первый по-павшийся автомобиль, движущийся в данном направлении. Най-ти закон распределения времени Т, которое ему придется ждать; определить его математическое ожидание rrtt и среднее квадрати-ческое отклонение at. Решение. Так как простейший поток не обладает последей-ствием, то «будущее» не зависит от «прошлого», в частности, от того, сколько времени тому назад прошел последний автомобиль. Распределение времени Т точно такое же, как и распределение промежутка времени между появлением соседних автомобилей, т.е. показательное с параметром X: f(t) = \e~xt (t < 0); отсюда mt = 1/Х;Д =1/Х2; ot=l/\ = mt; vt = 1.

Примечание. Если поток автомобилей, идущих по шоссе, является многорядным, то его можно рассматривать как суперпозицию нескольких потоков, соответствующих каждому ряду. Если каждый поток — простей-ший, то результат суперпозиции также является простейшим потоком, так как свойства стационарности, ординарности и отсутствия последействия при суперпозиции сохраняются (см. задачу 10.1).

10.7. Пассажир выходит на остановку автобуса в некоторый момент времени, никак не связанный с расписанием движения. Автобусы следуют друг за другом регулярно с интервалом времени длины I Найти закон распределения времени Г, которое придется пассажиру ждать автобуса, и выразить его характеристики Tfip ot через интенсивность потока автобусов X.

Решение. Момент прихода пассажира распределен с постоянной плотностью на интервале длины I между двумя автобусами; плотность распределения времени ожидания Т будет также постоянная [равномерное распределение на интервале (0, 1)]: f(t) = 1/1 (0 < t < I) или, обозначая 1/1 = X, f(t) = X (0 < t < 1/Х). Для равномерного распределения на участке длины 1/Х имеем mt=l/(2X); DT= 1 / (12Х2); ог = 1/(*/§Х); 10.8*. На оси 0? имеется пальмовский поток событий, интервалы между которыми распределены с плотностью f(t). На ось 0? случайным образом бросается точка ?* (например, прибывает «инспектор», наблюдающий за появлением событий, или же «пассажир» появляется на остановке автобуса), причем момент ?* никак не связан с моментами появления событий потока (рис. 10.8). Найти плотность распределения того интервала Г*, на который попала точка ?*, его математическое ожидание, дисперсию и среднее квадратическое отклонение.

Решение. С первого взгляда может показаться, что эта плотность — такая же, как плотность распределения f(t) любого интервала Т между событиями, однако это не так. Тот факт, что на участок Г* попала случайно брошенная точка ?*, меняет его распределение; действительно, если на оси (И есть разные участки (большие и маленькие), то с большей вероятностью точка попадет на один из больших участков.

Найдем плотность распределения f*(t) того участка Т*, на который попала точка Для этого найдем элемент вероятности /* (t) dty равный вероятности того, что точка попадет на промежуток, длина которого заключена в пределах (t,t + dt). Эта вероятность приближенно равна отношению суммарной длины всех таких промежутков на очень большом интервале времени Q к полной длине этого интервала.

Пусть на очень большом интервале Q уложилось большое число N промежутков между событиями. Среднее число промежутков, длина которых лежит в пределах (t,t+dt), равна Nf(t)dt; средняя суммарная длина всех таких промежутков приближенно равна tNf(t) dt. Средняя же общая продолжительность всех TV промежутков на участке Q будет (приближенно) равна Nmt, где

оо

ТП , = М[Т} = f tf(t) dt. Разделив одно на другое, получим

о

Nmt mt

Это равенство выполняется тем точнее, чем более длительный интервал времени будет рассматриваться (чем больше N). В пре-деле закон распределения случайной величины Г* будет

f*(t) = —№(t> 0). (10.8)

mt

і 00 і і М[Г*] = — f t f(t)dt = —a2(t) = —(Dt +mt2); mt mt mt

Она делит его на два промежутка: Q — ( ?

от ближайшего предыдущего события —• х ^ f— і

до и Я — от до ближайшего после- 0 Q ** Н дующего события. Найти распределение обоих ЭТИХ промежутков. РИС- 10-Ю

Решение. Предположим, что слу-чайная величина Г* приняла значение s: Г* = s, и найдем условное распределение промежутка Q при этом условии. Обозначим его плотность fq(t |s). Так как точка бросается на ось 01 совершенно случайно (безотносительно к событиям потока), очевидно, она будет иметь равномерное распределение в пределах промежутка Г* = s:

fQ(t\s) = l/s при О Чтобы найти безусловное распределение fq(t), надо осреднить плотность (10.10.1) с «весом» /*(з). Пользуясь формулой (10.8), получаем

оо

/*(*) = — Я*); /«(*) = /Л?(Ф)/* (*)<*»•

777/ /

* О

Учитывая, что fQ(t\s) отлично от нуля только при s > t, можно написать

оо оо

/«(*) = г-2-/(e)de = -l г/(і)л = —[i-f(0],

^ 5771. 777,, ^ га,

о * * о 1

где F{t) — функция распределения интервала Г между событиями в потоке Пальма.

Итак,

/mt

Очевидно, то же распределение будет иметь и промежуток времени Я = Г*- Q:

Ш = — [1-F(t)}. (10.10.3)

mt

10.11. Пользуясь результатами предыдущей задачи, проверить решение задачи 10.6, полученное из других соображений.

Решение. Имеем f(t) = \e~Xt; F(t) = l-e~xt (;t >0);mf =1/Х. По формуле (10.10.3)

fH (t) = X [1 - 1 + е"х< ] = \e~xt (t> 0), т.е. задача 10.6 решена верно.

10.12. Пассажир выходит на остановку автобуса в момент времени, никак не связанный с расписанием. Поток автобусов представляет собой поток Пальма с интервалами, имеющими равномерное распределение в пределах от 5 до 10 мин. Найти: 1) плотность распределения того интервала между автобусами, на который попал пассажир; 2) плотность распределения времени Я, которое ему придется ждать автобуса; 3) среднее время ожидания автобуса.

ю

/*(0

Рис. 10.12 Решение. Имеем /(г) = 1/5 при t є (5,10); mt =7,5. 1) По формуле (10.8) f*(t) = t/ 37,5 при t є (5,10). График плотности f*(t) показан на рис. 10.12, а. 0

(<~5)/5 1

при t < 5; при 5 < t < 10; при t > 10.

2)

т=

Отсюда по формуле (10.10.3)

fo

при t < 0;

/я(0 =

1 / 7,5 при 0 < t < 5;

(10 — t)/ 37,5 при 5 < ? < 10;

0 при t > 10. График плотности /я (t) показан на рис. 10.12, б. 3) Среднее время ожидания

Г t г 10-t тн = I —dt + / t dt ^ 6,11 [мин].

о 7'5 о 37'5

10.13. Рассматривается поток Эрланга А;-го порядка с плотностью распределения интервала Г между событиями: k-i

е-Х( (t > 0).

ш=

(10.13.1)

х (\t) (к- 1)! Найти функцию распределения Fk(t) этого интервала. Решение. Можно было бы найти функцию распределения по обычной формуле

I

Fk(t) = Jh(t)dt, 10.16. но проще найти ее исходя непосредственно из определения Fk(t) = P{TПерейдем к противоположному событию и найдем Р{Т> t}. Свяжем начало отсчета 0 с одним из событий потока Эрланга и отложим от него вправо два участка: Т (расстояние до следующего события потока Эр- / Т

ланга) и tДля выполнения неравенства Т > t нужно, чтобы на участок t попало меньше чем к событий простейшего потока с интенсивностью X (либо 0, либо 1,..., либо к — 1).

Вероятность того, что на участок t попадет тп событий, равна

р _ (х*г с-*

тп — і

m !

По правилу сложения вероятностей откуда

к-1

К (0 = 1- Е1-^- е_Х< = 1 - Я (* - 1, (Ю.13.2)

^ тп!

тп- 0

где 1 - R (гп, а) — табулированная таблица (см. табл. 1 прил. 1).

10.14*. Поток отказов ЭВМ представляет собой поток Эрланга А;-го порядка с плотностью (10.13.1) интервала между отказами (восстановление машины после отказа происходит мгновенно). «Инспектор» прибывает в случайный момент времени f* и ожида-ет первого отказа. Найти плотность распределения времени Я, в течение которого ему придется ждать отказа, и его математиче-ское ожидание тпн.

Решение. По формуле (10.10.3)

Ш =—\ 1-ШЪ

mt

где Fk(t) дается формулой (10.13.2), am, —к/\. Отсюда

K 771=0 ш ! К 771=0 171 1

Перепишем формулу (10.14.1) в виде

/я(О = їЕ^е-м(<>0). (10.14.2)

(г-1)!

Из (10.14.2) видно, что случайная величина Я имеет распределение, «смешанное» из к эрланговских распределений разных порядков; с одинаковой вероятностью 1 /к она имеет эрланговское распределение 1, 2, ..., А;-го порядков. Математическое ожидание такой случайной величины найдем по формуле полного математического ожидания:

тя=М[Я] = ±?М[Я|г], (10.14.3)

к г=і

гдеМ[Я| г] — условное математическое ожидание случайной величины Я при условии, что она распределена по закону Эрланга г-го порядка.

Находим по первой формуле (10.0.4) М[Я|г) = г / X, откуда

1 * (к + 1)к к + 1 ,лі\л/ тп и =—\ г = - — = . (10.14.4)

к\ 2к\ 2Х

10.15*. Пальмовский поток событий с плотностью распределения f*(t) интервала между событиями подвергается р-преобразо- ванию (см. задачу 10.2). Случайная величина V— интервал между событиями в преобразованном потоке. Найти математическое ожидание и дисперсию случайной величины V.

Решение. Случайная величина V представляет собой сумму случайного числа независимых случайных величин (см. задачу

8.63): V = где Y — дискретная случайная величина, имеюк=і

щая геометрическое распределение Р {Y = т} = pq m_1 (га = 1,

2,... = 1 - p, а каждая из случайных величин Тк имеет распре-деление f(t).

Тогда последовательные интервалы между событиями в р-пре- образованном потоке будут

к=1 і =1

где случайные величины Vv V2,... независимы, и преобразованный поток есть поток Пальма. В соответствии с задачей 8.63

mt Dt

mv = —Dv = —

P P

где

UU LaJ

m( = f tf(t) df; Dt=f(t-mt )2f(t) dt.

Примечание. Можно доказать, что при многократном р-преобра- зовании потока Пальма получается поток, близкий к простейшему.

Найти закон распределения интервала Т между событиями в потоке Пальма, если случайная величина Т определяется из

выражения Т = у т е- представляет собой сумму случайного

к=\

числа случайных слагаемых, где случайные величины Тк независимы и подчинены показательному закону с параметром X, а случайная величина Y не зависит от них и имеет геометрическое распределение, начинающееся с единицы: рп = Р{Y = n} = pqn~1x

х (0 < р < 1; п = 1,2,3,...).

Решение. В задаче 8.62 было показано, что случайная величина Т подчинена показательному закону с параметром Хр, следо-вательно, рассматриваемый поток Пальма является простейшим с интенсивностью Хр, который получается путем р-преобразования простейшего потока с интенсивностью X. Это подтверждает правильность решения задачи 10.2.

Поток автобусов, приходящих на остановку, представляет собой поток Пальма; интервал Т между ними имеет плотность распределения fT (t). Автобус находится на остановке в течение неслучайного времени т. Пассажир, подойдя к остановке в случайный момент t* (рис. 10.17, а), садится в автобус, если тот находит-

Ті

-хТ ?* т' Т Зона захвата

гр*

Зона Зона

захвата захвата

Т*-(т-тЛ

ШЯ ШЯ* ешз УШ т' т t* т' т ся на остановке; если же автобуса нет, то ждет его в течение времени т' и, если за это время автобус не подойдет, покидает остановку и идет пешком. Закон распределения fT(t) таков, что случайная величина Гне может быть меньше, чем т + т' (рис. 10,17, б). Найти вероятность того, что пассажир сядет в автобус. __

Решение. Переходим к противоположному событию А = = {пассажир не сядет в автобус}. Это означает, что пассажир прибудет на остановку в момент t*, когда на ней нет автобуса, и за время ожидания следующий автобус не придет. Каждое событие «подход автобуса к остановке» сопровождается «зоной захвата» пассажира; ширина этой зоны т' + т (рис. 10.17, в).

Событие А = {пассажир не сел в автобус} соответствует попа-данию точки t* вне пределов зоны захвата (рис. 10.17, г). Точка t* распределена равномерно по всей длине интервала Г*. Вероят-ность того, что она попадет на участок Г* — (т + т'), не вошедший в зону захвата, равна (по интегральной формуле полной вероят-ности)

f(t)dt = т + т т + т/

где mt — средний интервал между автобусами.

Вероятность того, что пассажир сядет в автобус, равна

10.18. Происходит преобразование простейшего потока с ин-тенсивностью X, состоящее в следующем. Если расстояние между соседними событиями Г, оказывается меньше какого-то допустимого предела («интервала безопасности»), то событие отодвигается от предыдущего на интервал если же Г, >t0l то событие остается на своем месте (рис. 10.18). Является ли преобразованный поток, образованный точками ©{, ©... на оси 0V, простейшим? Является ли он потоком Пальма?

Решение. Ни тем, ни другим преобразованный поток не яв-ляется, так как в нем имеется сколь угодно далеко идущее после- ©7©8©9 ©

10

6

О Є, ©2 ©з 04 ©5 ©,

Т

т т— г

^0 1 1 А)

4-е

0' действие. Например, «теснящиеся» на оси О V точки в7,08,69,01О отодвигают каждую последующую точку на оси 0V на отрезок времени, зависящий от моментов прихода событий и интервалов между ними в прошлом. Если t0 много меньше среднего расстояния между событиями в исходном потоке: t0 « 1 / X, то последействием в преобразованном потоке можно пренебречь.

10.19. Происходит наложение (суперпозиция) двух независимых потоков Пальма с плотностями распределения интервала между событиями Д(0 и /2 (0- Будет ли результирующий поток потоком Пальма?

Решение. Суперпозиция двух потоков Пальма выглядит, как показано на рис. 10.19. Ясно, что интервалы Tv Т2,... результирующего потока III не будет независимыми, так как их размеры могут быть обусловлены размерами одного и того же интервала на оси I или И. Например, Тг и Т2 в сумме дают Тп и, значит, не являются независимыми. Однако эта зависимость быстро затухает по мере увеличения расстояния по времени между началами интервалов.

ЇІ II

Рис. 10.19

I

Примечание. Можно доказать, что при суперпозиции достаточно большого числа независимых потоков Пальма со сравнимыми интенсив- ностями получается поток, близкий к простейшему.

10.20. В процессе эксплуатации ЭВМ может рассматриваться как физическая система 5, которая в результате проверки может оказаться в одном из следующих состояний: sx — ЭВМ полностью исправна; s2 — ЭВМ имеет незначительные неисправности в оперативной памяти, при которых она может решать задачи; s3 — ЭВМ имеет существенные неисправности и может решать ограниченный класс задач; s4 — ЭВМ полностью вышла из строя.

В начальный момент времени ЭВМ полностью исправна (состояние sx). Проверка ЭВМ производится в фиксированные моменты времени tv t2l tz. Процесс, протекающий в системе 5, может рассматриваться как однородная марковская цепь с тремя шагами (первая, вторая, третья проверки ЭВМ). Матрица переходных вероятностей имеет вид

0,3 0,4 0,1 0,2

0 0,2 0,5 0,3

0 0 0,4 0,6 '

0 0 0 1,0

"" ——Определить вероятности состояний Рис.10.20 ЭВМ после трех проверок.

Решение. Граф состояний ЭВМ имеет вид, показанный на рис. 10.20. Против каждой стрелки проставлена соответствующая вероятность перехода. Начальные вероятности состояний рг (0) = 1; р2 (0) = = р,(0) = р4(0) = 0.

По формуле (10.0.14), учитывая в сумме вероятностей только те состояния, из которых возможен непосредственный переход в данное, находим:

Р1(1) = Р1(0)Р11 =1-0,3 = 0,3;

Р2(1) = Рг(0)Р12 =1-0,4 = 0,4;

Рз(1) = Рі(0) різ =1-0,1 = 0,1;

Р4(1) = Р!(0)Р14 =1-0,2 = 0,2;

Pi (2) = Рі(1) Рп =0,3-0,3 = 0,09; р2(2) = р1(1)Р12 +р2(1)Р22 = 0,3-0,4 + 0,4-0,2 = 0,20; РЗ(2) = Р1(1)Р„ +Р2(1)Р23 +Р3(1)Рзз =0,27; Р4(2) = Р1(1)Р14 +Р2(1)Р24 +P3(1)J°34 +Р4(1)Р44 =0,44;

рг (3) = р1 (2) Рп = 0,09 • 0,3 = 0,027; р2 (3) = Pl (2) Р12 + р2 (2)Р22 = 0,09 • 0,4 + 0,20 • 0,2 = 0,076;

р3(3) = рх (2) Р13 + р2(2)Р23 + Рз(2)Р33 = 0,217; р4(3) = р,{2) Р14 + р2(2)Р24 + р3(2)Р34 + р4(2)Р44 = 0,680.

Итак, вероятности состояний ЭВМ после трех проверок: рх(3) = 0,027; р2(3) = 0,076; р,(3) = 0,217; р4(3) = 0,680.

10.21. Точка S «блуждает» по оси абсцисс Ох (рис. 10.21, а) по следующему закону: на каждом шаге она с вероятностью 0,5 остается на месте, с вероятностью 0,3 перескакивает на единицу вправо и с вероятностью 0,2 — влево. Состояние системы S после к шагов определяется одной координатой (абсциссой) точки S. Начальное положение точки — начало координат. Рассматривая последовательность положений точки S как цепь Маркова, найти

0,5 0,5 0,5 0,5 0,5

s

1 1 I I I « L

-3-2-10 1 2 3 x

б

Рис. 10.21

вероятность того, что она после четырех шагов окажется от начала координат не дальше, чем на расстоянии, равном единице.

Решение. Обозначим СОСТОЯНИе СИСТеМЫ (ТОЧКИ S) Через

где і — координата S на оси абсцисс. Размеченный граф состояний показан на рис. 10.21, б. (Здесь для наглядности проставлены «петли», соответствующие задержке S в прежнем положении.)

Последовательность состояний образует цепь Маркова с бесконечным числом состояний. Переходные вероятности Ротличны от нуля только в случае j = і; j = г — 1; j = і + 1; Рг г = 0,5; р. = 0,3; Р; —0,2. Все остальные переходные вероятности равны нулю. Искомая вероятность Р равна сумме вероятностей: р0(4) + ^(4) + p_j(4). Найдем их, пользуясь рекуррентными соотношениями (10.0.14).

Имеем р0 (0) = 1; рг (0) = р_х (0) =... = 0. Далее,

t;0(l) = p0(0)P0j0 = 0,5; рг(1) = р0(0)Р0|і =0,3;

р.1(1) = р0(1)Р0|.1=0,2;

р0(2) = р0(1)Р^0 +ft(l)P1|0 +p.1(l)P_lj0 =0,5-0,5 +

+0,2 • 0,3 + 0,3 • 0,2 = 0,37;

P1(2) = Po(l)P0fi +Рі(1)Рі,і ^ 0,5 • 0,3 + 0,3 • 0,5 = 0,30; р2 (2) = Pl(l)P12 =0,3-0,3 = 0,09; р_г (2) = р0(1-)Р0|-1 + Р-1 і,—і = 0,5 • 0,2 + 0,2 • 0,5 = 0,20; Р,2 (2) = р_г (l)P_ls_2 = 0,2 • 0,2 = 0,04; Ро(3) = Ро(2)Ро,о +Рі(2)Р1|0 +Р-і(2)Р.1|0 =0,305; Pl(3) = Po(2)P0fi + Pi (2)Рід + J>2(2) P2,2 = 0,279; p2 (3) = Pl (2)P12 + p2 (2)P2 2 = 0,135; Рз(3) = р2(2)Р23= 0,027;

P-i(3) = P.2(2)P.2i.1 +P.1(2)P.1|.1 +Po(2)P0|-I =0,186; p_2( 3) = p_2(2)P_2 _2 + p.^JP.^ = 0,060;

Р_з(3) = р_2(2)Р_2,-з — 0,008;

ро(4) = Р!(З)Р1ї0 + Po(3)Po,o + p-i(3)P-i,0 ~°>264;

P1(4) = P2(3)P2|1 +^(3)Р1Д +Po(3)P0fi ~ 0,257; p_1(4) = p0(3)P0)_1 + p_1(3)P_1_1 + p_2(3)P_2,_1 « 0,172.

Искомая вероятность

P = Ро (4) + рг (4) + (4) « 0,693.

Итак, вероятность события А, состоящего в том, что за четыре шага точка S окажется от начала координат на расстоянии, не большем единицы, равна 0,693.

В условиях предыдущей задачи найти вероятности того, что за четыре шага точка S ни разу не удалится от начала координат дальше, чем на единицу.

Решение. Обозначим р0 (к), рг (к), р_г (к) вероятности состояний 50, sv s_x при условии, что до fc-го шага включительно точка S ни разу не удалялась от начала координат больше, чем на единицу.

С первого взгляда здесь процесс не является цепью Маркова (так как вероятности будущих состояний зависят от «предыстории» — была ли точка S хотя бы один раз дальше, чем на одну единицу, от начала координат), но его можно свести к цепи Мар-кова, если ввести еще одно состояние 5* — точка хотя бы один раз была от начала координат на расстоянии, большем, чем единица.

Рис. 10.22

Граф состояний показан на рис. 10.22. Из состояния s* нет перехода ни в какое другое, такое состояние называется в теории марковских цепей «поглощающим». Вероятность события А = {точка S за четыре шага ни разу не отойдет от начала координат на рас-стояние, большее, чем единица} вы- числится как сумма вероятностей Ро (4) + (4) + рг (4) для системы с графом состояний, соответствующим рис. 10.22. Предоставляем читателю вычислить эти вероятности самостоятельно.

Система S — техническое устройство, состоящее из т узлов и время от времени (в моменты tv t2,..., tk), подвергающееся профилактическому осмотру и ремонту. После каждого шага (момента осмотра и ремонта) система может оказаться в одном из следующих состояний: s0 — все узлы исправны (ни один не заменялся новым); — один узел заменен новым, остальные исправны; s2 — два узла заменены новыми, остальные исправны;...; s{ - і узлов (г < т заменены новыми, остальные исправны;...; sm — все т узлов заменены новыми.

Вероятность того, что в момент профилактики узел придется заменить новым, равна р (независимо от состояния других узлов). Рассматривая состояния системы S как марковскую цепь, найти переходные вероятности и для т = 3, р = 0,4 вычислить вероятности состояний системы S после трех шагов (в начальный момент все узлы исправны). 0,216 0,36 0,6 1 0,432 0 0,48 0 0,4 0 50 53 ^ 0,064^

Рис. 10.23

Решение. Обозначая q = 1 - р, запишем переходные вероятности цепи. Для любого состояния системы Sj вероятность Р{-равна нулю при j < г; вероятность Рй равна вероятности того, что на данном шаге ни один узел не придется заменить новым, т.е. т— і еще не замененных узлов остаются в составе устройства: Рй =qm~%. При г < j вероятность перехода Рн равна вероятности того, что на данном шаге из т — і еще не замененных узлов j — і придется заменить новыми. Пользуясь биноминальным распределением, находим P{j = pj~% qm~j+%. Состояние sm яв

ляется поглощающим. Для т = 3, р = 0,4 граф состояний системы имеет вид, показанный на рис. 10.23:

0,216 0,432 0,288 0,064 0 0,36 0,48 0,16 0 0 0,6 0,4 0 0 0 1,0

Имеем р0 (0) = 1; рх (0) = р2 (0) = ръ (0) = 0. Находим вероятности состояний после одного, двух, трех шагов:

РоС1) = 0,216; рг(1) = 0,432;

р2(1) = 0,288; ft(l) = 0,064;

p1(2) = p1(i)p11 +Po(i)P0ii р2(2) = р2(1)Р22 +Ро(1)Р02 +Рі(1)Рі2 « °>4425

рз(2) = рз(1)рзз +р2(1)Р23 +Рі(1)Р/з +р0(1)Р03 « 0,262; Ро(3) = р0(2)Р00 « 0,010;

Р1(3) = р1(2)Р11+р0(2)Р01 «0,110;

р2(3) - р2(2)Р22 + Р0(2)Р02 + р1 (2)Р12 « 0,398; Рз(3) = Рз(2)Рзз + Ро(2)Р03 + Pi (2)Різ + Р2(2)Р2з ~ 0-482.

10.24. В моменты времени tv t2, t^ производится осмотр ЭВМ. Возможные состояния ЭВМ: s0 — полностью исправна; Sj — незначительные неисправности, которые позволяют эксплуатировать ЭВМ; s2 — существенные неисправности, дающие возможность решать ограниченное число задач; s3 — ЭВМ полностью вышла из строя.

Матрица переходных вероятностей имеет вид

0,5 0,3 0,2 0 . и _ 0 0,4 0,4 0,2 1^1- 0 0 0,3 0,7 ' 0 0 0 1

Построить граф состояний. Найти вероятности состояний ЭВМ после одного, двух, трех осмотров, если вначале (при t — 0) ЭВМ была полностью исправна.

0,5 0,4 0,3 1

Рис. 10.24

Решение. Граф состояний показан на рис. 10.24.

Ро(1) = Ро(0)Р0о =1-0,5 = 0,5;

Рі(1) = Ро(0)Р„і =1-0,3 = 0,3;

р2(1) = р0(0)Р02 =1-0,2 = 0,2;

р0(2) = р0(1)Р00 =0,25; рг(2) = р0(1)Р01 + р1(1)Р(1 =0,27;

р2(2) = р0(1)Р02 +Рі(1)Р12 +р2(1)Р22 =0,28;

Рз (2) = Р2 (1)Р2з + Рі (1)Різ =0.20; Ро(3) = Ро(2)Роо =0,125;

Pi (3) = Ро (2) Рої + Рі (2)Рц = 0,183;

р2 (3) = ро (2)Р02 + рх (2)Р12 + р2 (2)Р22 = 0,242;

р3(3) = р1(2)Р1 з + р2( 2)Р23 + Рз(2)Р33 = 0,450.

10.25. Рассматривается процесс работы ЭВМ. Поток отказов (сбоев) работающей ЭВМ — простейший с интенсивностью X.

Если ЭВМ дает сбой, то он немедленно обнаруживается, и обслуживающий персонал приступает к устранению неисправности (ремонту). Закон распределения времени ремонта — показательный с параметром р: ip (t) = (t > 0). В начальный момент (t = = 0) ЭВМ исправна. Найти: 1) вероятность того, что в момент t ЭВМ будет работать; 2) вероятность того, что за время (0, t) ЭВМ дает хотя бы один сбой; 3) финальные вероятности состояний ЭВМ.

Решение. 1) Состояния системы S (ЭВМ) следующие: s0 — исправна, работает; — неисправна, ремонтируется. Размеченный граф состояний дан на рис. 10.25, а. X 50 5i Рис. 10.25 а б

\ dPi \

at

Уравнения Колмогорова для вероятностей состояний p0(t) и рг (t) имеют вид

(10.25.1)

dPo dt

р рг. Из этих уравнений одно (любое) может быть отброшено, так как для любого момента t имеем р0 + рх = 1. Подставляя в первое из уравнений (10.25.1) pt = 1 — р0, получаем одно дифферен-циальное уравнение относительно р0:

:р- (Х + р)р0.

Фо dt

Решая это уравнение при начальном условии р0(0) = 1> получаем МРо(0 =

Х + р

м(10.25.2) откуда X

Pitt)

х + р

(10.25.3) бы один сбой, равна p-^it) = 1 — e~yt. Эту вероятность в данном случае можно было бы вычислить и проще, как вероятность того, что за время t появится хотя бы одно событие (сбой) в простей-шем потоке сбоев с интенсивностью X.

3) Из уравнений (10.25.2), (10.25.3) при t —> оо получим финальные вероятности состояний: р0 =\i / (X + р,); рг =Х / (X + р.), которые, впрочем, можно было бы получить непосредственно из графа состояний, пользуясь схемой гибели и размножения (предоставим читателю сделать это самостоятельно).

10.26. В условиях предыдущей задачи 10.25 неисправность ЭВМ обнаруживается не сразу, а по прошествии некоторого времени, имеющего показательное распределение с параметром v. Написать и решить уравнения Колмогорова для вероятностей состояний. Найти финальные вероятности состояний (непосредственно по графу состояний).

Решение. Состояния системы: s0 — ЭВМ исправна, работает; с X V a0 sx — ЭВМ неисправна, но это не обнаружено; s2 — ЭВМ ре-монтируется. Граф состояний дан нарис. 10.26.

Рис. 10.26

dp о х dpx

dp 2

1Г = УР>

Уравнения Колмогорова для вероятностей состояний будут:

>Ф0 - vPi;

\ip2. (10.26.1)

Решать эту систему будем с помощью преобразования Лапласа. Тогда уравнения (10.26.1) с учетом начальных условий для изображений тг { вероятностей pi примут вид: srK1 = Хтт0 — ;

sn0 = рлг2 - Хтг0 + 1; от2 = утт1 -млт2.

Решая эту систему алгебраических уравнений, получаем следующие уравнения для изображений:

уХ

X у

к, = тг 0; тг2 = тт., =

i\ ^ —

(,s + v)(s + \l)

s + у

ТГп = •

ч

S (s + S (|jl + у + X) + уХ + V[i + Xjl)

Обозначим (\l + у + X)

— уХ — v\i — X|jl;

[і + у + x

a = h Тогда выражения для вероятностей примут вид: 1 - ae*

aeat _ Ье~ы eat - ebt P о (О = ; + 0> + М-) 7— + M"

a — b

a — b

ab ab (a — 6) beat - ¦ аеи ab (а ¦ +

рД^) = X Xp

a — і p2(t) = v\

1 | beat -aebt ab ab (a — b) Для нахождения финальных вероятностей можно воспользоваться как изображениями, так и самими вероятностями:

Ро = lim p0(0 = limOT0(s) = - ^ 5

г->оо s->0 Хр + ЛУ Н- Ур Хр

Ху

(10.26.2)

Pl =

Хр + Ху + ур

Хр Н- Ху + ур

Р2 =1 - Ро - Pi Финальные вероятности состояний можно найти и непосред-ственно по графу рис. 10.26 : рр2 = Хр0; Хр0 = ург; ург = рр2. Из этих уравнений любое (например, последнее) можно отбросить. Выражая р2 через р0 и рг: р2 = 1 - р0 — рг, получаем два уравнения:

М- (1 ~ Ро - Pi) = ХР0; хРо = vPi •

Решение этих уравнений даст те же результаты (10.26.2).

10.27. Электронное техническое устройство (ЭТУ) состоит из двух одинаковых взаимозаменяемых узлов. Для работы ЭТУ достаточно, чтобы работал хотя бы один узел. При выходе из строя одного из узлов ЭТУ продолжает нормально функционировать за счет работы другого узла. Поток отказов каждого узла — простейший с параметром X. При выходе из строя узла он сразу начинает ремонтироваться. Время ремонта узла — показательное с параметром р. В начальный момент (при t = 0) оба узла работают. Найти следующие характеристики работы ЭТУ:

вероятности состояний как функции времени: s0 — исправны оба узла; sx — исправен один узел, другой ремонтируется; s2 — ремонтируются оба узла (ЭТУ не работает);

вероятность p(t) того, что за время t ЭТУ ни разу не прекратит работу;

финальные вероятности состояний ЭТУ;

для предельного (стационарного) режима ЭТУ среднее от-носительное время, в течение которого ЭТУ будет работать;

для того же предельного режима среднее время tp беспере-бойной работы ЭТУ (от включения после восстановления до очередного выхода из строя).

Решение. Граф состояний ЭТУ дан на рис. 10.27, а (у левой верхней стрелки стоит 2\, так как работают и могут выходить из строя два узла; по аналогичной причине стоит 2\і у правой нижней стрелки, так как оба узла ремонтируются).

1) Уравнения Колмогорова имеют вид:

= ^j- = 2\p0+2М>2 -(X + mOPi;

at at

= (10.27.1)

При этом должно выполняться условие р0 + рх + р2 = 1.

Решая эту систему уравнений при начальных условиях р0 (0) = 1; рг (0) = р2 (0) = 0, получаем

і it at bt

Ро(0 = - р- + (Х + Зм.)- е— +

ab beat - aebt ab (a -ь)\ +2[і2

а — Ь а + b

где a = -(X + jx); & = —2 (X + |л);

b=\ + \i] ab = 2 (X -h M') ;

_ a2eat -b2ebt , (X + S[i)(aeat -beht) , 2^ (eat -ebt) ( 2X ^ Pi (0 = ; 7T- + - : jt + 7 + — Pott)

[i {a — b) [i [a — b) a — b p,

Из полученных выражений находим:

p2(t) = l-Po(t)-Pl(t); р2( 0) = 0.

2) Чтобы найти вероятность p(t\ сделаем состояние s2 (ЭТУ прекратило работу) поглощающим (s2) (рис. 10.27, б). Уравнения Колмогорова для вероятностей состояний ЭТУ будут

dp0/dt =\ip1 —2X j90; dpl/dt =2\p0 — (X + dp2/dt =2\рг.

Решая первые два уравнения при начальных условиях р0 (о) = 1, рг (0) = 0, получаем

a t о 3* a t 31

_ ae - pep /x v e - ep

a — p a — p

где

а = -(ЗХ + р) + д/х2+6Хр + р2 -(ЗХ + р)-д/х2+6Хр + р2 — ^ р —

(величины а и (3 отрицательны при любых положительных значениях X и р). Далее 2Х , .

Н Ро(*)М1 dpn 2Х р at р

+ (Х + ц)

a - (3

a - (3 Искомая вероятность p(t) = p0(t) + p1(t). Заметим, что функция р (t) является монотонной убывающей, при этом р (0) = 1; р(оо) = 0.

2Х 2Х

Pi =—Ро; Рі=г~чРо

И 2ц2

X

IN

3) Финальные вероятности состояний найдем по графу (рис. 10.27, а) и общим формулам (10.0.23) для схемы гибели и размножения

Ро', Po+Pl+P2=1'> 2 1—1

у/(X + jx)2.

Ро = [1 + 2Х/^ + (Х/[х) 4) Среднее относительное время, которое ЭТУ будет работать, равно V 2 >

и- і 2

= 1- ' X '

2

\ її. \

1 - Р2 = 1

5) Величина t есть математическое ожидание времени Гр, проходящего между моментом включения ЭТУ в работу и моментом ее следующего выхода из строя. б

а

Работает

Не работает

Не работает

Работает

в Представим работу ЭТУ в стационарном режиме как состоя-щую из ряда циклов: «работает» и «не работает» (на рис. 10.27, в участки работы показаны утолщенной линией). Среднее время tnp, в течение которого ЭТУ не работает (математическое ожидание длительности нерабочего периода), очевидно равно 1 / (2р) (так как на ЭТУ, находящееся в состояние «не работает», действует поток переходов в «рабочее» состояние с интенсивностью 2р).

Далее, отношение среднего времени бесперебойной работы tp к среднему времени простоя t равно отношению финальной веро-ятности 1 — р2 того, что ЭТУ работает, к вероятности р2 того, что оно не работает: t /t = (1 - р2) / р2. Отсюда, учитывая, что гпр =1/(2,4 Wnp1

Р2 = 1 1 ~ Р2 2р р2

Р2 10.28. Условия и вопросы те же, что и в задаче 10.27, с той раз-ницей, что пока один из узлов работает, другой находится в «хо-лодном резерве» и выходить из строя не может. При включении резервного узла он немедленно начинает работать и подвергается потоку отказов с интенсивностью X.

Решение. Граф состояний ЭТУ будет иметь вид, показанный на рис. 10.28, а, граф с «поглощающим состоянием» — на рис. 10.28, б. X^ x^ 50 51 52 2p M-

Рис. 10.28 Ответы на вопросы:

1 beat - aebt

ає0І-ЬеЬі Pat - Ры

ab ab (a — b) X

1) Po(t)=- + (X + Зц) 5 + 2|І,

a — b

a — b

oV-(х+ад ^ 2[i t ht Л

РЛЧ= ;—7\—+—;—гг(ае +be )+—тІе ~e ]+-iw);

ц.(а— b) ц,(а—o) a — b ji a _ -(2\ + 3\i,) + ^4[iX + [i2 -(2X + 3|i,) + + |x2 _ ; _ ; 31

eat -e0t a - p

at

P?

a - (3

ae

2) p0(t) =

_ ~(2\ + [і) + ^4\[і + [і2

p2(t) = L- p0(t)- рГ(І); OL

—(2X [і) — ^[i2 _ _

P = y ; p(0 = I-P2(0;

^ x

3) Pi = — Pol P2 = M- 1 fX] 2 т X , 1 2 — Pol Ро = 1 + —+ - — 2 IMJ 2 Ім-J X+Y х^ 5о sl 52 и- 2(1 Рис. 10.29

10.29. Условия задачи 10.27 изменены таким образом, что неработающий узел находится в «облегченном резерве» и выходит из строя с интенсивностью X7 < X. 1) По-строить граф состояний ЭТУ, написать уравнения Колмогорова для вероятностей состояний. 2) Не решая этих уравнений, найти финальные вероятности состояний; вычислить их для Х = 1;Х' = = 0,5, [і = 2. 3) Для этих же численных данных найти среднее время t? бесперебойной работы ЭТУ.

Решение. 1) Граф состояний показан на рис. 10.29. Уравнения Колмогорова: dp0 _

dt

= -(Х + X7) р0 +\ірг\ dPi_ dt

2>

= -(X + [i)Pl + (X + \')p0 + 2 [ip Po + Pi + P2 = L

2) Финальные вероятности состояний найдем, пользуясь общими формулами (10.0.23) для схемы гибели и размножения:

Х + Х' (Х + Х')Х

Pi = Ро; Р2 = ———Ро;

м2|л Р о =

1+X + V+(X + X/)X Подставляя сюда X = 1, X' = 0,5, р = 2, получаем Р0 = jl + М + 1?l1\ ~ 0,516; рг « 0,387; р2 « 0,097.

4 р2

10.30. В состав ЭВМ входят четыре накопителя на магнитных дисках (НМД). Бригада в составе четырех человек обслуживающего персонала проводит профилактический ремонт каждого диска. Суммарный поток моментов окончания ремонтов для всей бригады — пуассоновский с интенсивностью Х(?). После окончания ремонта диск проверяется; с вероятностью р он оказывается работоспособным (время проверки мало, и им можно пренебречь по сравнению со временем профилактики). Если диск оказался неработоспособным, то вновь проводится его профилактика (время, потребное на нее, не зависит от того, проводилась ли ранее профилактика) и т.д. В начальный момент все НМД нуждаются в профилактическом ремонте.

Построить граф состояний для системы S (четыре НМД), написать дифференциальные уравнения для вероятностей состояний. Найти Мт — математическое ожидание числа дисков, успешно прошедших профилактику к моменту т.

Решение. SQ — все четыре НМД нуждаются в профилактиче-ском ремонте; Sj — один НМД успешно прошел профилактику, а три НМД нуждаются в профилактическом ремонте; s2 — два НМД успешно прошли профилактику, а два нуждаются в профи-лактическом ремонте; 53 — три НМД успешно прошли профилактику, один нуждается в профилактическом ремонте; s4 — все четыре НМД успешно прошли профилактику.

То, что каждый профилактический ремонт заканчивается ус-пешно с вероятностью р, равносильно р-преобразованию потока окончаний ремонтов, после которого он остается пуассоновским, но с интенсивностью р\ (t).

Граф состояний показан на рис. 10.30. Уравнения Колмогорова:

(10.30.1)

dpA / dt = p\(t)p3.

dp0 / dt = -p\(t)p0; dpl / dt = p\(t)(p0 - рг); dp2 /dt = p\(t)(p1 — p2); dp3 /dt = p\(t)(p2 -p3);

Начальные условия р0 (0) = 1; рг (0) = ... = рА (0) = 0. Математическое ожидание числа дисков, успешно прошедших профилактику к моменту т, равно

Мт =?><( т). (10.30.2)

і=І

При постоянной интенсивности X решениями уравнений (10.30.1) будут:

~\pt .

\3

і =0

В условиях предыдущей задачи за каждым членом бригады закрепляется свой НМД, который он ремонтирует. Поток окончаний профилактики, приходящийся на одного члена бригады, имеет интенсивность \(t) / 4 Ответить на вопросы предыдущей задачи.

Решение. Граф состояний дан на рис. 10.31. Уравнения Кол-могорова:

dp о / dt = -p\(t)pQ; dpl /dt = p\(t)(pQ -(3/4)^); dp2 / Л = рХ(0((3/4)Рі -(l/2)p2); dp3 / dt = p\(t)(( 1 / 2)p2 - (1 / 4)ps); dp, / Л = (1 / 4)pX(0 p3.

Выражение (10.30.2) дляМт сохраняется.

p X(t) IpX(t) ipX(t) ipX(t)

I I »} |—I I I

Рис. 10.31

Рис. 10.32 X V S2 Техническое устройство (ТУ) подвергается простейшему потоку отказов с интенсивностью X. Отказ обнаруживается не сразу, а через случайное время, распределенное показательно с параметром у. Как только отказ обнаружен, производится осмотр ТУ, в результате которого оно либо направляется в ремонт (вероятность этого р), либо списывается и заменяется новым. Время осмотра — показательное с параметром % время ремонта — показательное с параметром |л, время замены списанного ТУ новым — показательное с параметром х- Найти финальные вероятности состояний ТУ. Определить: 1) какую долю времени в среднем ТУ будет рабо- тать нормально; 2) какую долю времени ТУ будет работать с необнаруженным отказом (давать брак);

какова средняя стоимость ремонтов ТУ и его замен за единицу времени, если средняя стоимость ремонта равна г, а нового ТУ равна с;

какова средняя величина потерь за единицу времени от ТУ, работающего иногда с необнаруженным отказом, если такое ТУ приносит в единицу времени убыток I

Решение. Состояния ТУ: s0 — исправно, работает; sx — неисправно, но отказ не обнаружен, дает брак; s2 — неисправность обнаружена, ведется осмотр; s3 — ремонтируется; s4 — заменяется новым. Граф состояний дан на рис. 10.32.

Линейные алгебраические уравнения для финальных вероятностей состояний:

Хр0 = № + ХР*; Хр0 = ург; ург = чр2; р чр2 = рр3;

(1 -р)чр2 =ХР4.

г [ X [ X [ рХ [ (1-р)Х

Нормировочное условие Ро + рх + р2 + Рз + р4 = 1. Решая эти уравнения, получаем:

Ро

У 1 М- X

X X

Pi = — Рі = — Рої у ч

рХ (1 -Р)Х Рз= Ро\ Р 4= РоМ- X

1) Доля времени нормальной работы ТУ равна р0; 2) рг; 3) ТУ проводит в среднем долю времени Рз в состоянии ремонта; каждый ремонт длится в среднем 1 / р; поток отремонтированных ТУ, выходящих из состояния 53, имеет интенсивность рр3; средняя стоимость ремонтов в единицу времени грр3. Аналогично средняя стоимость новых ТУ в единицу времени с х 5 °бщая средняя стоимость того и другого равна грр3 + с\р4 \ 4) средние потери от работы ТУ в неисправном состоянии за единицу времени равны I У рх.

10.33. Рассматривается процесс накопления информации в базах данных, хранимых в ЭВМ. Интенсивность поступления единиц информации в базы данных равна \(t) и не зависит от того, сколько их накоплено. Каждая единица информации, поступившая в базы данных, хранится в них бессрочно. Найти характеристики mx(t)y Dx (t) случайной функции X(t) — числа накопленных единиц информации в базах данных в предположении, что поток поступлений единиц информации пуассоновский с интенсивностью X (t) и в начальный момент времени t = 0 случайная функция Х(0) = 0.

Решение. В этой задаче мы имеем дело с процессом «чистого размножения» без ограничения числа состояний (га —> оо). Все интенсивности «размножения» Х^. =\(t) (рис. 10.33) и интенсивности «гибели» рд. = [ik (t) = 0.

Рис. 10.33

Дифференциальные уравнения (10.0.24) и (10.0.25) для этого случая примут вид

dmx(t)

5>(0А(0 = Ч0;

dt к=о

dD (t) 00

л j- = ?[X(0 + 2fcX(0-2m,(0X(0]A(0 = X(t),

Л

А:=0

так как

к—0 к=0

Решая эти уравнения для начальных условий тх (0) = Dx (0) = = 0, получаем

mx(t) = Dx(t) = f\(r)dr.

о

Этот результат можно было ожидать; его можно найти непосредственно из теории потоков. Можно доказать, что случайная величина X(t) для любого момента времени t будет подчинена закону Пуассона с найденными характеристиками mx(t) = Dx(t).

10.34. Условия те же, что и в предыдущей задаче, за исключением того, что принятая на хранение в базах данных единица информации хранится некоторое время, после чего по определенному признаку исключается из баз данных. Поток исключений для каждой единицы информации — пуассоновский с интенсивностью p(t).

Решение. В этой задаче имеет место процесс «гибели и размножения» числа единиц информации, хранимых в базах данных ЭВМ.Интенсивность гибели \ik (t) — k\x(t), так как в состоянии sk в базах данных накоплено к единиц информации и на каждую из них действует поток исключений с интенсивностью \х (t).

Дифференциальные уравнения для функций mx(t)nDx (^имеют вид

dm (t) 00

—jr1 = Е(МО - *»*(*)) Л (0 = МО - тЛУХММА)

dt fco

+2тЛ0М0Ы0 = Ч0 + ^(0™Л0-2^(0?>Л0, (Ю.34.2) так как

Ея-(0 = і; Е^-(0 = ™Л0;

E*2Pi (0 = = ДЛО + mj(0k=0

Для начальных условий тх(0) — т0, Dx(0) = D0 постоянных интенсивностей пополнения и исключения единиц информации X (t) = X; ц (t) = ц решения этих уравнений будут иметь вид X

X

и

X

¦\lt

тх (0 — т0е~^ +-(1 -е~*) = - + е

м- М- -2(1«

-ЦІ

-pi

— 2е

1 е - + М'

Dx(t)=\

+

М'

+ (X + \iD0 + |xm0) -м-* \ _

+D0 (2е-2^ - е"^ ) = mx(t) + (D0-m0)e Для начальных условий т0 = D0 = 0 получим mx(t) = Dx(t) =

= — (l - ). Можно доказать, что для этих начальных условий Мпроцесс накопления информации X(t) будет распределен по закону Пуассона для любого момента времени t и для любого вида функции \(t) (интенсивности поступления информации), но для этого интенсивность исключения единиц информации [х должна быть постоянной.

При постоянных X и р, и ? —> оо в системе будет устанавливаться стационарный режим накопления информации, который, естественно, не будет зависеть от начальных условий: тх —Dx =

= \/VL.

10.35. Рассматривается процесс производства ЭВМ определенного вида. Интенсивность производства ЭВМ \(t) представлена на графике рис. 10.35, а. Эта интенсивность линейно возрастает в течение первого года производства от 0 до 1000 ЭВМ в год, затем три года производство сохраняется на уровне 1000 ЭВМ в год, после чего ЭВМ снимается с производства. Средний срок эксплуатации ЭВМ 5 лет. Считая все потоки событий простейшими, определить математическое ожидание и дисперсию числа ЭВМ, находя-щихся в эксплуатации в любой момент времени t.

Решение. Интенсивность производства ЭВМ

\(t) = 0 при t <0; kt при 0<< < 1; X при 1 < t < 4; 0 при t > 4,

где к = 1000 1/год2; X = 10001/год.

Найдем решения уравнений (10.34.1) и (10.34.2) для участка времени 0 < t < 1 и при условии, что р = 0,2 1/год для любых участков t> 0. Уравнение (10.34.1) при этих условиях имеет вид

at

Решая это уравнение для начального условия тх (0) = 0, получаем є""5 -1 + - 5J

mx(t) = jL(e-v* -l + pi) = 25000 По истечении одного года в эксплуатации будет в среднем тх (1) = 25 000(е~1/5 - 1 + 0,2) = 468 ЭВМ. Заметим, что если бы

ЭВМ имели неограниченный срок службы, то их к концу года было бы в эксплуатации 500 ЭВМ.

Уравнение (10.34.2) при тех же условиях имеет вид

dDx (t) j dt — lOOQfc + 0,2mx (t) - 0,4Dx (t).

Решая это уравнение для начального условия Dx (0) = 0, получаем Dx (t) = тх (t) = 25 000 (e~t/5 - 1 + t / 5). По истечении одного года дисперсия числа ЭВМ, находящихся в эксплуатации, будет равна Dx — 468; ах = 21,6. Число ЭВМ, находящихся в эксплуатации по истечении года, будет приближенно подчинено нормальному закону с характеристиками тх = 468; ох =21,6.

На участке времени 1 < t < 4 соответствующие уравнения будут иметь вид

at at

Их нужно решать при начальных условиях: mx(l) = Dx(l) = 468. Решение этих уравнений было найдено в за-даче 10.34, откуда

mx(t) = тх(1)е-^ + ^(1 - е-^-1)) (1 < t < 4);

МDx(t) = mx(t).

Найдем значение rnx (t) для t = 4:

mx(4) = mx(l)e"311 + — (1 — e~3li) = 2513.

МТаким образом, среднее число ЭВМ, находящихся в эксплуатации к концу четвертого года выпуска, будет равно 2513. Обратим внимание на то обстоятельство, что к этому времени было выпу

а

Sh

I \Хг({)\ 1 \x2(t) I 1 \X3(t) \Xk(t)

б

mx{t)

3500 3000 2500 2000 1500 1000 500 3500 / /

— / /

_ ?X 2513 - / шу

1 1 1 1 1 \920 і 1 1 1 23 456789 10 t, годы в

щ

щено в среднем 3500 ЭВМ. Следовательно, в среднем за четыре года было исключено из эксплуатации 987 ЭВМ.

На участке времени t > 4 будет иметь место процесс «чистой гибели», граф состояний которого показан на рис. 10.35, б.

Дифференциальные уравнения для математического ожидания и дисперсии процесса чистой гибели в общем случае имеют вид

^--ёмОлС);

dt km 0

dD (t) 00

= (0 - 2k2\ik(t) + 2mx(t)k[Lk (t)]pk (t).

dt k—0

Для нашего случая \ik (t) = fcp, следовательно, получим уравне-ние

dt /с—О

которое нужно решать при начальном условии тх (4) = 2513. Решение этого уравнения будет иметь вид

mx(t) = mx(4)е-^-4> (t > 4).

Так как Dx (4) = тх (4) и р = const, то Dx(t) = тх (t) на участке времени t > 4.

На рис. 10.35, в показана зависимость mx(t) — среднего числа ЭВМ, находящихся в эксплуатации от времени t. На этом же графике пунктирной линией показана зависимость от t среднего числа выпущенных ЭВМ к моменту времени t

10.36. Рассматривается процесс накопления терминов в динамическом словаре (тезаурусе) при функционировании автоматизированного банка данных (АБД). Сущность процесса в том, что термины заносятся в словарь по мере их появления в той информации, которая вводится в АБД. Например, в АБД автоматизированной системы управления производством (АСУП) могут в качестве терминов заноситься наименования организаций, с которыми данное предприятие поддерживает производственные отношения. Динамический словарь наименований таких организаций будет накапливаться в АБД АСУП по мере появления этих наименова-ний в единицах информации, вводимых в АБД.

В каждой единице информации, поступающей в АБД, в среднем встречается х терминов словаря, а интенсивность поступления единиц информации в АБД \(t). Следовательно, интенсивность потока терминов словаря в информации, поступающей в

АБД, будет = Предполагается, что поток терминов

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

Решение. Обозначим X(t) число терминов, накопленных в динамическом словаре. Очевидно, что случайный процесс X(t) есть процесс «чистого размножения» с конечным числом состояний п, граф состояний которого представлен на рис. 10.36. Для нахождения интенсивности Х^(t) (к = 0,1,... ,п — 1) введем в рассмотрение гипотезу О ТОМ, ЧТО процесс находится в СОСТОЯНИИ SfcJ н^и Vi An-lW bn —\\(t) Vi(*)i—іЧ(')

Рис. 10.36 вероятность этой гипотезы по определению равна рк (t). В предположении, что эта гипотеза имеет место, интенсивность потока новых (еще не занесенных в динамический словарь) терминов будет 1-А

п)

Xt(f) = X(t)—= Х(І)

П Дифференциальные уравнения (10.0.24) и (10.0.25) примут вид: А'

п ,

dmx(t)

= Емо і

dt

А;=0

к ) 1-А

п,

1-А]

п ,

= ?

к=о к

1-- п

dDx(t)

X(t)

dt

п

-2mx(t)\(t) = 10.36Л)

+ 2 k\(t)

- (10.36.2)

Dx(t)

п Найдем решение этих уравнений для простейшего случая, ко

гда

X (t) = X = const; п = const; тх( 0) = Dx (0) = 0, ~t

(10.36.3)

mx(t).

lim mx(t) = n;

(10.36.4)

f -±4) -±t -h

Dx(t) = n 1-е " e " = mx(t)e " ;

/—> oo lim 0,(0 = 0.

t—>00 Обратим внимание на то, что функция тх (t) монотонно увеличивается, стремясь в пределе к тг, в то время как функция Dx(t) равна нулю при г=0и?—>оои достигает своего максимума при некотором значении tm, которое можно найти из условия dDx(t)/dt = 0(t>0).

Отсюда

1тп

0,5 = е 71 -*tm «0,7п / X.

При этом значении tm максимальная дисперсия max Dx(t) «

і

« п (1 — е-0'7) е-0'7 = п 0,25; ох (tт ) = 0,5л/п, а максимальное значение коэффициента вариации ox{tm) / mx{tm) = l / 4п.

Если известна интенсивность X потока терминов словаря в единицах информации, поступающих в АБД, и общее число тер-минов п, то можно с достаточной точностью определить среднее время tH, потребное для накопления 95 % объема динамического

словаря: 1-е 71 = 0,95, откуда tH « Зп / X.

Если п неизвестно (что чаще всего на практике имеет место), то можно найти оценку п величины п следующим образом. Для моментов времени т1? т2, т3,..., Т1(Ті <т.+1) определяют фактические количества накопленных терминов в словаре mv mv ..., тг. Полагаем эти величины приближенно равными средним коли-чествам накопленных терминов: mi =п (1 - е"Хт,/п )(г = 1, 2,...,/).

Решая это уравнение относительно п, находим I значений nv п2, ..., П/для соответствующих пар значений: (m15 т2); (ш2, т2); (mh т1). Оценку п находим по формуле

10.37. Для условий предыдущей задачи найти время tu запол- ления словаря на 95 % и вероятность того, что через два года после начала накопления словаря он будет содержать не менее 90 % всех терминов, если общее число терминов п = 100 000, в год в АБД вводится 100 000 документов и каждый документ содержит в среднем 1,5 термина.

Решение. Найдем интенсивность потока терминов словаря в единицах информации, вводимых в АБД:

X = 100000 .1,5 = 150000 1/год.

Величина tu определяется из выражения tH=3n/\ =

= 3 • 100 000:150 ООО = 2 года. Для определения вероятности того, что через два года после начала наполнения словарь будет содержать не менее 90 % всех терминов, нужно прежде всего найти тх{2) и Dx (2) [см. формулы (10.36.3) и (10.36.4)]: тх(2) = = 100 000 х (1 — е-1'5'2 ) = 0,95 .100 000 = 95 000; Dx (2) = 95 000-0,05 =

= 4750; сг д. (2) = 68,9.

Заметим, что максимальная дисперсия Dx(tm) = 0,25 п = 25 000; a,(im) = 158.

Число терминов в словаре в момент времени t = 2 года есть случайная величина Х(2), приближенно распределенная по нормальному закону с найденными выше характеристиками; поэтому Р (Х(2) > 0,9n} « 1, так как тх -3ах >0,9п.

10.38. Рассматривается более общий случай функционирования динамического словаря АБД. Первое усложнение по сравнению с условиями задачи 10.36 состоит в том, что максимальное число терминов словаря п не является постоянным, а зависит от времени t. n(t) (в случае с динамическим словарем названий организаций это означает, что общее число организаций со временем изменяется: увеличивается или уменьшается).

Кроме того, введенные в динамический словарь термины по истечении некоторого случайного времени исключаются из словаря в связи с тем, что сам термин устаревает. Предполагается, что поток исключений термина в динамическом словаре — пуассоновский с интенсивностью |i (t), одинаковой для всех терминов словаря.

В этом случае интенсивности потоков «размножения» и «гибе-ли» будут иметь вид \k(t)=\(t)

1

; = (Ю.38.1)

n(t) а уравнения (10.0.24) и (10.0.25) примут вид (зависимости от времени t функций mx{t), Dx(t), n(t), \(t), іл (t), pk (t) для краткости опущены):

dmx / dt = X - mx (X / n 4- |i); dDx / dt = X - mx (X / n - p.) - 2 (X / n + \i) Dx. (10.38.2)

Если величины X, n, |Л постоянны (не зависят от времени), то при t —> оо существует стационарный режим работы, для которого dmx / dt = dDx j dt — 0, откуда

/ \-1 [in )

= n

1 + —

fin )

1 + ЇЇІІ ; D,=m,

<< | >>
Источник: Е. С. ВЕНТЦЕЛЬ, Л. А. ОВЧАРОВ. ЗАДАЧИ И УПРАЖНЕНИЯ ПО ТЕОРИИ ВЕРОЯТНОСТЕЙ. 2003

Еще по теме ГЛАВА 10потоки событий. марковские случайные процессы:

  1. ГЛАВА 6СИСТЕМЫ СЛУЧАЙНЫХ ВЕЛИЧИН (СЛУЧАЙНЫЕ ВЕКТОРЫ
  2. ГЛАВА 9 случайные функции
  3. ГЛАВА 7ЧИСЛОВЫЕ ХАРАКТЕРИСТИКИ ФУНКЦИЙ СЛУЧАЙНЫХ ВЕЛИЧИН
  4. ГЛАВА 8ЗАКОНЫ РАСПРЕДЕЛЕНИЯ ФУНКЦИЙ СЛУЧАЙНЫХ ВЕЛИЧИН. ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ТЕОРИИ ВЕРОЯТНОСТЕЙ
  5. ГЛАВА 5СЛУЧАЙНЫЕ ВЕЛИЧИНЫ. ЗАКОНЫ РАСПРЕДЕЛЕНИЯ. ЧИСЛОВЫЕ ХАРАКТЕРИСТИКИ СЛУЧАЙНЫХ ВЕЛИЧИН
  6. НЕОБХОДИМОСТЬ И СЛУЧАЙНОСТЬ
  7. События
  8. СЛУЧАЙНОСТЬ
  9. СОБЫТИЕ
  10. СЛУЧАЙНОСТЬ
  11. НЕОБХОДИМОСТЬ И СЛУЧАЙНОСТЬ
  12. * § 5. Необходимость и случайность