Цепи Маркова (1121219), страница 56
Текст из файла (страница 56)
совпадает со инвариантным распределением для M/M/1/∞-цепи Маркова, когда процессприбытий является процессом Пуассона ПП ( j) и интенсивности обслуживания равны j . См. уравнение (2.9.8). Однако мы не можем утверждать,что процесс (Nj (t)) стохастически эквивалентен процессу (Q(t)), задающему длину очереди, который генерируется этой цепью M /M/1/∞ в состоянии равновесия. Таким образом, общий процесс прибытий на станцию jне обязан быть процессом Пуассона ПП ( j).В действительности общий вид процесса, задающего общее число прибытий на заданную станцию сети Джексона (замкнутой или открытой),остается неизвестным.
Нетрудно исследовать случай, когда матрица маршрутизации P открытой сети не оставляет возможностей для циклов, т. е.задания перемещаются вдоль графа, представляющего собой направленноедерево. См. рис. 2.71 а). При таком ограничении процесс, задающий общеечисло прибытий на станцию j, в состоянии равновесия действительно является процессом Пуассона ПП ( j). В частном случае эта так называемаятандемная сеть, где задания могут перемещаться только слева направо.См.
рис. 2.71 б).=1 p1В этих примерах пропускную способностьобрjна станции j можно вы-= ... ,Рис. 2.71∗J pJjnjjP (Nj (t) = n) = 1 −j355eq§ 2.10. Ветвящиеся процессы с непрерывным временемгдеГлава 2. Цепи Маркова с непрерывным временем354Глава 2. Цепи Маркова с непрерывным временем§ 2.10. Ветвящиеся процессы с непрерывным временемобрjа вероятности выходов p∗j обр — как357= j p∗j , j = 1, . . . , J;(2.10.24)356б) вектор интенсивностей обслуживания тот же;обрв) матрица маршрутизации pобр = (pij ) определяется так:обрpij == j pji непосредственно следуют соотношенияобрpij =jобрijpji =ipji .Чтобы проверить состоятельность такой конструкции, обратим внимание на следующие положения.обра) Обращенная во времени матрица маршрутизации P обр = (pij ) является субстохастической. Это следует непосредственно из определений:jобр обрi pij, j = 1, .
. . , J.3. Из равенствjjp∗j обр =ipji , i, j = 1, . . . , J.Следствием теоремы 2.8.10 является аналог теоремы Бурке для открытых сетей Джексона; см. теорему 2.10.7. Она описывает структурувыходных потоков для рассматриваемой сети. Для заданной станции j,представим процесс (Nj (t)) (число заявок на станции j) таким же образом,как и в (2.9.14):XX(t) +Ai→j (t) −Dj→k (t) − Dвыход(t).
(2.10.26)Nj (t) = Nj (0) + Aвходjj= 1 ∀ i, j = 1, . . . , J.(j=1) =(ij=1−jjj=j=1−j pji.jудовлетворяет (2.10.15), т. е.обр Tобр T=1−J1 Xобр T обр) +() P, или (обробрpijобр T) (I − Pобр) = (обр T) .jipji =jii∗∗j pj + j (1 − pj )=ji=pji =iX= j p∗j +обр обрi pijXX= j p∗j +обр+j=обр+ ( обр) T Pобр jjЭто тоже легко получить:обрj∀ j = 1, . . . , J.В результате получаем следующую теорему.Теорема 2.10.6.
Пусть имеют место обозначения и выполняютсяпредположения теоремы 2.10.3. Тогда в состоянии равновесия обращенный во времени процесс (Nобр (t)) соответствует открытой сети обр Джексона со следующими параметрами:а) вектор интенсивностей прибытийв видеобр1 = ... задаетсяобрJ1заданной сети, а= ... — неотрицательный вектор, который аннулиJруется матрицей R: T R = 0T .
Предположим, что матрица R неприводимаобри i > 0, i = 1, . . . , J. Образуем матрицу маршрутизации R обр = (rij ), гдеобрrij =б) Вектор=1−JXp∗j обрКроме того, обращенные во времени вероятности выходов имеют видj = 1, . . . J, обозначают (независимые пуассоновские) входЗдесьные потоки. Далее, (Ai→j (t)) — это процесс прибытий на станцию j из i(t)),и (Dj→k (t)) — это процесс переходов из станции j в k.
Наконец, (D выходjj = 1, . . . J, обозначает процесс выходов из сети.Теорема 2.10.7. В условиях теоремы 2.10.3 в состоянии равновесия (т. е. при N(0) ∼ , где = ( n) определено в формуле (2.10.20)) длялюбого T > 0 выполняются следующие условия:а) процессы (Dвыход(t)), . . ., (Dвыход(t)) являются независимыми про1Jвыход(t)) ∼ ПП ( j p∗j ), j = 1, .
. . , J;цессами Пуассона: (Djб) процесс (N(t + T), t > 0), описывающий состояние сети Джексона после момента времени T, не зависит от процесса (D(t), 0 6 t < T),который подсчитывает выходы из сети до момента T.Мы не будем приводить доказательство теоремы 2.10.7, так как по сутионо лишь повторяет доказательство теоремы 2.9.2 (хотя и с техническимисложностями ввиду векторной природы процесса (N(t))).Пример 2.10.8. Рассмотрим замкнутую сеть Джексона в состоянииравновесия.
Докажите, что ее обращение во времени опять является сетьюДжексона.Решение (набросок). Пусть R = (rij) — матрица маршрутизации для jj=1ii6j=1j pjik(t)),(Aвходji1обрpij =обрpij > 0,J1 XiJX(2.10.25)irji , i, j = 1, . . . , J.(2.10.27)Глава 2. Цепи Маркова с непрерывным временем1Машина обращенного времени15(Из серии «Фильмы, которые не вышли на большой экран».)Пример 2.10.9. В птичнике с K птицами находится лишь один бассейндля купания птиц. Купаются птицы индивидуально, время купания каждой птицы имеет показательное распределение со средним −1 . Покинувбассейн после купания, птица летает где-нибудь неподалеку в течениепериода времени, имеющего показательное распределение со средним −1 ,прежде чем приземлиться для очередного купания.
Если у бассейна ужеесть птицы, вновь прилетевшая птица ожидает в очереди. Все временакупаний и времена полетов независимы. Пусть X(t) — число птиц, которыене летают в момент времени t. Выпишите Q-матрицу цепи Маркова (X(t))и покажите, что стационарное распределение имеет вид ii=k=01(K − k)! k −11(K − i)! iчто и требовалось показать.Стационарное распределение b цепи {Yn } имеет видbY0 =0Ki(+ (K − i) ),i = 1, . . .
K.Наконец, мы наблюдаем цепь {Zm }, когда {Yn } совершает скачоквверх, т. е. Yn = Yn−1 + 1. Следовательно, стационарное распределение bZцепи {Zn } таково:bY ,bZj ∝ bYj Pjj+1b Y обозначают вероятности перехода в цепи (Yn):где Pjj+1b Y = 1,P01Таким образом,, i = 0, 1, .
. . , K.bZi ∝(K − i), 1 6 j 6 K − 1.+ (K − i)bY =Pjj+1 i(K − 1 − i)!∝ i− 1(K − 1 − i)!.Отсюда получаем последнее утверждение.Пример 2.10.10. Рассмотрим открытую сеть Джексона со станциями1, . . ., J, векторами интенсивностей прибытий и облуживания и и субстохастической матрицей маршрутизации P. Предположим, что матрицаI − P обратима и выполняется условие неперегрузки < , где — векторTпропускной способности и T = (I − P). Рассмотрим эту сеть в состоянииравновесия с таким инвариантным распределением , как в уравнении(2.10.20). Для заданных i = 1, .
. . , J и n > 0 определим i|n — интенсивностьприбытий, «застающих n заявок на станции i», следующей формулой:i=i+1 ,i = 0, . . . , K − 1,с названием фильма «The Time Machine».=11× × E (число прибытий на станцию j(Ni = n)tв период времени от 0 до t, когда уже есть n заявок в узле i).Докажите, что для любых i и n выполняется равенство= i.15 Ср.(K − i)Уравнения детального баланса имеют видi|nРис. 2.72Найдите стационарное распределение цепи скачков {Y n , n > 0}. Пустьm — время m-го приземления после момента времени 0, и Z m == X( m +) − 1.
Рассмотрев процесс { (Yn , Yn+1), n > 0} (или иным способом), покажите, что стационарным распределением цепи Маркова{Zm , m > 1} является j(K−1) , j = 0, 1, . . . , K − 1.Решение (набросок). См. рис. 2.72, где i — число птиц не в полете.bYi =,XKi = 0, . . . , K,k=0=XK k −1 i 111∝,(K − i)!(K − k)!(K − i)!(K)i359откуда получаем стационарное распределение для (X(t)):Проверяем, что T Rобр = 0T . Затем проверяем, что описание обращенногопроцесса (Nобр (t)) соответствует конструкции, задающей сеть Джексонав состоянии равновесия с Q-матрицей Rобр и теми же самыми стационарJQnkными вероятностями n ∝k , что и у исходного процесса (N(t)).§ 2.10.
Ветвящиеся процессы с непрерывным временем358i|nГлава 2. Цепи Маркова с непрерывным временемРешение (набросок). Напомним, чтоi=P360l pli .Обозначим третийlсомножитель (математическое ожидание) символом E t . Тогда в силу стационарности инвариантного режима Et удовлетворяет равенствуEt1 +t2 = Et1 + Et2 , t1 + t2 > 0.Следовательно, Et = At, где A > 0 — некоторая постоянная. Чтобы найтиA, рассмотрим Et при малых значениях t:XEt = (Ni = n)l pli to(t),lA = lim (Ni = n) i .t→0361(до определенной степени). В самом деле, мы можем найти в явномвиде условие положительной возвратности (см. формулу (2.10.19)) и соответствующее инвариантное распределение (см. формулу (2.10.20)). Этообусловливает постоянный интерес к этой модели, несмотря на ее очевидные недостатки с точки зрения приложений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
