1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1186154), страница 47
Текст из файла (страница 47)
Фориулы (7) сохраняют смысл и в том случае, когда (ц„), (з ) — зависимые последовательности случайных величин. Важна лишь независимость в совокупности случайных величин (Ь„). Дадим, следуя Линдли, две интерпретации полученных рекуррентных формул. Первая интерпретация — случайное блуждание с задерживающим экраном. Представим себе блуждующую частицу, координата которой в момент п равна х .
В начальный момент л = 1 х, = О. В каждый последующий момент и к координате частицы добавляется ь„, где Ь„не зависит от ~о ~м..., ~„, и имеет распределение К(х). Если на каком-либо шаге частица уходит в область отрицательных значений координаты, она немедленно возвращается в нуль. Тогда распределение координаты частицы в момент п совпадает с распределением длительности ожидания и-го требования. Зтот факт непосредственно очевиден ввиду соотношения (5), представляющего фориальную запись закона блуждания с задерживающим экраном. Вторая интерпретация, также приводящая к распределению длительности ожидания,— случайное блуждание с поглощающим экраном.
Снова рассматривается блуждающая частица с координатой х„на п-и пгаге; х, = О. Имеем х„= х„, + ~, л > 2. Ставится поглощающий экран на уровне х. Если в какой-либо момент времени х„Р-"х, частица поглощается. 5 5.Ь СИСТЕМА О1~6~1 249 Утверждается, что вероятность непоглощения частицы за п шагов совпадает с Р (х) = Р(иы( х).
Другими словами, для неограниченного блуждания х.=х„-1+~, в~2, х,=О, Р (и1„( х) = Р ( шак хз с х) „ 1~1~;.а т. е, ш„можно интерпретировать как шах хо Доказательство 1~Ыв этого утверждения осуществляется по индукции. При п = 1 оио выполнено тривиальным образом, При и ~ 1 имеем шах(0, х ), если шах (х1 — х,) (О, шал (О, х ) + шах [О, (хз — х1))> а<ма если шах (х, — х,) ) О. з~мп (9) шах хз = 1азав Ь„1(х — у) НК (р), х ) 01 О, х~ О. От~ формулы зквивалентньт формулам (7), но, поскольку последние однозначно определяют Р„(х), имеем совпадение Л„(х) = = Р„(х) при любом п ~ 1.
2. Интегральное уравнев(ие. Существование предельного распределения. Только что был установлен факт, эквивалентный ра- венству (10) Р„(х) = Р ( 1пах х1 ( х); отсюда следует, что при любом п ) 2 Р. (х) < Р„, (х); стало быть, существует Р (х) = 11ш Р (х) в смысле слабой слодпмости. Функцию Р(х) можно доопределить по непрерывности слева. По теореме Лебега о возможности перехода к пределу под знаком интеграла мы можем в (7) Е!о распределение шах (х; — х,) совпадает с распределением слуЗазав чайной величины шах х1 (ввиду однородности блуждания). 1<1~и-1 ОбозначямЬ„(х)=Р(шак хз ~х).
Тогда из (9) выводим следу- 1 1ощне формулы: гл. е пги51енеиие БОлее ОБщих методОБ 250 х Р(к у) дй.(у),,~0 О, к(0. (12) Уравнение (12) представляет собой интегральное уравнение на полуоси с ядром, зависящим от разности аргументов. Общая теория подобных уравнений развита в известной статье М. Г. Крейна (1). Решение находится посредством факторизации преобразования Фурье ядра интегрального уравнения.
Является ли Р(х) функцией распределения, зависит от значения Р( о)=11шр(х). х-» Теорема. Пусть существует математическое ожидание 55 = 1ч)ьх конечное или бесконечное, но определенного знака. Тогда; 1) при а(0 Р(») 1, 2) при а > 0 Р( ) = О, 3) при 55=0 Р( )=О, ва исключением случая, когда Ь„=О с вероятностью 1. Дока з а т ель ств о. Можно записать Р(х) = Р ( шах х1(х), (13) 11х1л куда включается и случай шах х; = сс. 1лгх-. Рассмотрим первый случай: а ( О.
Согласно усиленному закону больших чисел положительными могут оказаться лишь конечное число ао откуда следует конечность максимума с вероятностью 1. Во втором случае ответ также дается усиленным законом больших чисел: хх — Ос с вероятностью 1, так что тем более х-~ ~ю шах х1 = со и Р(х) = О при любом х. 1лгкю Займемся третьим, наиболее трудным случаем. Возможны две альтернативы: Р(+ 0)= О и Р(+ О)) О. Если Р(+ 0)= О, то из уравнения (12) получаем ) Р( — у)дК(у)= — ) Р(у)дК( — у) =О. (14) Здесь, в свою очередь, имеются две возможности: ~. = 0 с вероятностью 1 ИР(~ ФО):~0.
В первом случае все 5с„ совпадают. устремить и к бесконечности, что приведет к интегральному уравнению 3 за. системА ог» о» 1 251 Во втором случае, учитывая, что Мь~ = О, найдем такое з > О, О »»о ~ »»К (у) О. Но тогда из равенства (14) следует, что зе Е(у) = О при у < е. Подставив в уравнение (12) х = е' ( з, по- лучим, что г'(у)= О при у (з+ е; последовательно применяя зот же прием, приходим к выводу, что г" (у)— = О. Пусть теперь Е(0) = б ) О н и'., = и';, =...
=и»»„=... = О, а промежуточные и», положительны. Тогда разности», — »„», — »„... — независимые, оди»»азово распределенные случайные величины. Из теории це- пей Маркова получаем, что г(+ 0)= б ) 0 может быть лишь в зом случае, когда М (»в — »„-Д( со. Усиленный закон больших чисел приводит к выводу: осли лз„— число равных нулю»пм 1 -= - У~ и, то т„/в — б. Обозначии через ф„время между Г»„, и»;„, когда прибор свободен. Все $„одинаково распределены и (прп ь Ф 0) с положительной вероятностью положительны.
Сле- довательно, ~$»)св, с)0 п)в (15) Однако»п„= и, + ~ с» + ~ $». Согласно усиленному закону больших чисел ~ ~» = о (и), п -~- оо; »» в в сочетании с оценкой (15) это дает С и ) — и, л' вы откуда г"(х)= О для любого х. Теорема полностью доказана. Установим теперь эргодичность предельного распределения: при любом у г'„(х ( у) = Р (и»„( х ( и, = у) — г" (х).
Обозначим и»„(у) решение рекуррентной системы уравнений »а. (У) = (и» вЂ”, (у)+ ь )+ при начальном условии и», (у) = у. Тогда, так как функция хь монотонно не убывает по х, имеем »п„(у) ~ и»„(з), у ~ з. (15) Предположим, что а (О. Пусть („— свободное время прибоРа в»штервале (О, »„). Если бы в начальный момент времени г'рнбору была задана дополнительная работа, равная (, то он выполнил бы и се, и ту работу, которую он выполнил без этого, т.е.
.(()= '- (17) 252 гл. 3. пвименение Более ОБщих методов а следовательно, в силу (16) Р (в„< х) — Р (у„< у) < Р (и» (у) < х) ( Р (к„< х). (18) Далее, Т»~Г (то+ ° ° ° +Ч -~)~ ~(~»+ ° ° .+~~), и по закову больших чисел т — по вероятности. Таким образом, Р (у„ < у) — О, и из (18) находим г"„(х!у) — г"„(х) — О, г'»(х~у) — г'(х), В случае сс~ О и в случае и = О,Р(ь ФО) О из (16) получаем Пш Р»(х~у) «~11ш Р„(х) = О. » ~а В единственном случае а = О, Р(~ О) = 1зргодичность отсутствует: ш„(р) = у, и ~ 1. Пусть р= ббп (19) Тогда а р — 1 а М~в откуда р <1, р = 1 или р ) 1 в зависимости от того, какое из неравенств я<О, я=О, и) О имеет место.
Таким образом, зргодическое распределение случайной последовательности (и„) существует при р < 1, заведомо не существует при р - 1 и существует лишь в вырощденном случае Р(ь„= О) =1 при р=1. Постоянная р, определенная равенством (19), имеет тот же вероятностный смысл, что и ) т в случае системы с простейшим входящим потоком: это загрузка системы. 3. Аналитические методы. Пусть $„, л ~ 1, — независимые случайные величины с функцией распределения г'(х) и характеристической функцией ~р(1), г„= $, +...
+ $„, г, =О; г»(х) = Р(а <х). При!з! <1 и вещественных г 1 — азу(г) = ехр Пп(1 — гф(г) )), 1Б (1 — сф (г)) = — т — з ф (т)= — д,— з )е ЙГд(х) ч~Г 1 ь а 'ч» 1 «( и» а 1 ,=1 = и (г, г) + о (з, Ф) + и (г)„ 5 Ол, системА оно!! где г ~ еа"дРО(х), +О О г ) е аРА (х), ЗГО и(г, 5) = —,~— 5=5 и(г) = — ~~ — г (РО(+ О) — РО (О)). О=а Функция и(г, О) аналитична в верхней полуплоскостн по комплексной переменной О ((ш Г ) 0) и непрерывна в области ()шГ~О).
Аналогично, г(г, 5) аналитична в нижней полуплоскостп н непрерывна при (шс ( О. Эти свойства сохраняются и для функций и,.,(Г)= ехр( — и(г, О)), и, (О)=ехр(е(г, 5)). Кроме того, !и,О(Г)! ~ е ) 0 в соответствующих полуплоскостях и яч ((О )= 1. Обозначив Ор(г)= ехр(и(г)), получим представле- ние ( — г5Р(1) = ОР(г) и,+(1)/и, (1), называемое 4акториеааией. Теперь отвлечемся от того, что функции у(г), и,~(1) имеют определенный вероятностный смысл, а известны лишь уравнеяие факторизации и перечисленные выше аналитические свойства Ор, и.. Эти свойства однозначно определяют компоненты факторизации Ор, и,+ и и, — с точностью до постоянных множителей.
Оказьгзается, что через компоненты факторизации соответствующей функции выражаются многие характеристики случайных блужданий н, в частности, стационарные распределения величины очереди, времени ожидания, виртуального времени ожидания в системе 61!6!(. Важнейшим примером является тождество Спитцера: если у = шах (О, е„..., ез), ~р„(8) = Ме""", то ~ г"<р„ (С) = и,+ (Г)/((( — г) и,+ (5)), ! г ! ( (. О О Волн М)$5(<со, М$,~0, у = зпрез1 Ор(г) — характеристиче- ОЭО скак функция случайной величины у, то й5(С)= и,О(0)/иц.(Р). Вслн в качестве Р(х) взять функцию распределения К(х) случайных величин ~„, получим выражение характеристической ФУнкции стационарного распределения времени ожидания в системе 61!6! 1.
Ввиду трудности аналитического решения уравнений, определяющих характеристики систем 61(6!(, 61!6(т и других, им ГЛ. 2. ПРИМЕНЕНИЕ БОЛЕЕ ОБЩИХ МЕТОДОВ 254 подобных, большую важность приобрели различного рода неравенства между этими характеристиками и соответствующими характеристиками более простых систем. Эти неравенства основаны на Отношениях стохнстического порядка.
Приведем пример подобных результатов (Штойян 12)). пусть Р,((), Р,(1) — функции распределения. Определим два отношения стохастпческого порядка: (1) Р1 ~«Р2» ' Р1(г) ~~Р2 (г)~ — со(1( оо; (2) Р)~~Р .2=ь ) Р1(х)()х( ~ Р (х)()х, — со<.'1 Соо. Если Р(() обладает конечным моментом та и Р(0)= О, определим Ре(~) = — ( Р(х)Ах, с~)О. шг / и) Окажем, что Р— типа )))ВПЕ ()2'22Ч)Е)е), если Рн~<Р (соот- (1) ветстзенно Р:Рз). Если в системе 61)6!1 распределение А(х) времени между поступлением требований — типа )))В()Е ()2 22)1) Е) ТО Р(Р (Р 1 Р), где Р— стационарное распределение времени ожидания требования в данной системе, Р— соответствующее распределение для системы ))Х)6)1 с той же загрузкой и распределением времени обслуживании.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
