Цепи Маркова (1121219), страница 60
Текст из файла (страница 60)
Это дает значение (v),аналог значения (2.11.3), полученного для очереди с одним сервером. Равенство (2.11.2) перепишется в виде 11lim ln P max[vi t − ε, 0] < Qi (tn) < vi t + ε,nn→∞ ni = 1, . . . , J, 0 < t < Ti= −T (v).(2.11.37)Следует отметить, что весь этот продолжительный анализ имеет своей целью проверкувсех траекторий векторного процесса (с измененныммасштабом) (Q(tn) n) вблизи луча, направленного вдоль вектора v.
(Посути такой анализ имеет смысл проводить, только если мы хотим изучитьпереполненную сеть Джексона, когда j > j для некоторого j, j = 1, . . . , J.В этой ситуации может представлять интерес анализ тех возможностей,когда процесс (Q(tn) /n) уходит в бесконечность.) В нашем случае в силуусловия (2.11.16) важным значением v является значение v = (v 1 , 0, . .
. , 0).С. Т. Колеридж (1772–1834), английский поэт= 0,0When the last rookBeat its straight path along the dusky air.i (s)j ∈ (Λ ∪ {i}) , опять проверяем неравенстваДля этих значений(2.11.30) ∀ k ∈ (Λ ∪ {i}) :X∗Λ∪{i}∗Λ∪{i}Λ∪{i} ∗Λ∪{i}Λ∪{i}− l():=+m(e−)ek6 k.kllkkl∗Λ∪{i}∨ср. с (2.11.28), (2.11.32). В результате получаем (|Λ| + s) -мерный векторc, vi − R(Λ∂l∈Λ∪{l}∗Λ∪{i}(...................................= ( l ∈ Λ) — (неизвестный) неотрицательный вектор размерЗдесьΛности |Λ|, i — (неизвестное) неотрицательное число, а H Λ∪{i} ( ∨ i)определяется (модифицированной) формулой (2.11.25).∗Λ∪{i}задачи (2.11.32),Мы вновь приходим к единственному решению∗Λ∪{i}компоненты которого lположительны, l ∈ Λ ∪ {i}.
Как и прежде,мы хотим расширить этот (|Λ| + 1)-мерный вектор до J-мерного вектора,положив для этого X∗Λ∪{i}∗Λ∪{i}Λ lΛ= lnmjl e+ mj0 , j ∈ (Λ ∪ {i}) c .(2.11.33)jh}∂ Λ∪{i,...,i (s) }H(∂ i(2.11.32)Λl ,∗Λ∪{i},jc(s)ΛHΛ∪{i,...,i∂ Λ∪{i}H(∂ i∨ i) = vΛ ,ΛΛΛHΛ∪{i} (Λgradgrad(2.11.31)e . Рассмотрим задачу (2.11.27), (2.11.28),Теперь возьмем произвольное i ∈ Λ«распространенную» на станцию i:.i>l∈Λ∗Λi381Λ ∪ {i, i 0 }.
И так далее: этот процесс должен будет когда-нибудь закончиться, поскольку, когда мы прибавим все Λc к Λ, уже не останется ниодного неравенства для проверки. Пусть {i, i 0 , . . . , i (s) } — множество, гдевсе процедуры (начавшиеся с i ∈ Λc) завершаются. Тогда решаем уравнениястанций, для которых не выполняются неравенства:XcΛ ∗ΛΛ− ∗Λel:= i +mil l e− l eΛ= i∈Λ : i§ 2.11. Большие уклонения для цепей Маркова с непрерывным временемГлава 2. Цепи Маркова с непрерывным временем380{1}H{1} ( 1) = m10 ( 1 (e 1 − 1) +1 (e−1− 1)),(2.11.38)Решение задачиThat is the Path of WickednessThough some call it the Road to Heaven) = v1 .(2.11.39)Нас интересует некое особенное значение v1= (v1 , 0, . .
. , 0)), когда{1}v1 = m10 ( 1 − 1).(т. е. вектора v =j=1В самом деле, подставляя ∗1 = ln 1 − ln 1 в правую часть равенства(2.11.39), проверяем, что оно выполняется.Кроме того, функция H {1} обращается в нуль в точке ∗1 :(2.11.41)1 − 1)∗{1}Оно эквивалентно неравенству{1}mj111{1}+ mj0 6j{1}− 1)) (mj1 e 1 + mj0 ) 6∗1{1}( j + mj1 ( 1 e−jЧтобы проверить, что соотношение (2.11.41) дает окончательный ответ,нам необходимо проверить, что для любого j 6= 1 выполняется неравенствоj.(2.11.42)(2.11.43)p120и=21=1 + 2 p21,1 − p12 p212=1 p12 + 2;1 − p12 p21(2.11.44)ср.
с (2.10.35). Если мы предположим, что1>11>2(2.11.45)2(см. (2.11.16)), то вектор v∗ = (v∗1 , 0) из формулы (2.11.18) будет иметьпервую компонентуp + p12 p20( 1 − 1).(2.11.46)v∗1 = 10откуда следует, что преобразование Лежандра в точкеимеет вид{1}H{∗1} (v1) = m10 ( 1 − 1) (ln 1 − ln 1).{1}{1}v 1 = m10 ( 1 − 1)v1 =m10 (0Джексона с двумя станциями с параметрами = 1 , P = p212 1=суммарные интенсивности прибытий задаются какH{1} ( ∗1 ) = 0,1i=1пользовать для получения соотношения (2.11.15).Пример 2.11.1 (cеть Джексона с двумя станциями).
сети Для открытой1 − ln 1 .= ln∗1{1}эволюционирует вдоль вектора v = (m10 ( 1 − 1), 0 . . . , 0), легко объяснить. Нам известно, что при условии (2.11.16) инвариантное распределениеобразовано произведением геометрических сомножителей i,JPi = 1, . . . J. Следовательно, инвариантная вероятностьQj = na соi=1 J naP11бытияQj = na не превосходит CJJ−.
Этот факт можно ис+na(2.11.40)принимает вид∗1В действительности вышеуказанный факт, состоящий в том, что еслиJPQj достигает высокого уровня na, то процессобщая длина очереди11e−−Три ворона, ирландская баллада1>0> 0 уравнения∗1d {1}{1}H ( 1) = m10 ( 1 ed 11задается единственным решениеммаксимизировать [ 1 v1 − H{1} ( 1)] поВ этом случае383и выполняется благодаря тому, что станция 1 в неравенстве (2.11.16)является критической.{1}Значение v1 = m10 ( 1 − 1) выделяется тем, что соответствующий вектор v = (v1 , 0, .
. . , 0) доставляет минимум преобразованию Лежандра R ∗функции R по всем векторам из RJ+ . В терминологии больших уклоненийэто означает, что оптимальный способ аккумулировать большое числоклиентов в сети состоит в том, чтобы поставлять их линейно (во временн о́й{1}шкале с измененным масштабом) со скоростью m10 ( 1 − 1) на критическую станцию, сохраняя сублинейный рост в остальной части сети.Тогда вышеописанная процедура упрощается: условия (2.11.30) выполняются ∀ k = 2, . . .
, J. А именно, здесь Λ = {1}, и преобразование Лежандрафункции = ( 1 , . . . , J) 7→ R ( ) (для вектора v с единственной ненулевойкомпонентой v1) относительно переменных 1 , . . . , J совпадает с преобразованием Лежандра относительно переменной 1 следующей функции:§ 2.11. Большие уклонения для цепей Маркова с непрерывным временемГлава 2. Цепи Маркова с непрерывным временем3821 − p12 p21Глава 2.
Цепи Маркова с непрерывным временемТак будет определяться 1 направление,вдоль которого процесс с изме1Q (nt), Q2 (nt) будет эволюционировать, когданенным масштабомn 1nобщая длина очереди Q1 (nt) + Q2 (nt) достигнет уровня na. Ср. с уравнением (2.11.19) и рис. 2.83.§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем385§ 2.12. Вопросы к теории цепей Марковас непрерывным временем, заданные на экзаменах«Математические треножники» в КембриджскомуниверситетеThe -dity of the Bad, the -ty of the Good(Or the Other way Around)384(Из серии «Фильмы, которые не вышли на большой экран».)Задача 2.12.1.
а) Рассмотрим ц.м.н.в. с состояниями 1, 2, 3, 4 и производящей матрицей−211001 1 −2 1 0 Q=.0 1 −2 1 1−2Представьте эту цепь графически. Пусть цепь выходит из состояния 1.Найдите вероятность того, что в момент времени t цепь находится в состоянии 1.б) Рассмотрим теперь цепь с пятью состояниями 1, 2, 3, 4 и 5 и производящей матрицей−3100011 1 −3 1 0 1 Q = 0 1 −3 1 1 . 1 0 1 −3 1 000Пусть цепь выходит из состояния 1.
Сравнив эту матрицу с матрицей,рассмотренной выше, найдите вероятность того, что в момент времени tцепь находится в состоянии 1.Решение. а) Цепь попадает в заданные четыре состояния в прямомили обратном циклическом порядке. Иными словами, эта цепь ведет себякак две независимые марковские цепи (Xt) и (Yt), каждая цепь имеет двасостояния, скажем 0 и 1, и прозводящую матрицу−1 1Q = 1 −1 .Можно представить это так, что пара (Xt , Yt) переходит из одного углаквадрата [−1, 1] 2 в один из соседних, причем с равными вероятностямиперехода в каждый из них; см.
рис. 2.84.Глава 2. Цепи Маркова с непрерывным временемРис. 2.84Следовательно, искомая вероятность записывается в виде(p11 (t)) 2 = (A + B−2t) 2 .Из условий при t = 0 и t → ∞ находим A = B = 1/2. Это приводит к ответу(1 + e−2t) 2 4.б) В новой цепи добавятся поглощающее состояние 5 с интенсивностьюпоглощения 1. Следовательно,P (цепь не находится в состоянии 5 в момент t) = e−tнезависимо от начального распределения .
Тогда в силу независимостиP (состояние цепи в момент времени t такое же, как и в момент 0) = e−t =(1 + e−2t) 2 .4Задача 2.12.2. а) Рассмотрим случайное блуждание (Xn) n>0 на графе,представленном на рис. 2.85.§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем387На каждом шаге этот процесс переходит в соседнюю вершину с равными вероятностями и независимо от прошлых переходов: это означает, чтоиз C процесс переходит в A, B, D или E с вероятностью 1 /4 для каждойиз этих вершин. Четко формулируя все общие теоремы, которые вы будетеиспользовать, покажите, что P (Xn = A) имеет предел при n → ∞, и найдитеэтот предел.б) Для случайного блуждания (Xn) n>0 из а) найдите среднее числопопаданий в C, прежде чем процесс, стартовавший из A, впервые вновьвернется в A.Пусть теперь (Zt) t>0 — ц.м.н.в.
на графе из а), и пусть элементы ееQ-матрицы имеют вид(1, если (i, j) является ребром,qij =0 в противном случае.Пусть S обозначает суммарное время, проведенное в {C, E} цепью(Zt) t>0 , выходящей из B, прежде чем она впервые вернется в B. Покажите,что S имеет показательное распределение, и найдите его параметр.Решение. а) Для неприводимой апериодичной ц.м.д.в. с инвариантнымраспределением выполняется соотношениеP (Xn = j) →j∀jпри n → ∞ независимо от начального распределения .
В данной задачец.м.д.в. представляет собой случайное блуждание на графе. Она неприводима и апериодична (длины всех циклов. Pвзаимно простые), ее инвариантноераспределение таково, что i = vivk , где vj — кратность вершины j.P kПоскольку суммарная кратность vk равна 28, мы получаем P (Xn = A) =k= 2/28 = 1/14.б) Для неприводимой апериодичной ц.м.д.в. с инвариантным распределением выполняется соотношенеE i (число попаданий в j до возвращения в i) =,iчто приводит к ответу vC /vA = 2.Использование симметрии помогает при рассмотрении сгруппированной цепи с состояниями B, (C, E), (A, F), D, (I, G), H.
Тогда все интенсивности переходов (C, E) → B, (C, E) → (A, F) и (C, E) → D равны 1.Следовательно, для (Zt) t>0 время, проведенное в (C, E) или E при каждомпосещении, становится экспоненциальным, с интенсивностью = 3. ПриРис. 2.85j386388Глава 2. Цепи Маркова с непрерывным временемi=1n>1q.q −=−n X XNXi =(1 − q) n−1 qE expкаждом посещении вероятность возвращения в B равна 1 /3. Это означает,что число попаданий в {C, E} до возвращения в B является геометрической величиной с параметром q = 1/3. Сумма случайного числа (имеющегогеометрическое распределение) независимых показательных случайных величин имеет показательное распределение с интенсивностью q , поскольку,например, производящая функция моментов такова:Следовательно, S имеет показательное распределение с интенсивностью 1.Задача 2.12.3.
а) Пусть (Xt) t>0 — ц.м.н.в. с пространством состояний{1, 2, 3, 4, 5} и Q-матрицей вида−31011 1 −3 1 0 1 Q = 0 1 −3 1 1 . 1 0 1 −3 1 00000Для случая X0 = 1 найдите вероятность того, что Xt = 2 при некоторомt > 0.б) Для цепи, описанной в п. а), в предположении, что X 0 6= 5, найдите вероятность того, что ц.м.н.в. (Xt) t>0 в конце концов посетит каждоесостояние.Решение. а) Из описания цепи получаем уравнения для h i == P i (попасть в 2):h2 = 1,h 1 = h3 =11+ h4 ,3323h 4 = h1 ,откуда следует, что h1 = 3/7 и h4 = 2/7. В силу симметрииP i (попасть в j) = 3/7 для любой пары смежных углов, и эта вероятностьравна 2/7 для любой пары противоположных углов i, j.б) Условие, накладываемое на начальное распределение , означает,что 5 = 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
