Цепи Маркова (1121219), страница 55
Текст из файла (страница 55)
. , J (т. е. допустимо любое значение n = (n1 , . . . , nJ), где nj ∈ Z+), т. е.возможные состояния ц.м.н.в. (N(t)), n ∈ ZJ+ .Далее, P = (pij) образует субстохастическую матрицу J × J вероятностейперехода (называемую также матрицей маршрутизации) с элементамиJбудет предполагаться неотрицательным, а векторt→∞независимо от начального распределения. Еслиудовлетворяетуравнениям детального баланса (2.10.5), то ц.м.н.в. (N(t)) с этиминвариантным распределением обратима, и наоборот.Далее перейдем к открытым процессам миграции, или открытым сетям Джексона. В этой модели задается семейство независимыхвходных потоков (A (i) (t)) ∼ ПП ( i), i = 1, .
. . , J. С другой стороны, такжеразрешается выход из системы; это меняет устройство модели. В частности, i будет обозначать интенсивность обслуживания на станции i. Как1= ... .k=1=,= ... ,Удобно рассматривать векторы и , задающие интенсивности прибытийизвне и интенсивности обслуживания соответственно: nJY(2.10.9)1образует инвариантную меру для ц.м.н.в. (N(t)).
Если вдобавок удовлетворяет уравнениям детального баланса для R (см. равенства (2.10.5)), топроцесс (N(t)) с инвариантным распределением { n } становится обратимым.Общее число заявок K является неизменной величиной для процесса(N(t)). Таким образом, имеет место теорема.Теорема 2.10.2. Предположим, что матрица R неприводима, ипусть = ( 1 , . . .
, J) — (единственная с точностью до множителя)вектор, такой что k > 0 ∀ k и R = 0. Зафиксируем K и положимИнтенсивности скачков таковы:n 7→ n + i ,интенсивность i(вход извне в систему через узел i),n 7→ n + − , интенсивность p 1 (n > 1)i ijiji(переход из узла i в j),∗→7n−,интенсивностьni pi 1 (ni > 1)i(уход наружу из системы через узел i).JYnJn∝NJ (t)(2.10.6)R = 0T , тоn1n = ... .TТаким образом, если= 0 ∀ j.N1 (t)N(t) = ... ,XJ349и ранее, будем рассматривать векторную ц.м.н.в. (N(t)), где ( T R) j = j rjj +будут выполняться тогда и только тогда, когда векторнентами k > 0 аннулируется матрицей R:§ 2.10. Ветвящиеся процессы с непрерывным временем348pij > 0,JXj=1pij 6 1 ∀ i = 1, .
. . , J,а p∗i — это вероятности выходов из системы:p∗i = 1 −JXj=1pij , 0 6 p∗i 6 1∀ i = 1, . . . , J.350Глава 2. Цепи Маркова с непрерывным временем§ 2.10. Ветвящиеся процессы с непрерывным временем351Как и ранее, образуем вектор 1= ... .JРис. 2.70 = ... все компоненты строго положительны. Поскольку матрица(0)n(0)1(0)J[ j+∗j pj 1(njпереход из узла i в jX> 1)] +ji pij 1(ni> 1) = 0.i,j : i6=j{z(2.10.11)}диагональный членПодставив произведение (2.10.10) в формулу (2.10.11), после сокращений получаем (предполагая, что nj > 1 ∀ j = 1, .
. . , J)i,j6X(0)i .jjik=1k(2.10.10)( j+jj −1ii pij −X∗j pj ) +i,j : i6=jjjjj∗j pj=Xpj ji = 0.(2.10.12)j.(2.10.13)jЧтобы добиться выполнения равенства (2.10.12), попытаемся сгруппировать оставшиеся члены: −1 X −1Xjj∗(2.10.14)j+i pij = j pj +j pji = j ∀ j,.XXn ki,j : i6=jikXjJ Y∗j pj +Заметим сначала, что в состоянииP равновесия общий входящий в систему поток с интенсивностьюj должен компенсироваться общимjP ∗выходящим потоком с интенсивностьюj pj . Отсюда следует, что∝j−Заметим, что, вообще говоря, мы не предполагаем, что диагональныеэлементы pii равны 0, позволяя тем самым заявкам возвращаться на станции. (В некоторых задачах вводится это предположение, чтобы избежатьтехнических сложностей.) Цепь Маркова с непрерывным временем (N(t)),которая описывается интенсивностями (2.10.9), будет называться открытымпроцессоммиграций или открытой сетью Джексона с параметрами, P,.Найдем теперь инвариантные вероятности n в виде произведений геометрических сомножителей:njjP) j =(0)i pijXjji : i6=ji : i6=j(jX+(0) Tj=X −1i(0)ij0XXP субстохастическая, максимальное собственное значение не должно пре(0) T(0) Tвосходить 1.
Действительно, в силу того чтоP= 0, получаем|уход из узла j−Xприбытие в узел jДля простоты в дальнейшем будем предполагать, что матрица маршру(s)тизации P неприводима (т. е. pij > 0 ∀ i, j = 1, . . . , J для некоторого s > 1).Тогда в силу теоремы 1.15.7 норма ||P|| равна максимальному собственному значению0 матрицы P, а у соответствующего собственного вектора Из дальнейшего будет видно, что компоненты j , j = 1, . . .
, J — это суммарные интенсивности прибытий (или нагрузка) в узлах 1, . . ., J (еслипринимать в расчет прибытия как извне, так и из других узлов).Теперь уравнения для инвариантного распределения для любого n ∈ Z J+записываются в видеXXX∗n− j j 1(nj > 1) +n+ j j pj +n+ i − j i pij 1(ni > 1) −{z}| {z } i,j : i6=j |{z}j |jт. е.T+TP, т. е.(I − P) =T.(2.10.15)Предположим, что матрица I − P обратима. Это некоторое ограничение;оно эквивалентно требованию, чтобы норма ||P|| была меньше 1.
В этомслучае матрица (I − P) −1 является суммой геометрической прогрессии:XPk .(I − P) −1 =k>0< ,=т. е. суммарная интенсивность прибытий i в каждом узле j меньше,чем интенсивность обслуживания j . Тогда произведение геометрических вероятностейT(I − P) −1 .(2.10.16)Поскольку матрица P неприводима, у матрицы (I − P) −1 все элементыположительны. Следовательно, для любого неотрицательного вектора интенсивности входного потока 6= 0 вектор имеет компонентыTj>0и, более того,j> j , j = 1, . .
. , J.Видим, что компоненты вектора действительно представляют собойсуммарные интенсивности прибытий (внешние плюс внутренние) в предположении, что в состоянии равновесия для любого jnk=1kk nkkk(2.10.20)t→∞∀nn(2.10.21)независимо от начального распределения.Сохраняющая частныепришедших с холода14 .сеть из ,(Из серии «Фильмы, которые не вышли на большой экран».)1−задает инвариантное распределение = ( n) процесса (N(t)). Крометого, если в матрице маршрутизации P любая пара узлов i, j == 1, . . .
, J сообщается (т. е. pij(s) > 0 для некоторого s > 1), то процесс(N(t)) становится неприводимым с единственным инвариантнымраспределением { n }. В этом случае процесс (N(t)) является положительно возвратным и(2.10.17)Формально, равенство суммарной интенсивности прибытия суммарнойинтенсивности уходов означает, чтоXXXX∗∗(2.10.18)j pj −j = 0, т. е.j=j pj ,jjjjji : i6=jjji : i6=jср. с соотношением (2.10.13).Однако равенство (2.10.18) и в самом деле следует из соотношений(2.10.15) – (2.10.16):XXXXXXXX∗j=j−i pij =j−j pji =j pj .j=J Ylim P (N(t) = n) =интенсивность прибытий в узел j = j равнаинтенсивности уходов из узла j.j(2.10.19)Тогда из соотношения (2.10.15) заключаем, чтоT=T353Таким образом, если предположить выполнение формулы (2.10.15) (т.
е.найти из равенства (2.10.16)), то будет выполняться равенство (2.10.12).В соответствие с условием (2.10.17) вектор называют вектором пропускной способности. На основании вышеизложенного получаем следующийрезультат.Теорема 2.10.3.Пусть(N(t)) — открытый процесс миграций с параметрами, P,. Предположим, что матрица I − P обратима,и введем согласно формуле (2.10.16). Предположим, что покомпонентно выполняется неравенство+ ( P) j = j , илиj§ 2.10.
Ветвящиеся процессы с непрерывным временемГлава 2. Цепи Маркова с непрерывным временем352jЗамечание 2.10.4. Формула (2.10.20) означает, что в состоянии равновесия для заданного момента t длины очередей на различных станцияxв момент t являются независимыми и имеют геометрическое распределение:YP eq (Nj (t) = nj , j = 1, . . .
, J) =P eq (Nj (t) = nj),(2.10.22)j14 Ср.с названием фильма по роману ле Карре «The Spy Who Came in from the Cold».числить в явном виде:, n = 0, 1, . . .(2.10.23)jj+XЗдесь суммированиеPYp i k i k +1 .i→jпроизводится по множеству станций i, предше-i : i≺ jствующих j (это множество может быть и пустым); такие станции образуютсемейство направленных путей в дереве, заканчивающихся в состоянии j.(На рис. 2.71 а) для станции j имеется три предшествующих: i, i 0 и i00 .)Произведение под знаком суммы распространяется на все станции i 1 = i,.
. ., is вдоль пути, ведущего из i в j, где s + 1 — расстояние на графе от iдо j. (На рис. 2.71 а) имеем j = j + i pij + i0 pi0 i pij + i00 pi00 i pij .)Замечание 2.10.5. Если для некоторой станции j выполняется равенствоj=j>jили неравенствоj,то инвариантного распределенияне существует.
(Однако мы все еще имеемQинвариантную меру ∝ ( j / j) nj .) Таким образом, процесс (N(t)) либоjимеет нулевую возвратность, либо невозвратен.Важным вопросом является обратимость во времени сетей Джексона.Как известно из § 2.8, обращение во времени общей ц.м.н.в. приводитк неоднородной ц.м.н.в. (см. замечание 2.8.7). Однако класс сетей Джексона имеет особенность: он замкнут относительно обращения во времени.Иными словами, обращение во времени сети Джексона вновь приводитк сети Джексона.Чтобы показать это, рассмотрим следующие свойства M /M/1/∞-цепей, мотивированные теоремой Бурке и ее доказательством.1.
Суммарный входной поток для заданной станции при обращениивремени превращается в суммарный выходной поток из этой станции. Следовательно, для обращенного процесса (N(t)) вектор нагрузки обр равен .Совпадают также и векторы интенсивностей обслуживания: обр = .обрследует опре2. Аналогично вектор интенсивности входного потокаделить как ∗ii : i≺jОднако этот факт ничего не говорит нам о совместном распределениивеличин (Nj (tj)) в различные моменты времени tj . Следовательно, мы неможем утверждать, что процессы (Nj (t)), представляющие собой длиныочередей на станциях открытой сети Джексона, независимы.Формула (2.10.23) также утверждает, что одномоментное стационарноераспределение (Nj (t)) является геометрическим, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
