Цепи Маркова (1121219), страница 58
Текст из файла (страница 58)
С другой стороны, если выполняются неравенства (2.10.39) (т. е. оба неравенства (2.10.42) нарушаются), то цепь (N(t))не может быть положительно возвратной. Остается вопрос: что происходитв случаях б) и в)?Анализ этих случаев зависит от того, как векторы E внутр и Eверт направлены по отношению друг к другу (и не зависит от их величины). А именно,в случае б) если вектор Eверт смотрит в сторону от вектора Eвнутр (илиEверт и Eвнутр параллельны), то ц.м.н.в. (N(t)) не может быть положительновозвратной.
Наоборот, если вектор Eверт направлен на Eвнутр , то цепь (N(t))2 (1 − p12 p21).(2.10.46)368Глава 2. Цепи Маркова с непрерывным временемТретье из неравенств (2.10.46) — это в точности второе из неравенств(2.10.35). При помощи тех же рассуждений получаем, что система (2.10.46)приводит к системе, где первое неравенство заменяется на первое из неравенств (2.10.35). Затем опустим второе из неравенств (2.10.46). В конечномсчете из системы (2.10.46) следует выполнение системы (2.10.35), т. е.положительная возвратность.Случай в) рассматривается аналогично; см.
рис. 2.78. Левая часть рис.2.78 соответствует неравенствамвнутр гор> 0, Eвнутр< 0 и − EвнутрEгорE2 > 0,Eвнутр1221 + E1(2.10.47)где последнее неравенство означает, что скалярноепроизведение−Eвнутрвнутр ⊥внутр ⊥внутрверт2hE −, E i положительно, E−=(= −E+ ⊥) означаетвнутрE1вектор, полученный поворотом против часовой стрелки вектора E внутр наугол /2 (поворот против часовой стрелки, так как вертикальная осьпри таком повороте становится направленной внутрь положительногоквадранта). Правая часть рис. 2.77 соответствует неравенствамвнутрE1горвнутр гор> 0, Eвнутр< 0 и − EвнутрE1 + E1 E2 < 0.22(2.10.48)§ 2.10. Ветвящиеся процессы с непрерывным временем369системе (2.10.45) (см. правую часть рис. 2.77) или в) векторы Eвнутри Eгор удовлетворяют системе (2.10.47) (см.
правую часть рис. 2.78).Мораль, которую можно извлечь из этого анализа, состоит в том,что положительную возвратность можно установить исходя из картинывекторных полей, порождаемых средними скачков. Отсутствие свойстваположительной возвратности у цепи в случаях б) и в) можно объяснитьпосредством следующих рассуждений «на физическом уровне»: когда мырассматриваем поведение процесса (N(t)) в «крупных масштабах» времении пространства, то главенствующая тенденция для путей /траекторий — эточеткое следование направлению векторного поля.
Левые части рис. 2.77и 2.78 оставляют возможность для путей/траекторий уйти на бесконечность, придерживаясь линии, которая остается вблизи соответствующихчастей границы Z2+ , как показано на рис. 2.79.Теория, лежащая в основании изучения цепей Маркова и других классов случайных процессов в больших масштабах времени и пространства,называется анализом предельных потоков. Некоторые аспекты этогоанализа представлены в следующем параграфе в связи с теорией большихуклонений.Рис.
2.79Рис. 2.780 p12p21 0и интенсивностями обслуживания1,ции P =Подведем итог.Теорема 2.10.13. Для открытой сети Джексона с двумя узлами,интенсивностями входных потоков 1 , 2 , матрицей маршрутиза2процесс(N(t)) является положительно возвратным тогда и только тогда, когда для векторов Eвнутр , Eверт и Eгор , заданных формулами(2.10.36) – (2.10.38), выполняется одна из следующих трех взаимно исключающих возможностей: а) вектор Eвнутр удовлетворяет системе (2.10.42) (см.
рис. 2.76), б) векторы Eвнутр и Eверт удовлетворяютИсследования такого рода можно распространить на общие цепи Маркова на Z2+ , и это приводит к мощной теории (см. Fayolle G. , Malyshev V. A. , Menshikov M. V. Topics in the Constructive Theory of Countable Markov Chains. Cambridge: Cambridge University Press, 1995). Специфический характер сетей Джексона подчеркивается тем фактом, чтов случае а) (см. неравенства (2.10.42) и рис.
2.75) векторы E гор и Eвертавтоматически нацеливаются на вектор Eвнутр , блокируя возможности ухода траектории и обеспечивая тем самым положительную возвратность.Это происходит в результате того, что векторы E гор и Eверт получены изEвнутр путем «усечения», когда подавляются скачки, не позволительныев силу геометрии квадранта Z2+ . Нетрудно привести пример «естественных» ц.м.н.в. на Z2+ , когда векторы Eгор и Eверт не могут быть получены при370Глава 2. Цепи Маркова с непрерывным временем0= .6 , P0 = P и0помощи этой процедуры. Анализ таких цепей становится намного сложнее.В завершение этого параграфа прокомментируем еще одно интересноеи полезное свойство процессов (N(t)), возникающих в сетях Джексона:монотонность.
Это научит нас полезной технике спаривания случайныхпроцессов.Пример 2.10.14. Рассмотрим два открытых процесса миграций с одним и тем же множеством станций (узлов) 1, . . ., J и параметрами ( , P, )0и ( , P0 , 0) соответственно. Предположим, чтоЗдесь и ниже неравенства для векторов понимаются покомпонентно. Рассмотрим соответствующие процессы миграций (N(t)) и (N 0 (t)), где N(t) = 0 N1 (t)N1 (t).0= .. и N (t) = ... .
Предположим, что (N(t)) и (N 0 (t)) стартуютNJ (t)NJ0 (t)из одного и того же самого начального состояния n0 ∈ ZJ+ . Тогда процесс(N(t)) остается стохастически бо́льшим, чем (N0 (t)) (или (N0 (t)) стохастически меньше, чем (N(t))), т. е. эти процессы можно запустить совместнотаким образом, что с вероятностью 1 выполняется неравенство0N (t) 6 N(t) ∀ j = 1, . . . , J и t > 0.(2.10.49)Попросту говоря, размер очереди в процессе (N(t)) все время остаетсябо́льшим, чем размер очереди в процессе (N 0 (t)) на каждой станции j.
См.рис. 2.80.§ 2.10. Ветвящиеся процессы с непрерывным временем371и ПП ( j − 0j). Заявки, относящиеся к процессу ПП ( 0j), «пометим» красным, а заявки, относящиеся к ПП ( j − 0j), — белым. Приоритет состоитв том, что красные заявки замечают наличие только других красных заявок,т. е. белые заявки могут быть обслужены только тогда, когда в очереди нет красных, и если красная заявка прибывает на данную станциюв тот момент, когда обслуживается белая, то обслуживание сразу жепереключается на красную. Обслуживание белых заявок возобновляется,когда в очереди не остается красных.
Заявки обоих цветов подчиняютсяодинаковым правилам циркулирования и ухода, которые предписываютсяматрицей P.Пусть Njкр (t) и Njбел (t) — числа красных и белых заявок на станции кр N1 (t)j в момент времени t; образуем векторы N (t) = ... и Nбел (t) =NJкр (t) бел N1 (t) .. = . . Ясно, что введенная выше модификация не меняет распредеNJбел (t)крления общего процесса (N(t)):(N(t)) ∼ (Nкр (t) + Nбел (t)).Более того, красная часть процесса (N(t) стохастически совпадаетс (N0 (t)):(N0 (t)) ∼ (Nкр (t)).Поскольку Nкр (t) + Nбел (t) > Nкр (t), получаем неравенство (2.10.49).Сети Джексона обладают множеством различных свойств монотонности (см. Shaked M. , Shanthikumar J.
G. Stochastic Orders and theirApplications. Boston MA: Academic Press, 1994; Müller A. , Stoyan D.Comparison Methods for Stochastic Models and Risks. Chichester: Wiley,2002). Многие из этих свойств возникают при детальном анализе моделейочередей с одним сервером. Также существуют интересные неравенства,связывающие открытую сеть Джексона и совокупность J изолированныхM/M/1-очередей17 .Рис. 2.80§ 2.11. Большие уклонения для цепей МарковаРешение. Чтобы построить спаренный процесс, запускаем совместнодве сети Джексона, рассматривая сеть с параметрами ( , P, ) и введяприоритеты.
Более точно, представляем пуассоновский входной поток ПП ( j) в виде суммы независимых процессов Пуассона ПП ( 0j)17 См. Massey W. A. An operator-analytic approach to the Jackson network// J. Appl. Probab.1984. V. 21. P. 379–393; Open networks of queues: their algebraic structure and estimating theirtransient behavior // Adv. in Appl. Probab.
1984. V. 16. P. 176–201.372Глава 2. Цепи Маркова с непрерывным временем373достигла высокого уровня больше vnT в момент nT). Можно записатьсоотношение (2.11.3) в виде P (vt − ε < Qtn /n < vt + ε, 0 < t < T) ≈ e−T (v) .с непрерывным временем§ 2.11. Большие уклонения для цепей Маркова с непрерывным временемo1vt − ε < Qtn < vt + ε, 0 < t < T .(2.11.1)nР. Браунинг (1812–1889), английский поэтv − R( ), где R( ) = (e − 1) + (e− − 1),(2.11.4)Поучительно получить уравнение (2.11.3) исходя из «первых принципов».
Для этого при заданном v > 0 максимизируем по > 0 следующеевыражение:иными словами, вычисляем преобразование Лежандра функции R( ). Прямым дифференцированием получаем значение ∗ , доставляющее максимум,как решение уравнения(2.11.5)v = R0 ( ∗),т. е.nДля него золотым был прямой путь.В этом параграфе будет разработана методология больших уклонений для цепей Маркова с непрерывным временем, возникающих в теорииочередей, поскольку это приводит к важным практическим приложениям.Существует и более общая теория, охватывающая формально более широкий класс ц.м.н.в.; см., например, [DZ] , однако она требует техническисложных условий.Мы сосредоточим внимание на так называемой картине выборочныхтраекторий, когда интерес представляет процесс длины очереди с измененным масштабом (Qtn n).
Основной результат получается следующимобразом. Зафиксируем временной горизонт T > 0 и скорость роста длиныочереди (в измененном масштабе) v > 0. Предположим, что = / < 1и Q0 = 0, и рассмотрим событие∗= ln v + pv2 + 42> 0.(2.11.6)Максимальное значение (2.11.4) совпадает с (v).Более тонкий анализ дается следующими рассуждениями. Пусть насинтересует событие, состоящее в том, что длина очереди когда-либо достигнет высокого уровня na:Рис. 2.81{sup [Qs : s > 0] > na}.Оказывается, для любого ε > 0 вероятность этого события стремитсяк 0 при n → ∞ с экспоненциальной скоростью. Точнее,Представляет интерес анализ логарифмической асимптотики вероятностиэтого события по аналогии с соотношением (2.11.2). Здесь результат выглядит следующим образом:+ + −v2 + 4(2.11.3)Тот факт, что выражение из формулы (2.11.3) положительно, следует издвух простых заключений: 1) (0) > 0 (эта величина неотрицательна длявсех и и равна нулю, когда = ), 2) 0 (v) > 0 при v > 0 (здесь условие< является существенным).Смысл события (2.11.1) вполне прозрачен: на большом временн о́м интервале [0, nT] длина очереди возрастала почти линейно (и, в частности,hi1ln P (sup [Qs : s > 0] > na) = − ∗ (a),n→∞ nlimгде∗(a) = a ln .> 0.(2.11.2)(2.11.8)(2.11.9)Однако этот факт говорит нам о большем, чем просто специфика асимптотики, поскольку позволяет указать траекторию процесса длины очередис измененным масштабом, вдоль которой достигается уровень a.
Болееточно, выберем(2.11.10)v∗ = −q= −T (v), v + pv2 + 4(v) = v ln2гдеih 11ln P vt − ε < Qtn < vt + ε, 0 < t < Tnn→∞ nlim(2.11.7)Глава 2. Цепи Маркова с непрерывным временеми рассмотрим подмножество события (2.11.7):no1av∗ t − ε < Qtn < v∗ t + ε, 0 < t < ∗ , sup [Qs : s > 0] > na .n(2.11.11)vПо сути, в сравнении с событием (2.11.7), в событии (2.11.11) мы ввели дополнительные ограничения на траекторию процесса длины очереди.Однако вероятности обоих событий демонстрируют одинаковую логарифмическую асимптотику:h 11alim ln P v∗ t − ε < Qtn < v∗ t + ε, 0 < t < ∗ ,nvn→∞ nisup [Qs : s > 0] > na = − ∗ (a), (2.11.12)где функция ∗ (a) определена в формуле (2.11.9).В терминах большихуклонений это интерпретируется так: асимптотически процесс (Qtn n) достигает уровня a вдоль прямой v∗ t, 0 < t < a/v∗ .§ 2.11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
