Цепи Маркова (1121219), страница 51
Текст из файла (страница 51)
.(2.8.10)0 01 1=2 2,1 1,=...,откуда следует, что10=0,12(2.8.11)=0 110,2...,=i0 ...1 ...i−1i0,...(2.8.12)При этом если ряд, составленный из элементов (2.8.12), сходится, т. e.X Yj−1jn>1 16j6nто решениеiзадается равенствамиX Y0 = 1+i=0 ...i−11 ...i1+< ∞, −1j−1jn>1 16j6nX Yj−1jn>1 16j6n(2.8.13), −1(2.8.14),i > 1.Замечание 2.8.9. Отыскание решений уравнений детального баланса — лишь полдела. Нужно также гарантировать, что ПРГ ( k , k)невзрывной: только тогда решение (2.8.14) даст истинное стационарное распределение, а значит, определит обратимую ц.м.н.в.
Элегантноенеобходимое и достаточное условие10 , обеспечивающее положительнуювозвратность, а следовательно, и обратимость, состоит в том, чтобыдополнить соотношение (2.8.14) требованием расходимости рядовX Yj−1jn>1 16j6n< ∞,X 1 Ynn>116j6njj−1= ∞,(2.8.15)т. е. при условии (2.8.15) стационарное распределение = ( i) из формулы(2.8.14) — истинное стационарное распределение ПРГ ( k , k). Доказательство мы опустим, но заметим, что соотношенияX Yj−1n>1 16j6nj= ∞,X 1 Yn>1n16j6njj−1=∞(2.8.16)дают необходимое и достаточное условие для того, чтобы процессПРГ ( k , k) имел нулевую возвратность, а соотношенияX 1 Yn>1и уравнения детального баланса приобретают вид325Замечание 2.8.6.
Уравнения детального баланса — это удобный инструмент для отыскания стационарного распределения (или, более общимобразом, инвариантной меры). Поэтому если нельзя найти стационарное распределение (или инвариантную меру) из уравнения Q = 0, постарайтесь решить уравнения детального баланса. Если это удается, тодостигаются сразу две цели: находится инвариантная мера (и с помощьюнормализации находится стационарное распределение, если это возможно), и доказывается обратимость.Замечание 2.8.7.
Что происходит, если для заданной ц.м.н.в. уравнения детального баланса не выполняются? Тогда обращенный во временипроцесс (Xtrev , 0 6 t 6 T) отличается от исходной цепи (Xt , 0 6 t 6 T). Тем неменее, процесс (Xtrev , 0 6 t 6 T) является ц.м.н.в., только неоднородной,с переходными вероятностями previj (t, t + s), зависящими от «начального»и «конечного» моментов времени t, t + s. Иными словами, эти вероятности зависят от начального момента t и прошедшего времени s (каки в неоднородном ПП ( (t)) из § 2.4; ср. с уравнением (2.4.7)).
Точнее, длялюбых 0 = t0 < t1 < . . . < tn < t < t + s < T и любых состояний i0 , . . . , in , i, jусловные вероятности определяются по формулам§ 2.8. Сходимость к инвариантному распределению. ОбратимостьГлава 2. Цепи Маркова с непрерывным временем324n16j6nj−1j= ∞,X Yn>1 16j6njj−1<∞(2.8.17)10 См. Karlin S., McGregor J. The classifications of birth and death processes// Trans. Amer.Math. Soc.
1957. V. 86. P. 366–400.326Глава 2. Цепи Маркова с непрерывным временемиrevНо (Drevt ) ∼ (Dt) и (Bt ) ∼ (Bt) благодаря обратимости. Объединим всесоотношения эквивалентности:327rev(Dt) ∼ (Brevt ), вклад процесса рождения в (Xt ).дают необходимое и достаточное условие для того, чтобы процессПРГ ( k , k) был невозвратным (допускается и возможность взрыва);см. [K] .Если i ≡ и i ≡ , то ПРГ однороден; в этом случае он всегданевзрывной.
Тогда условие (2.8.13) эквивалентно неравенству < ; приэтом условии процесс положительно возвратен и обратим. Если = , топроцесс имеет нулевую возвратность, а при < процесс невозвратный.Процессы рождения и гибели обладают следующим удивительнымсвойством.Теорема 2.8.10. Пусть (Xt) — невзрывной, положительно возвратный и обратимый ПРГ ( i , i), и предположим, что выполненосоотношение (2.8.15), а стационарным распределением задано соотношениями (2.8.14).
Рассмотрим процесс в равновесии (т. e. приX0 ∼ ), и запишем(2.8.18)Xt = X0 + Bt − Dt , t > 0,§ 2.9. Применения к теории очередей. Марковские очередиrev(Bt) ∼ (Drevt ) ∼ (Dt) ∼ (Bt ) ∼ (Bt),где процессы (Bt) и (Dt) задают рождение и гибель в процессе (Xt),т. е. (Bt) увеличивается на единицу всякий раз, когда происходитскачок вверх у процесса (Xt), и (Dt) увеличивается на единицу всякийраз, когда (Xt) прыгает вниз.Тогда(2.8.19)(Bt) ∼ (Dt).что и доказывает соотношение (2.8.19).Ключевой момент состоит в том, что процессы (Bt) и (Dt) зависимы;в общем случае ни один из них не является даже процессом Маркова(хотя при i ≡ процесс (Bt) пуассоновский с параметром ( )).
Тем неменее, стационарное распределение задает тонкую связь между этимипроцессами, благодаря чему их распределения совпадают.Замечание 2.8.11. Теорема 2.8.10 важна в теории очередей. Там скачок(Bt) интерпретируется как прибытие нового требования (или клиента, посетителя) в марковской очереди, в то время как скачок (D t) означает уходклиента или покупателя или окончание выполнения требования. В этомслучае Xt задает длину очереди в момент t, т. e. число клиентов в системе(включая тех, кого обслуживают в данный момент).
В таком контекстетеорема 2.8.10 гласит, что процесс прибытий в очередь стохастическиэквивалентен процессу уходов; см. § 2.9.§ 2.9. Применения к теории очередей.Марковские очередиA Room with a Queue11(Из серии «Фильмы, которые не вышли на большой экран».)Рис. 2.61Это довольно неожиданно, так как процесс (B t) связан с параметрамиа процесс (Dt) — с i , а эти параметры могут быть совершенно различны.Д о к а з а т е л ь с т в о. Мы знаем, что процесс (Xt) обратим, т. e.(Xt) ∼ (Xtrev), где (Xtrev) — исходный процесс (Xt), наблюдаемый в обратномвремени.
Однако когда мы наблюдаем процесс в обратном времени, тоскачки вверх становятся скачками вниз. Иными словами,i,rev(Bt) ∼ (Drevt ), вклад процесса гибели в (Xt ),В этой главе мы остановимся на нескольких популярных моделяхмарковских очередей. Все эти модели, кроме одной, будут «истинными»процессами рождения и гибели с пространством состояний I, которое мыполагаем множеством неотрицательных целых чисел Z + = {0, 1, .
. .}, и независящими от i интенсивностями скачков вправо: q ii+1 ≡ (где qii+1 —элемент Q-матрицы, отвечающий за скачки вправо), в то время как q ii−1(элемент Q-матрицы, отвечающий за скачки влево) будет зависеть от i.Исключение составляет такая модификация предыдущих моделей, длякоторой пространство состояний конечно {0, 1, . . . , c}, где c — некотороеположительное число (что упрощает предыдущие модели).
Следовательно, qii+1 = для i = 0, 1, . . . , c − 1, однако qcc+1 и элементы матрицы Q,11 Ср.с названием фильма «A Room with a View».Глава 2. Цепи Маркова с непрерывным временемотвечающие за последующие скачки вправо, равны нулю (усложнениепредыдущих моделей). Можно сказать, что первые модели — с бесконечным буфером, в то время как последняя — с конечным.Для начала рассмотрим модели с бесконечным буфером; ср.
с рис. 2.43.§ 2.9. Применения к теории очередей. Марковские очередиМы видим, что процесс Q(t) совершает скачок вверх, когда прибываетновый клиент, и вниз, когда клиент уходит. Тогда (Q(t)) — это процессрождения и гибели с Q-матрицей−(2.9.1)Здесь A(t) ∼ Po( t) — число клиентов, прибывших на момент t, и D(t) —число клиентов, обслуженных на момент t.0(2.9.2)Модель б) соответствует так называемым M/M/∞-очередям (марковское прибытие, марковское обслуживание, бесконечно много серверов).Как и ранее, покупатели прибывают согласно процессу (A(t)) ∼ ПП ( ),но по прибытии каждому из них выделяют «личный» сервер, которыйприступает к обслуживанию моментально.
Как и ранее, времена обслуживания являются н.о.р.с.в. Exp( ). Процесс (Q(t)) — это опять-таки процессрождения и гибели. Однако в этом случае, если имеется i покупателейс оставшимися временами обслуживания S (1) , . . . , S (i) то скачок i → i − 1происходит с интенсивностью i , так как время до следующего скачка внизраспределено по законуmin [S (1) , . . . , S (i) ] ∼ Exp(i ).(2.9.3)Если за это время не придет ни один покупатель, мы заменяем интенсивность i на (i − 1) , иначе (т. e. если новый покупатель пришел до скачкаi → i − 1) мы заменяем i на i + 1 благодаря свойству отсутствия памятиу экспоненциального распределения.Соответствующая Q-матрица равнаQ(t) = A(t) − D(t), t > 0.0.... −( + )0 .
..Q=.. .−( + )0...... .........Рис. 2.62Как было сказано ранее, интенсивности скачков влево q ii−1 = i , i > 1,могут меняться; в качестве хорошо известных примеров приведем такие:а) i ≡ , постоянная интенсивность,б) i = i , интенсивность i пропорциональна i,в) i = min [i, r] , где и r — постоянные.Итак, предположим, что цепь стартует в момент времени 0 из состояния 0 (в большинстве случаев это не имеет значения).Модель a) соответствует так называемой M/M/1/∞-очереди: марковские прибытия, обслуживание марковского типа, один сервер, бесконечныйбуфер. Если не возникнет путаницы, последний символ ∞ часто опускаетсяи используется упрощенное обозначение M/M/1.В этой модели покупатели прибывают в очередь согласно процессу(A(t)) ∼ ПП ( ) и обслуживаются один за другим (представьте себе, например, парикмахерскую с бесконечным залом ожидания; парикмахерскаяоткрывается в момент времени 0, когда клиенты еще не пришли).
Временаобслуживания есть н.о.р.с.в. с распределением Exp( ). После обслуживания клиент уходит (и больше не появляется), а сервер сразу же начинаетобслуживать следующего клиента (если он есть) или стоит в бездействии,пока не придет следующий клиент. Порядок, в котором обслуживаютсяклиенты, обычно такой: кто первый пришел, тот и обслуживается первым;эквивалентное определение — первый пришел, первый ушел. Тем не менее,для многих задач (но не для всех) это не существенно.Нас интересует процесс (Q(t), t > 0) задающий длину (размер) очереди,т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
