3. Основы теории случайных процессов. Карлин (1971) (3. Основы теории случайных процессов. Карлин (1971).djvu), страница 15
Описание файла
DJVU-файл из архива "3. Основы теории случайных процессов. Карлин (1971).djvu", который расположен в категории "". Всё это находится в предмете "теория массового обслуживания (асвк)" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 15 - страница
Из предыдущего неравенства получаем .вл Рссус еы ус ПУсть задано е > О. Мы можем выбРать такое М(е), что (,сУс (е для с )~ М(о). Далее, имеем М-1 ~2~~ Р у + ~2з~ Р"у (у с-о сс с с-м откуда ~ РссУс+со(п (У,) 2", Р„(У„ с-о т> ' с-м и поскольку то М-1 С М-1 В е'„т~, ,кь ' Ст С (' - В "") ~ т Как было отмечено в доказательстве предыдущей теоремы, )(си Р"„=О при ! выл. н-ь Переходя к пределу при лс- оо, получаем для каждого фиксированного с йс(Со)уо+ со(п(У)(! — йс(Со)) (Ус т>М или ! ! — тсс(Со) ( щ,.о(„! (ус — йс(Со) уо) ~<оК т>м где А' =- Ус — й с (Со) У .
5 Д Приллер из теории оиереаей 91 й 5. ПРИМЕР ИЗ ТЕОРИИ ОЧЕРЕДЕИ Рассмотрим модель процесса обслуживания из гл. 2 (пример В) Матрица переходных вероятностей соответствующей марковской цепи имеет вид а,г а1 аг аз аг а, 1а, а, 0 ао 0 0 где аи>0 и ~по=1, и-о 11 Р ц 11 = а, аг ао а, (На самом деле при дальнейшем анализе нам потребуются только два условия: 0 < а, < 1 и а, + а, < 1, обеспечиваюшие неприводимость марковской цепи.) Мы покажем, что если ~~Р„йаи>1, то и-о система уравнений ~~ Рцуг —— уц 1Ф О, имеет ограниченное рег-о шение, отличнос от константы, что, согласно теореме 4.1, означает невозвратность процесса. Положим у; = 9', тогда упомянутая система уравнений принимает вид Х Рггв' = Х аг 1-о / г †! нли а; гл.Д ' =9= ~г аД" =1(1), Так как 1'(0)=а,>0 и 1(1)= ~ аи — — 1, то из условия 1 (1) = и=о = ~ йаи > 1 следует, что сушествует точка $о, 0<9о< 1, такая, и=о что 1(йо) = йо.
Это легко видеть на рис. 1. Вектор уг — — Я, 1 = О, 1, „ и представляет собой искомое ограниченное решение, оче- видно, не являюшееся постоянным, Пусть теперь ~с~ йао < 1. Тогда, полагая уг — — /, имеем ~~~~ Рц) = ~2~ а1 ьы1'= ~~."~ аг гл ~(1 — ю'+1) +1 — 1 = 1=о 1-г-~ 1=г-1 = ~г йао — 1+1<1 (1 ~ 0). и-о Поскольку е произвольно, а й,(С,) =1, то йй(Со)= 1 для каждого 1', что и означает возвратность исходной марковской цепи. 92 Гл. Д Осноеные предельные теоремы длп л~аркоескнх цепей Таким образом, в силу теоремы 4.2 процесс является возвратным, если ~~'., Ьаь ~~ 1. Прежде чем обратиться к вопросу о том, является ли процесс )р возвратным нулевым или возвратным положительным, рассмотрим следующую вспомогательную задачу, представляющую самостоятельный интерес. ле Рнс.
1. Пусть Х), Х,, Х,,... — последовательность независимых, одинаково распределенных случайных величин, принимающих значения — 1, О, 1, 2,... с вероятностями Р(Х =й)=Ьм й= 1 0 1 2 ° ° Ь )>О и пусть 5„= Х) + Х, +... + Х„. Определим Х как значение параметра и, для которого Я„впервые становится отрицательным, и пусть Р(Л=Ь)=уь Ь=1 2, 3, .-.. (5.1) Пусть У (з) = Х уьз' (уе - О) (5.2) е-е есть производящая функция распределения (5.1). Пусть Т~~' есть случайная величина, равная первому значению параметра и, для которого Т„< О, где л „- т+ Я„(» — неотрицательное целое (г) лг) число), Поскольку каждая из с. в.
Х; > — 1, нетрудно убедиться В том, что Ю") = Х) + Лх+ . + Е,+), где с, в. Х1 — независимые и 93 Э Б. Пример из теории очередей одинаково распределенные в соответствии с (5.1), Производящая функция с. в, Х<"~, очевидно, равна [У (з)]'+1. Пусть у"~~ есть коэффициент при 5'" в разложении функции (и(з)]'+. Наконец, положим 6 (з) =- ='+ Ь, + Ь, и + Ьезе + Наша цель — выразить У(з) через 6(з).
Для этого запишем сле- дующие соотношения типа уравнений восстановления: (5.3) г=о Первое из этих соотношений очевидно. Что касается второго, то событие (5„> О, и = 1, ..., Й вЂ” 1; Я„= — Ц представляет собой объединение следующих несовместных событий: (Х, = /; Х, + +...+Х„+у>0, н=-2, ..., й — 1; Хе+...+Хи+/=- 1], 1 = О, 1, .... Так как с. в. Х, независимы и одинаково распределены, вероятности этих событий, как легко видеть, равны Ь|у'+,". Формула полных вероятностей дает (5.3). Переходя к производящим функциям, с помощью (5.3) получаем и(з)=Ь, +2 (ЯЬ,.ун+, =е',г-о I =ь,.+, ~ь,~,рун.п; — = о-е = Ь 1з+ з,'„Ь, (и ( )]и ы = !-о = Ь,з + зУ (з) ~ 6 (У (з) ) — ~ = зУ (з) 6 (У (з) ), 0 < з < 1.
Далее, и(з) непрерывна и строго возрастает при з ~ 10, 1], причем У(0) = О. Следовательно, У(з) удовлетворяет уравнению 6(У(з)) = 1/з при 0 < з < 1. Но 6" (з) = =,'— +2Ь,+бьез+12Ь,з'+ ... >0 при з) О, так что функция 6(з) является выпуклой; к тому же, по определению 6(з), 1пп 6(з)=+ и и 6(1)=1. Из рис. 2 легко заклюечо чнть, что уравнение 6(х) = 1/з может иметь самое большее два положительных решения при каждом фиксированном аы]0, 1]. Ге. 3, Основные лределвные теоремы для марковских целей 94 Поскольку !!гп У (з) = О и У(з) строго возрастает на интервале еФо (О, !), то У(з) должно быть меньшим из двух решений уравнения 6(х) = !/з, если таковых два.
Исследуем теперь условия, при которых ~ ун = 1 или < !. «-о Возникают следующие две возможности: и(,) ве Рис. 2. Случай 1. 6'(1) > О. Условие 6'(1) > О эквивалентно тому, что Ь 1< ~ лЬ„. Из Рис. 2 видно, что У(1)= ~ Уе— - ко< !. Следова- л о е-о тельно, вероятность события (5„ > О при всех и) строго положительна. Случай 2. 6'(!) < О. Условие 6'(!) < О эквивалентно тому, что Ь, ~~ ~ лЬ„, и в этом случае мы имеем ~ уе = У (!) = 1. Далее, в-о н-о 6'(У(з)) У'(з) = — !/зе при О < з <1, так что в рассматриваемом случае У(з)-+1 при з-+1 (рис. 3).
Отсюда следует, что если б'(!) < О, т. е. если Ь >Хльсн о о то М (Я) = )~~ лу„= У'(1) =, < оо, л о 95 З Б. Пример из теории огередей а если с1'(1) = О, т. е. Ь,= Хпб. и О то Возвращаясь к процессу обслуживания, поставим в соответствие распределению (Ье) распределение (ае) количества посту- Сге1 Рис. 3. пающих заявок за период следующим образом: а„= Ьи г.
Определим Егг как число переходов (время), требующееся для того, чтобы впервые попасть в состояние 1 < г из состояния 1. Нетрудно видеть, что Яг, г. г есть в точности с. в, Е, производящую функцию У(з) которой мы только что рассматривали. Так как ~г а,=1, г-о то мы имеем Ь г> ~ пЬ„е-г ае) ~ ггаи — +-э 1> ~ч'„оа„ 96 Гл. 3, Основнь!е предельные теоремь! длв марковских цепей и, аналогично, 9 ! = Х пд„~ ао = ..,'.", па„.ь! ! = ~! па„. Следовательно, М(Уь ! !) = !к< о, если ~ па„<1, и М(У! ! !) и О = р= оо, если ~ па„= 1. Ясно, что У~ ! Уь,,+Е,, ! ~+ ...
+У!~ьп 1<!', и поэтому М(е.с,;) = (! — 1)р; в частности, М(А, О) = ь1х Рассмотрим теперь среднее время возвращения в состояние О. Отметим прежде всего, что вероятность времени возвращения быть равным 1 есть просто ао, т. е. вероятность перехода РО,. Далее, траектории, которые выходят из состояния 0 и возвращаются в это состояние впервые за два или более переходов, могут быть разбиты на группы в зависимости от состояния ь, занимаемого после первого перехода. Такое разложение в совокупности с марковским свойством процесса позволяет получить для среднего времени возвращения следующее выражение: ~2'.~ 4" = М (время возвращения) = в-О = а, + 2', а, !Е (х, ь, О) + 1] = 1 + ~ а, Е (Ль, О) = ! ! с-! ) ь = 1+,ь! ьра, =- 1+ р .~~!ар ! ! с-О Таким образом, ~ П1О" < оо, ЕСЛИ р< оо, н т.
е. при условии Х !ос<1, с-о ~ п)" = оо, если (ь= оо, л О нли, что то же, если ~с~~ !'а! = 1 ° с-О й 6. Еече один иртоиер из теории онередеа 91 Резюмируя полученные результаты, имеем ~~и па„( 1 =)т возвратный положительный, л о ~~.", па„= 1 Ф возвратный нулевой л-о (5.4) ;У,' па„>! ~ невозвратный. л=о ф 6. ЕШЕ ОДИН ПРИМЕР ИЗ ТЕОРИИ ОЧЕРЕДЕЙ Состоянием процесса, как и ранее, является длина очереди; за каждую единицу времени прибывает одна заявка, а обслуживается й заявок в соответствии с распределением 1аи > О, й = = О, 1, 2, ...), если в очереди столько заявок окажется, Матрица переходных вероятностей, как нетрудно убедиться, в этом случае имеет вид ~ а, ао О О е а, а, О !!РН!1= ~ ат ю а, а, ао 4 зал озо Эти результаты представляются довольно естественными.
Выражение ~ аал есть среднее число требований, прибывающих за л о один период обслуживания. Тогда если ~ пал > 1, то в среднем л о больше заявок поступает, чем обслуживается за каждый период. Следовательно, можно ожидать, что очередь будет расти беспредельно. С другой стороны, если ~~'., па„< 1, то процесс стремится л о к некоторому стационарному состоянию.
Нахождение стационарного распределения связано со значительными трудностями (см. гл. 14). йй Гл. 3. Основные предельные теоремьс длл марковских Чепей Мы покажем, что если ~ йаь>1, то существует стационарное ь-о распределение, так что в этом случае процесс возвратный положительный. Так как ~2~ йаь есть среднее число обслуживаемых за период заявок, тогда как за это же время поступает только одна заявка, то существование стационарного распределения при указанном условии не является неожиданным. РассмотРим УРавнениЯ ~ елРсс — — ~с и положим ~с = $1.