Цепи Маркова (1121219), страница 59
Текст из файла (страница 59)
Большие уклонения для цепей Маркова с непрерывным временем375основе вышеприведенных аргументов, пока остается достаточно хрупким.Рассмотрим случайную величину na — время достижения уровня na процессом (Q(t)):(2.11.14)na = inf [t > 0 : Qt > na] .Асимптотическое поведение na описывается соотношением: ln nalim P − a ln < ε = 1 ∀ ε > 0,nn→∞(2.11.15)т.
е. na ≈ ( / ) na . Этот факт можно объяснить следующим образом. Процесс (Q(t)) «пытается» достичь уровня na, продвигаясь вблизи оптимальной траектории v∗ t. Большинство таких попыток безуспешно (и тогдапроцесс падает к нулю и начинает новую, почти независимую, попытку).Однако существует экспоненциально малый шанс успеха таких попыток,что и приводит к формуле (2.11.15).374Этот... путь легок,Но возврата нет.С. Г.
Росетти (1830–1894), английский поэтНаш путь возникает на время,А затем уходит в мечты.Е. С. Доусон (1867–1900), английский поэтОднако интуитивное понимание больших уклонений, возникающее на<j,j = 1, . . . , J(см. соотношение (2.10.19)). Определимнаиболее загруженную станциюс максимальным отношением ( j j); для простоты предположим, что такая станция единственна и соответствует j = 1:hii: i = 2, . .
. , J .(2.11.16)1 > 1 > max2vпри v > 0. Минимум величины (2.11.13) достигается при v ∗ = − , и онравен ∗ (a) = a ln( / ).j1iВновь рассмотрим момент временине меньше na. Тогда lnlim P n→∞nna ,когда общая длина очередиPQj (t)jna− a ln1Этот факт можно объяснить следующим образом.
Рассмотрим все возможные траектории процесса с измененным масштабом (Q tn /n), которыеведут к уровню a. Поскольку мы рассматриваем прибытия, независимыеот состояния, и процесс обслуживания также не зависит от состояния,можно ожидать, что «оптимальный путь» находится среди прямых линий.Это означает, что нам необходимо оптимизировать правую часть равенства(2.11.2) относительно v (или, что эквивалентно, относительно T = a /v).Таким образом, минимизируемqh v + pv2 + 4 ia+ + − v2 + 4v ln(2.11.13)Рис.
2.82Посредством прямых, но аналитически громоздких вычислений формулы (2.11.1) – (2.11.15) можно преобразовать в строгое доказательство; см.[SW] .Перейдем теперь к сетям Джексона. Мы будем следовать статье:Ignatiouk-Robert I. Large deviations of Jackson networks // Annals Appl.Prob. 2000. V. 10. P. 962–1001. Предположим, что задана устойчивая (неперегруженная) открытая сеть, где1 < ε = 1 ∀ a, ε > 0,(2.11.17)376Глава 2.
Цепи Маркова с непрерывным временемт. е. сеть достигает высокого уровня общего числа клиентов, когда переполняется ее «узкое место» — ее критическая станция. Мы видим, чтосоотношение 1∗1 (a) = a ln11n377P1Q1 (t), . . . , QJ (t) , вдоль которой сумма Qj (nt) достигает уровня na,njследует вдоль прямой линии в J-мерном неотрицательном ортанте RJ вдольпервой оси (соответствующей длине очереди на станции 1) с векторомскорости v∗ . (Если дописать время, размерность будет J + 1 и вектор будетиметь вид (v∗1 , 0, . .
. , 0, 1). Иными словами, мы движемся вдоль прямойv∗ t.) Для J = 2 см. рис. 2.83.является аналогом равенства (2.11.9).Далее, выборочный путь, который картина больших уклонений рисуеткак наиболее правдоподобный, можно задать следующим образом. Положим{1}(2.11.18)v∗1 = m10 ( 1 − 1), v∗ = (v∗1 , 0, . . . , 0).§ 2.11. Большие уклонения для цепей Маркова с непрерывным временем{1}Здесь постоянная m10 представляет вероятность того, что запрос, находящийся в текущий момент на станции 1, не вернется на эту станциюв будущем (т. е. покинет сеть, не возвращаясь на эту станцию):pij1 .
. . pjk 0 ,(2.11.19)k>1 j1 ,...,jk =2Рис. 2.83i− 1).заданного(2.11.21)вектораv== ( 1 , . . . , J) > 0.i (ei=1Оптимальным значением для этой задачи будет в точности преобразованиеЛежандра R∗ (v), которое мы обозначим (v):hi(v) = max h , vi − R( ) : = ( 1 , . .
. , J) > 0 .(2.11.22)∗1 (a),(2.11.20)что является аналогом соотношения (2.11.12).Интерпретация вновь такова: сеть достигает высокого уровня na общего числа запросов, «собирая» их на критической станции и поддерживая низкий уровень очереди на остальных станциях. В геометрическихтерминах оптимальная траектория процесса с измененным масштабомВид функции (v) в формуле (2.11.22) зависит от того, сколько компонент v, и какие именно, равны 0.
В простом случае имеем v > 0, т. е. все∗vj положительны. Тогда процедура вполне проста: значение , доставляющее максимум в формуле (2.11.22), является единственным решениемуравнения grad R( ) = v для градиента функции R( ):=−i∗∗∗(v) = h , vi − R( ), где grad R( ) = v.a, j = 2, . . . Jv∗10 6 Qj (u) 6 εn, 0 < u <JXдлямаксимизировать [h , vi − R( )] по11a= lim ln P v∗1 t − ε < Q1 (tn) < v∗1 t + ε, 0 < t < ∗ ,nv1n→∞ nsup [Q1 (s) : s > 0] > na,−1 +задача:jiiQj (s) : s > 0 > na =h hXsupj=1ij+ pi0 eНас интересует следующая= (v1 , .
. . , vJ) > 0, v 6= 0,h pij e−i=111Xaln P v∗1 t − ε <Qj (tn) < v∗1 t + ε, 0 < t < ∗ ,nv1n→∞ nlimij− iТогдаR( ) =XJJXl=1Основой для этих вычислений служит аналог уравнений (2.11.1) – (2.11.4)для сетей. А именно, начнем с аналога функции R( ):где pj0 (ранее это было p∗j ) означает вероятность покинуть сеть, выйдя состанции j:JXpjl > 0, j = 1, .
. . , J.pj0 = 1 −JX X{1}m10 = p10 +(2.11.23)= −T (v) ∀ T > 0.(2.11.24)Λ, vΛ i − HΛ ( )] поΛ= ( i , i ∈ Λ), гдеi > 0.(2.11.27)Λgrad HΛ ( ) = vΛ ,(2.11.28)i∈Λi−Xj∈ΛΛimj ji (e − 1) +X XmΛ+iij eXΛHΛ ( ) =i∈Λj∈Λl∈ΛДалее, для любой станции i ∈ Λc проверим неравенствоX∗ΛΛ ∗ΛΛ− ∗Λl():=+m(e−)e i 6 i.illiil(2.11.30)l∈ΛЕсли неравенства (2.11.30) выполняются для всех i ∈ Λ c , то мы дополним |Λ|-мерный вектор ∗Λ до J-мерного вектора ∗Λ , прибавив комcпоненты eΛi , i ∈ Λ , вычисленные в формуле (2.11.29).
Тогда мы получим(единственное) решение задачи максимизации (2.11.22) для заданного v.Приведенный далее анализ того случая, когда вектор v содержитнекоторые нулевые компоненты, является более сложным, и можно посоветовать читателю пропустить его при первом чтении. Пусть Λ (= Λ v)обозначает множество {i : vi > 0} и Λc = {i : vi = 0}. Это означает, чтовектор v определяет луч, выходящий из начала координат, который лежитна границе ∂RJ+ , т. е. на поверхности меньшей размерности |Λ|.
Тогдазначение, доставляющее максимум в задаче (2.11.22), может лежать награнице ∂RJ+ или внутри RJ+ , т. е. мы должны сравнить значения в точках,доставляющих локальный максимум, причем некоторые из этих точек могутлежать в ∂RJ+ .ΛПустьобозначает (переменный) вектор размерности J с ненулевымикомпонентами из множества Λ. Мы хотим рассмотреть задачу максимизации только по переменным i , i ∈ Λ; это будет возможно, если мы слегкаизменим функцию R. А именно, положимУ.
Уитмен (1819–1892), американский поэтДолгий... путь ведет меня к цели, какую бы я ни выбралгде vΛ задает сужение начального вектора v на Λ. Эта система из |Λ|уравнений в силу тех же причин, что и ранее, приводит к единственному∗Λрешению— вектору размерности |Λ| с компонентами ∗Λi > 0, i ∈ Λ.Оптимальное значение в задаче (2.11.27) задается преобразованием Ле∗Λ Λ∗Λ∗ Λжандра: HΛ(v ) = h, v i − HΛ ( ).∗ΛНам еще необходимо дополнить вектордо вектора размерности J∗Λ(который мы также обозначим).
А именно, положимX∗ΛΛ ∗ΛΛcl=lnme+m(2.11.29)iili0 , i ∈ Λ .ΛМаксимум доставляется (единственным) решением задачиСвязь между уравнениями (2.11.24) и (2.11.20) в точности такая же, каки между уравнениями (2.11.2) и (2.11.8), поэтому ∗ (a) является оптимальным значением для (v). Иными словами, чтобы найти ∗ (a), мы должныминимизировать аналог выражения (2.11.13) для сети Джексона.максимизировать [h=(Напомним, что pi0 и pj0 — это вероятности покинуть сеть со станций i и j,соответственно).
Тогда задача принимает следующий вид:ik>1 j1 ,...,jk ∈Λch 11ln P vi t − ε < Qi (tn) < vi t + ε, i = 1, . . . , J, 0 < t < Tnn→∞ nlim379Здесь для i ∈ Λ и j ∈ Λ ∪ {0} значение mΛij — это вероятность того, чтозапрос, находящийся в текущий момент на станции i, достигнет станции j(покинет сеть, если j = 0), не посещая множество Λ в промежуточныемоменты времени:X Xpij1 . .
. pjk j , i ∈ Λ, j ∈ Λ ∪ {0}.(2.11.26)mΛij = pij +∗При этом оказывается также, что> 0. Иными словами, значение, накотором достигается максимум, лежит строго внутри ортанта R J+ . (Свой∗ство > 0 выполняется в силу выпуклости функции R( ) по .) Отметим,что равенство grad R( ) = v образует систему J скалярных уравнений, поодному уравнению для каждой компоненты vi , i = 1, . . . , J.С геометрической точки зрения вектор v > 0 определяет луч, выходящий из начала координат, который лежит внутри ортанта R J+ . Тогда аналогуравнения (2.11.2) имеет вид§ 2.11. Большие уклонения для цепей Маркова с непрерывным временемГлава 2.
Цепи Маркова с непрерывным временем378И следовал скрытым путем, которымшли лишь очень немногие мудрецы мира!j− i− i+ mΛ−1 .i0 eФ. Луис де Леон (1527–1591), испанский теолог и поэт(2.11.25)Однако неравенство (2.11.30) может не выполняться для несколькихe v) ⊆ Λc — множествоe (= Λ(или даже всех) i ∈ Λc .
Пусть в этом случае Λ∨ i) = 0.∂l∈Λ∪{i}(2.11.34)Если все неравенства (2.11.34) выполняются, мы добавляем к вектору∗Λ∪{i}∗Λ∪{i}компоненты k, k ∈ (Λ ∪ {i}) c , найденные в формуле (2.11.32).∗Λ∪{i}. ИсПолученный в результате J-мерный вектор опять обозначимпользуем его для вычисления значения целевой функции (2.11.22):).Λ∨i . . . ∨ i (s) )∨i ∨ . . . ∨ i (s) )i ∨ . . . ∨ i (s) )= vΛ ,= 0,(2.11.35)(s)}(ΛHΛ∪{i,...,i∗Λ∪{i,i 0 ,...,i (s) }. Далее повторяем определения (2.11.28) и (2.11.32) дляЕсли некоторые из неравенств (2.11.34) не выполняются, выбираемсоответствующую станцию i0 и повторяем вышеизложенную процедуру для∗Λ∪{i,i 0 ,...,i (s) }Λ ∪ {i, i , . . .
, i (s) } и определяем дополнительные компоненты k,k ∈ (Λ ∪ {i, i 0 , . . . , i (s) }) c . Прибавив эти дополнительные компоненты∗Λ∪{i,i 0 ,...,i (s) }к, получим J-мерный вектор, который, как и прежде, будем∗Λ∪{i,i 0 ,...,i (s) }. Алгоритм заканчивается вычислением величиныобозначатьh∗Λ∪{i,i 0 ,...,i (s) }, vi − R (∗Λ∪{i,i 0 ,...i (s) }).(2.11.36)На завершающем этапе мы сравниваем значения (2.11.36), полученныедля разных начальных узлов j ∈ Λc и добавленных к ним впоследствииузлов i 0 , . . . , i (s) , и выбираем минимальное из них.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
