1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1186154), страница 29
Текст из файла (страница 29)
2. В общем случае введенными выше характеристиками ПМП определен лишь для г(т' = Пп) г . Однако, если вложенная э ю цепь Маркова (т.) обладает эргоднческим распределением, то всегда тэ, а следовательно, процесс определен для всех т>0. 3. Воли расширить множество состояний процесса, а именно ввести переменную т(г) (т„, т„.„), где т =*т(г), т)аы — состояние процесса после следующего перехода, то в новых переменных Рз(х) будут зависеть только от (, но не от у. 2. Некоторые результаты из теории ценен жаркова. Возможность решения задач теории массового обслуживания методом вложенных цепей Маркова, вскрытая Кепдаллом, послужила стимулом к разработке ме~одов в теории цепей Маркова, отражаю щнх специфику данного прикладного направления.
В первую очередь теорию массового обслуживания интересуют эргодические теоремы, согласно которым можно делать выводы о существовании установившегося режима системы, не зависящего от начального ее состояния. Рассмотрим однородну)о цепь Маркова, состояния которой будем обозначать символами ~„т„..., т, ... Так, ч, будет считаться начальным состоянием, т — состоянием на и-м шаге илн в к-й момент времени. Множество состояний будем считать конечным нли счетным; обозначим это множество через Х. Пусть рс — вероятность перехода из состояния Г в состояние )) за один шаг, ри — вероятность подобного же перехода за я (а) шагов. (В частности, ря и рп обозначают одно и то же.) (т) 154 Гл.
3. НекотОРые клАссы случАйных ПРОцессов Нас интересует условие зргодичности цепи (у.), которое здесь будет пониматься в следующем смысле. При п™ь существуют пределы вероятностей перехода, не зависящие от начального состояния: (1) причем ~ яв = 1 (исключен случай так называемого ухода пронах цесса в бесконечность, если 1 понимать как числовой индекс).
Прежде чем дать условие зргодичности цепи Маркова, сфор мулируем два требования к цепям Маркова, существенные для выполнения данного условия. 1) Неприводимость: из любого состояния 1 возможен переход в любое другое состояние 1 (за какое-то число шагов). Более точно, для произвольных состояний 1 и у найдутся также состоя- ния 1„1О ..., 1„(где и может зависеть от 1 и у), что вероятности перехода за один шаг из 1 в 4, из й в 1„..., из 1, в 1„, наконец, нз 1„в 1 положительны. 2) Непсриодичность: наибольший общий делитель целых по- ложительных и, для которыхр„'.в>)О, равен 1 (для всех 1 и 1). Цепь Маркова со свойствами 1) и 2) называется неприводи.
мой непериодической цепью. Условия зргодичности неприводимых непериодических цепей выводились многими авторами в нескольких различных вариан- тах. Желающим подробно ознакомиться с этим вопросом реко- мендуем книги Феллера [31 (гл. 15), Сарымсакова [11, а также статью Фостера [11. Мы не будем здесь излагать общие аргоди- ческие теоремы, которые могли бы показаться трудными читате- лю-инженеру. Вместо этого мы сформулируем теорему, полезную для теории массового обслуживания. Пусть существует неотрицательная функция 1(1), 1ЫХ, со следующими свойствами: 1. Для некоторого е)О и всех 1жХ, за исключением, воз. можно, некоторого конечного множества, МО( +г)! ' = 1)(1(') — . (2) 2. М(/(У„+т)(У„= 1) ( со, 1ее Х.
(3) Те ар ем а. Если цепь Маркова (у ) — неприводимая неперио- дическая и удовлетворяет условиям (2) — (3), то зта цепь явля ется зрзодической Дока аательство приведено в работе Г. П. Климова [11, Укажем еще полезный признак зргор;ечности цепи Маркова (Твиди [11). Пусть (у ) — неприводимая непериодическая однородная цепь Маркова с состояниями О, 1, 2, ...; р';",Д = Р ( - = 1! з = 1); и(1) = М(У тв — ъ„! т = 1). З Зл. ИетОд кпндллчА.
полумлвковскик ПРОцзссы 135 Тогда для эргодичности Ц„) достаточно существования таких 1 и Я) О, что Пш ~ рй р(у)(О. йю г~я В практических задачах важно анать не только эргодическое распределение, но также и то, насколько быстро допредельное распределение сходится к предельному. Наиболыпий интерес представляет тот случай, когда можно получать экспоненциальные оценки вида ! Р()'> — л,!( МиЛй, где постоянные Хо меньше 1. Если выполнено условие (2), то говорят (термин Кендалла), что имеет место геометрическая эргодичность.
Выяснению условий геометрической эргодичности посвящена работа Кендалла [2]. Внр-Джоунз [11 доказал теорему о возможности равномерной оценки ~ ро~ — и; ~ МЦХ, О Л(1. Если для данного состояния 1 справедлива оценка ! р( ) — л4! ( МЦЛ~;, то это состояние называется геометрически эргодическим. Результат Вир-Джоунза формулируется следующим обрааом: Если все состояния неприводимой непериодической цепи Маркова являются геометрически эргодическими, то справедлива равномерная оценка при некотором Х ( 1.
В статье Вир-Джоунза [21 автор применяет свой реаультат к псследованию времени вхождения систем массового обслуживания в стационарный режим. Полезно также привести соответствующую теорему для случая, когда число возможных состояний цепи Маркова конечно. В отой ситуации геометрическую эргодичность состояний не нужно специально доказывать. Если цепь Маркова неприводимая непериодическая и если множество У ее состояний конечно, справедлива оценка (4) при некотором Х (1. Доказательство см.
в книге Феллера [3). Классическое неравенство С. Н, Бернштейна дает оценку значения )а если рн -з1 — Х, то ~ ~ рцз~ — и; ~ ~ (2Х". (4) э 3. Основные соотношения для полумарковских процессов. Обозначим через Ве(г) вероятность события (т(г)= ~) при уело вии ч(О)=г, через В,(г) — беаусловную вероятность этого же 156 гл. 3. некОтОРые классы случьнных ЦРОцессов события. По формуле полной вероятности В;(г) = ХРГ'Ва(г)* (5) где р1Ю= Р(то = 1).Таким образом, Во(Г)= В,(Г) при выборе паоо) чальных вероятностей в виде ро = би. Имеем стохастическое соотношение тм гг» )г, у (г) = .* (г — г,), г, ( г, где те(Г) — ПМП с теми же характеристиками, что и т(о), и на- чинающийся с состояния, в которое исходньш процесс переходит в момент ФО Перейдя от стохастического соотношения к вероят- ностям, получим уравнение Вп(г) = Р,(г)бп+ ~э~ ) Вм(г — х)йР;„(х), о~~О.
(6) "о Можно воспользоваться методом преобразований Лапласа, введя функции В;. (е) = ~ е НВ;; (Г) Ю о лп (е) = ~ е "е(Р6 (Г)о о ФЭ л; (е) = ~ч~лп (е) = ~ е '~йРо(Г). з о (8) (О) (Первая из них имеет смысл при Кез)0, остальные — пре Кее ) 0.) Перейдя в (6) к преобрааованиям Лапласа, получим Вм(е) = — [1 — л, (е)) 66 + ~~)~~ Вй (о) лы (е) (10) При фиксированном е соотношения (10) представляют собой систему линейных алгебраических уравнений. Предположим, что г — положительная величина; устремим ее к бесконечности. Тогда при всех 1, 1, очевидно, ло(о) будет стремиться к нулю. Вследствие этого определитель системы (10) будет стремиться к 1. Поскольку этот определитель, как легко видеть, при Кое) 0 является аналитической функцией, он может обращаться в нуль лишь в отдельных точках (иначе он равнялся бы нулю тождественно, что, как мы убедились, не может иметь места).
Это говорит о том, что при конечном числе состояний процесса система (10) обладает единственным решением. 6 1,1. метод кендАллА. Полга1АРковскпе ПРОцессы 157 Внимательный читатель мог заметить некоторый пробел в нашем рассуждении. В самом деле, все изложенное справедливо лишь в том случае, когда за конечное время с вероятностью 1 происходит конечное число восстановлений. В противном случае нельзя говорить о значении процесса Р(1) в момент д так как он может быть неопределенным. сутоб1А исключить возможность подобной ситуации, достаточно потребовать, чтобы нашлось такое положительное е, что при любом у справедливо неравенство Го(е) < 1 — е.
1)Ну(1) = ~~.",р1~~11Р11(у) + ~ ) 1уНд(8 — х) ЙР„у(х), г) О. (11) 1 "о К уравнениям (11) можно применить метод преобразования Лап- Ю ласа — Стилтьеса. Обозначив Уоу(г) =у е "еУН; (У), найдем о Уоу(г) = ~.", р1о)я„(г) + ~11о (г) пм(г), Пег ~0, (12) Теперь можно возвратиться к поставленной задаче. Событие (ч(1) у) может произойти двумя способами: либо ч(0)=у и 11) ) Г, либо в некоторый момент х с г произошел переход в состояние у и после этого в течение времени 1 — х переходов не было.
Отсюда Ву(г) = р<"Ру(г) + ) Ру(1 — х) ИН; (х), о Следовательно, гВ,' (г) = р(ю (1 — яу (г)) + [1 — и; (г)) йу (г). (14) (13) В практических задачах это неравенство всегда выполняется. Предлагаем читателю вспомнить по этому поводу теорему Феллера, приведенную в главе о входящих потоках. Уравнения (10) являются обратными уравнениями ПМП, или, по терминологии Феллера [31, уравнениями, обращенными в прошлое. Займемся теперь составлением прямых уравнений. Обозначим через Н1(1) среднее число переходов процесса ч(1) в интервале (О, г), после каждого из которых процесс попадает в состояние у. Множество моментов подобных переходов образует процесс восстановления; таким образом, Н,(1) — функция восстановления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
