Цепи Маркова (1121219), страница 57

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 57)

(Один серьезный недостатоксостоит в том, что мигрирующие заявки совершают случайное блужданиепо сети; другой недостаток — времена обслуживания на разных станцияхнезависимы, третий — распределение обслуживания определяется станцией (зависит от станции), а не заявкой, которая обслуживается.)Формально сеть Джексона с J станциями представляет собой случайноеблуждание с непрерывном временем на неотрицательном ортанте целочисленной решетки ZJ+ . В случае двух станций (J = 2) это неотрицательныйквадрант Z2+ , а состоянием является пара n = (n1 , n2) неотрицательныхцелых чисел n1 , n2 ∈ Z+ .Таким образом, i|n = i .Замечание 2.10.11.

Свойство, подчеркнутое в примере 2.10.10, часто называют так: пуассоновские прибытия видят усреднение во времени(ППВУВ) 16 .Аналогичное свойство для замкнутых сетей рассматривается в следующем примере.Пример 2.10.12. Рассмотрим замкнутый процесс миграций (N(t)) состанциями 1, . . ., J и K циркулирующими заявками.

Предположим, чтоматрица маршрутизации R заданной цепи неприводима и — такой вектор,что T R = 0 и все компоненты i положительны. Пусть, далее, (K) —инвариантное распределение для (N(t)), определенное в формуле (2.10.4), § 2.10. Ветвящиеся процессы с непрерывным временемn1i(K)(Ni = n),где i (K) (Ni = n) — частота прибытий на станцию i, на которой уже находится n заявок, n = 0, 1, . . . , K − 1. Докажите, чтоfi|n =(K −1)(Ni = n),где (K −1) (Ni = n) — частота наблюдения n заявок на станции i, n == 0, 1, .

. . , K − 1. Здесь (K−1) — инвариантное распределение для замкнутого процесса с K − 1 заявками.Сети Джексона занимают исключительное место среди ц.м.н.в., поскольку для них можно произвести точные (и элегантные) вычисления16 Ванглийском оригинале: PASTA, Poisson arrivals see time averages. — Прим. перев.Рис. 2.73В результате случайный вектор N(t) имеет две компоненты N 1 (t)и N2 (t), представляющие число объектов на станциях 1 и 2 соответственно.Для простоты предположим, что диагональные вероятности перехода p 11и p22 равны 0, так что матрица маршрутизации P имеет вид0 p12P=.(2.10.28)p210Далее, очевидно, что вероятности уходов таковы:p∗1 = 1 − p12 и p∗2 = 1 − p21 .(2.10.29)Интенсивности скачков n → n , введенные в уравнении (2.10.9), указаны на рис.

2.74. У этой модели есть шесть независимых неотрицательныхпараметров, а именно 1 , 2 , p12 , p21 и 1 , 2 .0fi|n =nJгде n =  ...  ∈ ZJ+ и n1 + . . . + nJ = K. Для заданного i = 1, . . . , J определим362Глава 2. Цепи Маркова с непрерывным временем§ 2.10. Ветвящиеся процессы с непрерывным временем363а) для внутренних точек Z2+ ( n1 , n2 > 1):,n01 = n1 + 1, 1n01 = n1 − 1,1 (1 − p12), ,n01 = n1 ,12bn,n0 = внутр ×pqn01 = n1 ,2 (1 − p21),n01 = n1 + 1,2 p21 ,n01 = n1 − 1,1 p12 ,n02 = n2 ,n02 = n2 ,n02 = n2 + 1,n02 = n2 − 1,n02 = n2 − 1,n02 = n2 + 1,(2.10.31)qнач :=+1+22+211,2,+2,если n1 , n2 > 1, т.

е. точка n лежитвнутри квадранта Z2+ ,если n1 > 1, n2 = 0, т. е. точка n 6= 0 лежитна горизонтальной полуоси Z+ ,если n1 > 1, n2 = 0, т. е. точка n 6= 0 лежитна вертикальной полуоси Z+ ,если n1 = n2 = 0, т. е. точка n лежитв начале координат 0.(2.10.30)bn,n0 скачков n = (n1 , n2) →Соответственно, для цепи скачков вероятности p→ n0 = (n01 , n02) будут ненулевыми только для пар ближайших соседейn, n0 ∈ Z2+ , где |n1 − n01 | + |n2 − n02 | = 1, и для пар вида: точка и следующаяпосле ближайшего соседа точка, т. е.

таких пар, что n 01 − n1 = n2 − n02 = ±1.При этом вероятности скачков задаются так:1+2,++г) в начале координат (n1 = n2 = 0):(b0,n0 =p1×qнач1,2,n01 = 1, n02 = 0,n01 = 0, n02 = 1.Сосредоточимся теперь на некоторое время на этом примере. МатрицыI − P и (I − P) −1 имеют вид11 −p121 p12−1, (I − P) =.(2.10.34)I−P =1−p211 − p12 p21p211Видим, что матрица I − P обратима тогда и только тогда, когда p 12 p21 < 1.Соответственно, вектор пропускной способности , определяемый изTсоотношения T = (I − P) −1 (см.

формулу (2.10.16)), задается формулой11 + 2 p21=,qверт :=1+qгор :=1qвнутр :=Суммарная интенсивность qn скачков из состояния n = (n1 , n2) такова:Рис. 2.74б) на горизонтальной полуоси Z+ ( n1 > 1, n2 = 0):n01 = n1 + 1, n02 = 0,1, (1 − p ), n0 = n − 1, n0 = 0,1112112bn,n0 = гор ×p00q,n=n,n2112 = 1,0n1 > 1, n1 = n1 − 1, n2 = 0, n02 = 1,1 p12 ,(2.10.32)в) на вертикальной полуоси Z+ (n1 = 0, n2 > 1):n01 = 1, n02 = n2 ,1, p ,n1 = 0, n01 = 1, n02 = n2 − 1,12 21bn,n0 = верт ×p(2.10.33)qn01 = 0, n02 = n2 + 1,2,n01 = 0, n02 = n2 − 1,2 (1 − p21),1 − p12 p211 p12+2364Глава 2. Цепи Маркова с непрерывным временем§ 2.10.

Ветвящиеся процессы с непрерывным временем3651 + 2 p21<1 − p12 p211,1 p21 + 2<1 − p12 p21==12а неравенства (2.10.19) принимают вид2.(2.10.35)которые показывают средний снос во внутренней области Z 2+ и на горизонтальной и вертикальной частях границы Z 2+ соответственно. (Четвертыйвектор Eнач , который совпадает с и приписывается началу координат, неимеет существенного значения.) Более точно,∗111 − 1 p1 − 1 p12 + 2 p211 − 1 + 2 p21=Eвнутр = внутр,∗внутрq21Eгор = горqEверт =11qверт−−2 p2+∗1 p11 p12−−2 p211= горq1 p122+1+ 2 p21∗2 p2 − 2 p212−1 p12q1qверт=22−1− 1,+ 1 p12+ 2 p21,2− 212+1 p12(2.10.36)(2.10.37)212−1 p12−2 p21 −(1++<1+E22)p12 p21 ,(2.10.41)и правая часть неравенства (2.10.41) меньше правой части неравенства(2.10.40) (так как i 6 i < i , i = 1, 2).Таким образом, если мы хотим, чтобы цепь (N(t)) была положительновозвратной, то вектор Eвнутр должен быть направлен по крайней мере наодну из полуосей, образующих границу Z2+ (возможно, и на обе).

Удобновыделить взаимно исключающие случаи: а) вектор E внутр направлен на обеполуоси, б) вектор Eвнутр направлен на вертикальную полуось, но не направлен на горизонтальную, в) вектор Eвнутр направлен на горизонтальнуюполуось, но не направлен на вертикальную.E2тогда как суммируя неравенства (2.10.35), мы получаемE2Рис. 2.75Таким образом, неравенства (2.10.35) необходимы и достаточны для положительной возвратности ц.м.н.в.

(N(t)) для сети Джексона с двумястанциями. Иными словами, неравенства (2.10.35) описывают областьположительной возвратности в пространстве параметров 1 , 2 , p12 , p21и 1, 2.Интересно сравнить неравенства (2.10.35) со средними векторов скачков, возникающими из рис. 2.74 и уравнений (2.10.31) – (2.10.33). Мыимеем три вектора: внутр гор верт E1E1E1, Eгор =, Eверт =,Eвнутр =внутргорверт(2.10.38)2+1 p12>0212−1 p12−+>+противоречат неравенствам (2.10.35). Действительно, суммирование неравенств (2.10.39) приводит к неравенству12 p21 ,Рис. 2.76(2.10.39)(2.10.40)Рассмотрим сначала случай а); см. рис.

2.76. Тогда в силу соотношения(2.10.36) имеем неравенства, противоположные неравенствам (2.10.39):внутрE1внутр, E2< 0, т. е.1+2 p21<1и2+1 p12<−2> 0,2 p211+−1где нормирующие знаменатели qвнутр , qгор и qверт задаются формулой(2.10.30). (На самом деле в нижеследующих вычислениях эти множителине фигурируют.)внутрвнутрЗаметим сначала, что если у вектора Eвнутр обе компоненты E1 , E2внутр2неотрицательны (т.

е. Eсмотрит «из» границы Z+), то ц.м.н.в. (N(t))не может быть положительно возвратной. См. рис. 2.75.Это верно, поскольку неравенства2.(2.10.42)366Глава 2. Цепи Маркова с непрерывным временем§ 2.10. Ветвящиеся процессы с непрерывным временем367<1 p12 ,2 p21+<1 p12 p212 p21 p12+1 p12Умножим первое неравенство на p12 , а второе — на p21 :2 p21 .(2.10.43)+2+12 p21 ,<2 p21 p12 <1 p12 p21+1 p12 +2 p21+1 p12 +2 p21+2+1Затем сложим первое неравенство из (2.10.42) и второе неравенство из(2.10.43) и отдельно сложим второе неравенство из (2.10.42) и первоенеравенство из (2.10.43):1 p12 .Рис.

2.77Рассмотрим вначале случай б). Тогда левая часть рис. 2.77 соответствует неравенствамEвнутр< 0, Eвнутр> 0 и EвнутрEверт− EвнутрEверт> 0.122112(2.10.44)внутр ⊥, Eверт i(2.10.45)222 p21)>(1−1+2 p21) ( 2−+1 p12) ( 1+−(Возвращаясь к соотношениям (2.10.36), (2.10.37), перепишем последнее неравенство в (2.10.44) в виде2);2 1>2 1 (1 − p21 p12),1 1 p12+после сокращений получаем2+1 p1>что эквивалентно неравенству2 (1 − p12 p21).1+2 p21<1,2+1 p12>2,2+1 p12<Это неравенство противоположно первому неравенству в (2.10.35). Следовательно, неравенства (2.10.44) исключают положительную возвратность.С другой стороны, система (2.10.45) эквивалентна системе неравенствозначает вектор, полученный поворотом по часовой стрелке вектора E внутрна угол /2 (поворот по часовой стрелке, так как вертикальная ось притаком повороте становится направленной внутрь положительного квадранта).Аналогично в случае в), если Eгор смотрит в сторону от вектора Eвнутр(или параллелен ему), то ц.м.н.в.

(N(t)) не может быть положительновозвратной.вертвнутр верт< 0, Eвнутр> 0 и EвнутрE1 − E1 E2 < 0.22=внутрE1внутр ⊥положительно возвратна. См. рис. 2.77, где вектор E +внутрE2−Eвнутр1Последнее неравенство означает, что скалярное произведение hE +положительно.Правая часть рис. 2.77 соответствует неравенствамПосле очевидных сокращений получаем неравенства (2.10.35). Следовательно, случай а) приводит к положительной возвратности. Иными словами, область параметров 1 , 2 , p12 , p21 , 1 и 2 , которая описываетсянеравенствами (2.10.42), лежит строго внутри области параметров, задаваемой неравенствами (2.10.35).Этот факт можно проинтерпретировать на интуитивном уровне.

Неравенства (2.10.42) утверждают, что интенсивность обслуживания на каждойстанции достаточно велика, чтобы справиться с «экстремальной» ситуацией, когда другие станции постоянно заняты (непусты). Действительно,1 + 2 p21 задает общую суммарную интенсивность прибытий на станцию1, когда станция 2 занята, и аналогично для 2 + 1 p12 . Поэтому не вызывает удивления такой факт: если сеть может справиться с таким потоком,то положительная возвратность обеспечена.Как видим, если неравенства (2.10.42) выполняются, то ц.м.н.в. (N(t))положительно возвратна.

Характеристики

Список файлов лекций