Стохастически рекурсивные последовательности и их применение в теории систем обслуживания тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НА .V ¡Г. СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

На правах рукописи УДК 519.21

ФОСС СЕРГЕЙ ГЕОРГИЕВИЧ

СТОХАСТИЧЕСКИ РЕКУРСИВНЫЕ ПОСДЭДОВАТЕЛЬНОСТИ И ИХ ПРИМЕНЕНИЕ В ТЕОРИИ СИСТЕМ ОБСЛУЖИВАНИЯ

(01.01.05 - теория вероятностей и математическая статистика)

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Новосибирск - 1992

Работа выполнена в Новосибирском государственном уни-

\

вйрситете.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ: доктор физико-математических наук, п.осфоссор В.Б.Калашников, доктор физико-математических наук, профессор А.А.Могульский, доктор физико-математических наук, профессор В.В.Рыков.

ВЕДУЩАЯ ОРГАНИЗАЦИЯ: механико-математический факультет Московского государственного университета им. М.В.Ломоносова.

» Р(э 1992 г. в "/Г"

Защита состоится " ( Т" ^ ^ 1992 г. в "/3 " часов на заседании специализированного совета Д.002.23.03 при Институте математики СО РАН но адресу: 630090, Новосибирск, Университетский проспект, 4, х.417, Институт математики СО РАН.

С диссертацией можно, ознакомиться в библиотеке Института математики СО РАН. л

Автореферат разослан '■ и " 1992 г,

Учоный секретарь специализированного соьета Д.002.23.03

д.ф.-м.н. __, А.В.Косточка

г _

.В«!

ТД<5Л

:ертаций

В настоящее, время в теории вероятностей и ее приложениях получили развитие исследования класса случажнх последовательностей- элементы оторых определяются по предыдущим с помощью некоторой рекуррентной процедуры. Речь идет о последовательностях {/(л)} вида

Лл+-1 )=/,'(А(л),е ), 0, (1)

п

где г - заданная функция и } - заданная случайная последовательность, образующие "управление" последовательности'{.с(л)}. Последовательности вида (1) мы будем называть "стохастически - рекурсивными" (СРП). На значимость СРП указызает тот факт, что в широком класса приложений теории вероятностей (теории систем обслуживания, теории надежности и т.д.) практически псе рассматриваемые модели (в дискретном времени) допускают представление в виде (1). С..едует отметить и другой аспект: любая цепь Маркова (13М) с дискретным временем и достаточно общим фазовым пространством может быть задана в виде СРП при независимых £ , так что СРП является об'ектом более общей природа, чем Ш.

Б работе рассматриваются следующие два важных направления исследования СРП:

1. Изучение условий эргодичности СИ, то есть угпояий, гарантирующих сходимость (в том или инсм смысле) распределений Р(А(л)е. • ) при п -> <о к некоторому собственному стационарному, или предельному, распределению.

2. Изучение условий устойчивости СРП, то есть условий, при которых при малых (в известном смысле) "возмущениях" управления { £ > стационарные распределения последовательности Х(п) тс:яе

изменяются мало.

Изучение общих СРП впервые началось, по-видимому, б работах Р.Лойнеса* и б_ло продолжено (при той или иной степени общности об'екта исследований) в работах А.А.Боровкова, В.М.Золотарева, Л.Г.Афанасьевой. В.В.лалашникова, С.Т.Рачева, Н.П.Ло-онтьовой. И.Ахмарова П.Франкена, А.Брандта, Б.Лизека, Ф.Бач-челли, С.Г.Фосса и др. авторов. Как правило, предполагалось, что последовательность { £ } стационарна в узком смысле (в частности, состоит из и.о.р.с.в.). Полученные результаты применялись для исследования различных классов систем обслукивания.

Выделим два достаточно общих подхода к получении теорем эргодичности для СРП. Первый из них базируется не. свойстве монотонности функции с по первому аргументу.При этом подходе получается утверждения о "слабой" эргодичности последовательности А'(") i т.е. о слабой сходимости распределений Р(Л'(п)с. ) к некоторому предельному. Отметим, что в широком классе прикладных моделей (системах обслуживания с отказами, системах со случайном множественным доступом и т.д.) для изучаемых процессов, как правило, условие монотонности не имеет места. Кроме того, в системах с ожиданием свойство монотонности г мокет быть использовано для доказательства теоремы эргодичности только при специальным образом выбранных начальных условиях.

Второй подход, основанный на понятии г.и. обновляющего

ï/..улег, P. ïhe ctability o.f .л queue v/ith noti-iiulepoiidcuL intc:"-arrív.-a uiid nervi с;4 timos.//' F roc. Cambr. ?>ii 1. 8o<*.. -1 . i:. >. -г-.

события, бил предложен А.А.Боровковцм* и исследовался (для различиях типов СРП) в работах В.В.Калашникова, Л.Г.Афэноо^бзой, А.Брандтз, Е.Лизека, Г.Ш.Цициашвили.С.Г.йюсса и др.авторов. При условии ы/личия обновляющих событий имехя место утверждения со эсголичности последопателянссти х(п) в некотором "силгвом" смысле, эквивалентном в известной степени сходимости в метрике полной вариации. Именно сходимость такого типа н&блзо;<оет.-.я з зироком классе прикладных моделей (напр., в системах обслуживания). Эти два подхода зачастую успешно дополняют ;;пуг диугл.

Заметим, что в теории цепей Маркова исследование вопросов эргодичности' в ?кэоанном'выше "сильном" смнсло хронологически качалось раньше, о работ Деблина, и продолжалось рядом известим х авторов (Т.Е.Харрисом, С.Орееы, С,Асмуссеиом, Х.Ториссоком, К.Б.Атрейк, П.Неем, Э.Нуммелином и др.) независимо (до последнего времени) от работ по исследования СРП. В частности, Атрейя-Неем"* и Нуммелинсм*** был предложен прием, евлзашдл! с ■Возможностью построения регенерирующей пени в расширенном фазовом пространстве и позволяющий доказывать эргодичность однородных цепей Маркс-а в т.н. "условиях Харриса". Э.Нушелииом**** било доказано, что упомянутые "условия Харгп-са" необходимы и достаточны для "сильной" сходимости. В работе

* Борог.уоз А. 4., Асимптотические методы з теории массового об-олужигоним. -,М. : Наука, IS30.

*♦ At'л re:, а ¡;. В. , Ney P., A now approach to the .limit theory of recurrent Markov chains.// Trans. Anio.r. Math. Soc.-1978. -

p.493-501 .

«** Nuaun? LIn i7:., Л fpl.itting technique for Harris recurrent Markc v cm ins. // 2.V.ahr. Gob. -' 973.-V.43.-P. 309-31G.

**»* My'.vn-'iHii 3., Общи,: неприводимые цепи Маркова и кестрииа-

тельные и].ер,-¡терн. - М. : Мир, 1985.

С.Ороя4 получены некоторый условия эргодичности /uw "цепе? Маркова'' с дискретным множеством состоянии, в которих матриц;; перолодннх вероятностей случайны и образуют стационарную последовательность (о:метим, что этот об'ект может бить представлен в виде СРП). Фенсл, н "независимости" исследований условий эргодичности ИМ и СРП следует, видимо, об'яснеть тем, что отправные точки при изучении вопросов эргодичности в теории СРП п ■ в тьорич Ц\! были ризлпчныыи, хотя, при внимательном рассмотрении, ч них можно обнаружить достаточно много общего.

Ц|ЗЛЪ ДИССЕРТАЦИИ - с использованием подходи, основанного на понятии "обновления", провести исследование условий эргодичности и устойчивости СРГ. и некоторых их обобщений, изучит^ взаимосвязь с теорией цоп&й Маркова, а хакасе применить полу -чешшэ результат при исследовании двух важных типов моделей обслуживания: систем и сечей'с очередью и со случайным мноке-лвенины доступом иомиуникашюнных систем).

СОНОВШЕ РЕЗУЛЬТАТ!» ЙИССЕРШМ;;

I.'. Получен» критерии зргодич>тсти для СРП и их с.боыкжи.'. ;» '!■.■[') пиьк т.н. "icriHrHHJ'-cxo^'uvo v: и" "о;;.*, лой Kan.'.;;i;;'-':xo.i[i; '.!'■■[)!", i ыйл.ч Т<П>)Ч(№ орГО.ДИЧНОСТН ДЛ5» НрОЦОССОП С нопрор'-'»"

bii'.i )•; • ' ,i! r>-:.

* :т< у • '.. J-!i» rtov «rmir.r. wit!', с loci li c; \l.y ata l.i orp.ry f.w -r, i i I i\ ia':.i 1 Uic.i, .',' Ar.ii. Trol'. -i9>! - - 1i>, !.'. 3.-1 . Л.<V-

2)• Полупены условия ограниченности по вероятности СГП и чх обобщений и условия существования стэционошых мажорант для с-тпх последовательностей.

8), Для открытых сетей'обслуживания лжексоновского ти..а

•илучонн необходимые и достаточные условия эргодичности; лля

- сетей кайлегл условия зпгодич.юсти, блког.;'.е ч ивсбло-

" ), Локкояно совпадение уровней пропускной способности в системах случайного множественного доступа для цептралисов-'чшах л децентрализованных,алгоритмов управления из определенных

"•-тйссов.

Зев перечисленные результаты являются новыми, Результат 1 ) получены совместно с А.А.Боровковкм, а результаты 2}--Ч --¡кчно автором.

Основные результаты диссертации докладывались на аас.зданиях научно-исследовательского семинара в Институте математики 00 РА1-1 под рук. академтеэ А.А.Еог- вксва, а тякхе семинаров под рук. прпф.В.М.Золотарева, проф.В.В.Калашникова и проф.В.М.Круг-.:оьп (БЖ '.'ТУ), проф.А.Д.Соловьева (ММФ МГУ), проф.Р.Л.Дсбруши-на и проф. Ю.М.Сухова (ЛППИ РАН), на 4-й и 0-й Вильнюсских конференциях по ТВ и МС,(1985,1989), 1-м Всемирном конгрессе общо-отпа нм.Я.Беркулли (Ташкент, 1986),.1-м Международ! м снмпоаиу-

по пллумг.рковскям процессам (Брюссель, 1984), 18-й Европейской конференции статистиков (Берлин,1983), в Мат.Центре им.Ст. Банаха (Варшава,1990), на 2-м Международном семинаре по теории систем обслуживания (Вроцлав,1990), на научных семинарах под рук. проф. Ж.Неве и проф. Г.Фзйоля (Париж,1989), проф. Х.Бач-

челли (София Антиполис,Франция, 1939), проф. А.Боксмы .Амстердам, 1991).

По теме диссертации автором опубликовано более 20 работ. Основные результаты содержатся в [1-12].

СОДЕРЖАНИЕ РАБОТЫ

Диссертация состоит из трех глав, разбитых на 17 параграфов, и списка литературы. Общий об'ем ¿Ш страница.

В первой главе диссертации проводится исследование вопросов эргодичности и устойчивости СРП и их обобщений. Пусть (а;,а„.) и (у, 2^.) - два измеримых пространства, г : х- у •> к - измеримая функция и { £ } - стационарная (в узком смысле) последовательность случайных величин, прини-маьуикх значения в пространстве £ . Пусть X (гн ')-Г (X (п), £ ) есть СРП с управлением (г, {£ }) .Ради упрощения формулировок, мы будем предполагать, что последовательность метрически

тран&ятивна, а начальное состояние А'(О) неслучайно.

г-

Обозначим при л < к через к а-алгебру, порожденную случайными величинами £ Д , и через е^. , з^ , со-

Г? П "г* 1 К , А'

ответственно, а-алгебры

С £

- О ( £ , л < к } ; 9" - О { , -И < л < СО }.

Введем ряд определений. Будем говорить, что при некоторых

с

л ^ О и и ) О сооытка л е 5- , ■ является обновляющим для СРП

Л

Л' (л / , если найдется некоторая змаримая функция д : г/"** -» 5; , такая что на событии л ( -е. при всех элементарных исходах а; о' л ) y,:^'лez место савонстзо:

Х(п+т+1 ) = д ( % , . . . , £ ) . '(2)

При некотором.л; > О назовем последовательность событий { а }, А е г",„ обновляющей для СРП Х(п) , если найдется

и Л П+П1

функция д такая, что при всех п > О на событиях Ап выполнено (2).

Будхп говорить, что последовательность х(п) канлинг-схо-дится к некоторой последовательности Хп , если

Р( Х(к)=Хк при всех к ^ п ) 1 (3)

при /1 -> Ю .

Введем на пространстве з^-измеримых случайных величин сохраняющее меру преобразование сдвига и такое, что =

с

п.н. Соответствующее преобразование сдвига У^-измерпмых мно -жеств обозначим символом т . Символами т1', ик, -оо < а* < « , будем обозначать итерации соответствуоцих преобразовании.

Наряду с {х(п)), рассмотрим при к > о последовательности { А■ {п) = и~к X (п+к), п -к }.

Будем говорить, что последовательность х(п) сильно кап-линг-сходится к некоторой последовательности х" , если

ОТ 00

Г ( II п ( *П+1= Хь(п+1 )} ) -» 1 при л -» оо . (4) к=0 1-0

В § I.1 формулируются необходимые и достаточнне условии крплинг-еходимости и сильной каплинг-сходимости СРГ в терминах обновляющих событий. В частности, имеет место утверждение. *

ТЕОРЕМА 1.1.6. Следующие два условия эквивалентны: 3) последовательность У(п) кашлшг-с-ходитоя к некоторой стационарно» последовательности А'", такой что Xп'>1~ с и". Е ) п.>«,;

п

2.) оумостг.уют целое число т 2 О . собственная случайная г-елнчи-

но у и стационарная последовательность событии {в }, в е 1 п п

такие, что послемовательность { у ^ п } л в является nv-и 1 ' 1 л

обновляющей для { Х(п)}.

Выполнение условия 2) при Еу < «> необходимо и достаточно для сильной каплинг-сх^чимосш я(л) к последовательности х",

Кроме того, в § 1.1 показывается, что в случае н.о.р. последовательности xln) предлагаемые условия каплинг-сходимости эквивалентны (в известном смысле) хорошо изученным условиям аргодичнооти по Харрису для однородных LIM. Помимо этого, приводятся оценки скорости сходимости в теореме эргодичности. Рассматривается случай нестационарного управления.

В § : .2 вводятся в рассмотрение т.н. рекурсивные цепи (РЦ1, являоциеся обобщениег. СРП и ЦМ. А именно, пусть на одном вероятностном пространстве заданы стационарная последовательность и некоторая последовательность ж (л), п >. О. Будем говорить, что Xin) образует рекурсивную цепь с управлением

с , если при всех ^ О п

Ра'(л-Н )е . /Х{п),. . . ,Jf(0),{£.} )=Р(Х(т-1 . /Л(л),£ ) Л.Н.(5).

Л Л

Если условное распределение в (г>) не зависит от л , то РЦ естественно называть однородной (по времени). В работе в основном ра'.'.'.".матриваются однородные РЦ, так что, удобства ради, в д.'г.'!!.н'-Й!;1км термин "однородная" мы будем спу хать.

см (теорема 1.2.ß), чю существует задание но-

х(ина одп..,м с ,f ') вероятностном ииоотран-г '

; ; , ]■;;.. .д } •- iь..vio дснчтелы «JT)

ч?•■> л(п) иклязч2i.! с некоторым "росши)>£нн1.м

; А } следует и стационарность { )>

* 1,3 посвящен исследованию вопросов эргодичности РЦ. Зафиксируем т > 0 и обозначим через У а-алгебру, порожденную случайными величинами ( Х(О),...,х{п)\ , к 4 л+/»}}. Приведем основное утверждение параграфа.

ТЕОТ : МА Т.3.3. Пусть (Х{п)1 есть РЦ с управлением { £ >; последовательность { } стационарна и метрически транзйтпвнэ. Предположим, что существуют число т > о. стационарная последовательность событий ( а }, А е и измеримые функции Р : -» [0,1 ] ; Ф : У™*1 * ■» [0,1] ( где ф(у0,. . . ,ут; . )-

является вероятностной мерой на X для п.в. (уп,...,у ) <=-

и т

относительно распределения .....' ) ), такие что

(1КС) Е { Клд)'р(1а.....} > 0 ;

(11^) при О) е А , В е %%

р(А'(п+т+1) в в / г„)/л)» Рап.....ел+т)

Тогда можно задать на одном с { Х'п), } вероятностном пространстве стационарную последовательность { Хп ) такую, что х(п) ас-сходится к хп. При этом последовательность { хп } образует РЦ с теми ке управлением и переходной функцией, что и

РЦ {-V (л )).

Помимо отсмо, в § 1.3 рассматриваются некоторое условия, окаоилгоишы., достит->чш;ми для эргодичности. Так, в случае,, когда с.'.мп улраилягзюя последовательность ? удовлетворяет

;.гт|чч.и-;:■;ик:■;!; гпла !>( , ....), с / , к ^ п ] ) ->

; г

• ' ..... в С / , }

п.н. для некоторых числа ц > О, вероятностной меры ф на ( ) и любых в е и цилиндрических множеств с е у 00 ,

имеет место

ТЕОРЕМА 1.3.6. Если существует множество I' а £ , стационарная последователь ость событий Ап & , Р(/1р) > О , числа т > О, р > О и вероятностная мера ф на ( ) такие, что

1) Р( Л'(п) е V / „ ) = 1 на множестве А при всех п > О ;

л— 2 л

2} Р( Л (х,/п+1 ) е В ) 2 р х ф(Я) при всех 8 е 2» , х е I' , то для РЦ А'(л) справедливо утверждение теоремы з.З.З.

Здесь (д'(л'.л)} есть РЦ с начальным условием х(х,0)=х, управлением {£ } и той ко переходной функцией, что и у РЦ х{п), а, в свою очередь, {£ } есть последовательность и.о.р.с.в. с распределением <|>.

В § 1.4 обсуждаются некоторые условия, являющиеся необ-холимыми для каплинг- и строгой каплинг-сходимостей. Как известно, обычно обновляющие события для СРП (как л события, ■ фигурирующие в условии (И(?с) теоремы 1.3.3 - для РЦ) предета-вимы в виде

Лпъ Л^ ( А-(л) е V ; <£#|.....е 2 ), ^

.....

где Г * а - множество из фазового пространства х , которое залает■ ■я с номошь» некоторой (пробной) функции : 5; к ,

К и - { л- : 1Лу) <- N ). (8)' .'.•г-И'.ьчх, что себытп.-! такого вида не является, ьиобше говоря, -и. яь.'!; ::и\ '<ь "ч'¡:У:Ь" (? .....

и

последовательность Вп такую, что

ип Е { Х(п) е V }, P(S/( а ----in+n) е Z }) > С , (9}

то, тем самым, определяются и требуемые обновляющие событии ь, следовательно, последовательность А'(л) сильно каплинг-схэ дится к некоторой предельной. В свою очередь, последовательность в •" 5удет построена, если мы найдем вещественнозначную стационарную последовательность { к" } такую, что ¡Ахin)) i Yn п.н., и возьмем Bn= { fn ^ N }. В случае фазовых пространств х=а либо x=s и функции L(x)=x последовательность г'1 естественно называть стационарной мажорантой для х(п>. Условия существования стационарных мажорант для СРП обсуждаются в п. 1.4.2. Имеет, в частности, место следующее утверждение:

ТЕОРЕМА 1.4.3. Пусть x=3t+ , и Шл)}, X{0)=const. есть СРП с управлением { }. Предположим, что для некоторого с > О существуют функции Ft : '¡Г -> S , ¥2 : « f ■> 1 , F3 : у03 -» Я такие, что случайные величины фп = f **••'•

C„U) = F2(x ^л'^л-i" • • h Фл "'з^л^л-Г'"' удовлетворяют соотношениям:

1) A'(m1 ) -А' (л) ^ фп + С „Шл)) + фл-/(АГ(л) ^ С) П.Н.;

2) BJ) < О , Е ф

л ^ л

Я) для некоторого 5 > О

sup Е { |C0(x)|2+Ö } < со ; х

4) при всох л > О, х

Е i / > О

Если при этом для множества t'=[0,c] выполнено условие

1

(■..«11,1ост]<ук^ случайная величина , Е < га к конечной ¡{,".:чг> тичо.'с с ,...,.е X , i'aiciu: что для любых у е н, л >. ;

неравенство

гп(У') ** ГЛаХ (* I )

/г и ОНО! п '

справедливо п. и. на множестве { ..{у, к) с V при всех к ^ л } , то дал последовательности {А(л)} можно построить стационарную макоранту.

Здесь X (у,л) есть СРП с начальным условием х(у,0)=-у и

= £ сджу.л).

Отметим, что условие (Л'/.) выполняется, если функция г удовлетворяет условия Липшица по первому аргументу либо мпокз-- ствс V конечно.

В п. 1.4.3 формулиру6-тс.я аналог теоремы 1.4.3 в случае произвольного фазового пространства с использованном т.н. проб Ни/, функций.

Отметим, что для каплинг-сходимости условие (9) является кгбкточнш, и в случае фазового пространства %~л его естественным «налогом ив ются уеловне ограниченности по вьрояшооти иоиолоёьгол^ности IX(г>)} . Кмоет место

ТЕОРГ.'.'А 1.4.5. Предположим, что на одном вероятностно:-пространстве заданы последовательности ве:цественнозначных случайных "неличин {.V (л)}, {Ф }, 1С ) и возрастающая последовательность а-алгебр (э > , такие что

У) ,. л г', ;-А'.'п) < ф -1 С + С. • I (А (п) < с„) Л Л 7

Н.М. 111<И ВСГ;л л ^ О ДЛЯ. НОКОГОрЫХ ПОСТОЯННЫХ СуС,, ■

) Сф ) ^ с1) аиионарная метрп ,скп транзитивная лоследонате.щ -ьоо'П,, I.;. О ;

л; , •. ' ; > • /. : !•'•' ' . ' ! • ч и.;. ;

.1 <■■ -fi.fi I:

A) f»up Е ИС„| '£?( | С | ))=с < <*> ДЛЯ НС которой' ФУНКЦИИ ,

п

лзляпчейся непрорисиои, выпуклой вверх, монотонно воорзстаттсеЯ

удовлетворяемой условиям:

■1(0)-0 , I (Л- Г '■•()) .'-':< < ■

Гогда пог,^';дгз.1Толы:ость (х[п)} ограничена (сисрху) по теро-

Л'И'ОСТИ.

Иной подход к построению стьционэрних кокорант а получению условий ограниченности по вероятности обсулсдается в п. 1.4,5. В § 1.0 изучаются условия устойчивости рехурсиэнгх цепей. Наконец, в § 1.6 вводятся т.н. процессы (в дискретном ?шт иопрершшом времени), допускающие вложенные ?Ц. Зто понятие йстестввн!г«!м образом обобщает понятие процесса, допускающего ^чоженную Ш, предложенное Кендаллом. Доказываются теоремы эргодичности для таких процессов.

Глава 2 посвг ена изучению вопросов эргодичности и устойчивости для т.н. сетей обслуживания джексоновского типа и некоторых их о.общении. '

Пусть п > О - целое число. Обозначим через { z{n), п >■ О >

¡.И с (/V-i-2 ) состояниями 0,1.....N.N+1, начальным значением

у. (О)-О и матрицей переходов !!/>,• jl! > i,J-0,... ..v+1 , где Р4+1 avj"1 ' piO~° при БСех 1 ■ Руле" предполагать, что состояние (// +1 ) л.,етн;:симо ии любого состояния í ? О и. следовательно, является поглощанцим. Обозначим через тс^ , i ; н , сродное число посещений состояния i траекторией { >.

Нпяоеем матрицу p¡ ¡ ( а также ДО Z(n) ) ациклической, если никакие два состояния / ,./ не могут быть сооЗщасаимкся.

Рассмотрим теперь открытую сеть обслуживания с N одно-канальными станциями, в которую поступает рекуррентный потоп вызовов, т.з. времена между моментами поступления вызовов предполагаются независимыми и одинаково распределенными со средним Е-г =1/а > о . '<ажд.*й вызов из входного потека независимо от других направляется на станции с номером к с вероятностью р0 , Рм=1 • Времена обслуживания на Лг-й станции

{а'р независимы и одинаково распределены со средним Ея*-;.^ ,

о < а д. < ® . На каждой станции вызовы обслуживаются з порядке

поступления. После окончания обслуживания на *-й станции вызов

с вероятность» р}. . переходит на /-а станцию и с вероятностью

р, .,покидает сеть. Такие сети принято называть сетями джек-к , 2

ооновского типа.

При II % О через <7 - ( д'1 , ...„д'"' ) и-У * ( у1 .....уЛ' )

1 п п 4 п Лл лл лл

обозначим, соответственно, длины очереди и остаточные времена обслуживания вызовов на различных станциях б последовательные момы-'тн поступления вызовов в сеть. Нетрудно видеть, что ио-следовутельчость (я ,'х„ > образует однородную ЦМ, поэтому исследований условий ее оргоцичности можно проводить как методом обновлявших событий, так и традиционными методами, ислольоуе-

'н теории ЩЛ. Дяя нас оказывается более удобным первый г ¡■.¿/.у/х • '^ т мое^ о

ТЕОИЫЛ 2.2.Т. Если выполнено условие

< при всех У=1,___,ы, (Ю)

то ч;.>1 лгмом начальном значь-нии и/.. ,"<•„) последовательность

,J ' и

• „ ' г.аплинг-СХОДИТСЯ К МПС' орой стационарной последов«! -

.........., /7 , /I

'/.звестно*, что если условие (Ю) не выполняется, то последовательность не может быть эргодичной. Поэтому утзержьени. теоремы 2.2.1 носит окончательный характер.

Отметим, что утверждение, аналогичное теорема 2.2.1, биле сформулировано К.Сигманом**, но при двух дополнительных предп.; ложениях:

1 ) рк >0 при всех к=\,... ,Н ;

2) для ИМ (яп >Хп' существует положительно возвратное компакт ное множество.

Кроме того, в другой работе К.Сигманом*** было также сфор мулировано утверждение теоремы 2.2.1 без дополнительных прелпи ложений, однако при атом строгое доказательство было проведен. > лишь для случая ограниченных громен обслуживания, а из пестро гих и очень лаконичных рассуядений для общего случая не удает ся восстановить аккуратное доказательство. Отметим также, что предлагаемое в диссертации доказательство использует иные идеи и, тем самым, существенно отличается от доказательства, предло женного К.Оигманом.

Рассмотрим теперь случай непрерывного времени t > Т> и при 1-],... ,N через q'{t) обозначим количество вызовов, находящих«.;! в момент времени <+о на ;-й станции ( ,в очереди и на обслужи вании), и через %'(£) - остаточное время обслужиьяьяя нерног из 01'ик вызовов ( полагаем %J (f }-0 при q' (/ )-0 ); q{t )"(:/' it ¡,

* Тфанаеьока Л 06 эргодичности открытой сети об'Мутива щи. // Теория веронти. и примен.-Г9С?.-Т.32.Н.4. -С.77? -7о!. *» Sipjnan И. . Queijo.s as Harris recurrent Markov chain.-,.// Си.;I!ciп^; :',узЪ.>;и;;. - 19'УЗ.-'/.3, H. f . -F. 17'j- ' 9ГЗ. »■»■> «itfiwi i'. > flm ,'M.abU ity о Г roon :) jeu« i no tw> >r<.u ., / ;p r" . hmI aj.pl 1 ГОО . ! . 3'_>, IJ. ! . i-.1t

); X',i )-(%''(<).)• Обозначим Z ,={0,1....}. По теоремы 2.2.T и результатов 5 1.6 следует

РЕОРЕМА 2,2.2. Пусть нннолнено (Ю) и случайные неличины •с имеют ногхзвютчатое распределение. Тогда существует собствен-

; и

ное распределение Р{.) в пространство Z'^ * такие, что при лиЗим начальном условии (<у(0) ,%(0)) имеет место при t ~> ю слабая сходимость Р( (</(< ),%(t) е . ) =» Р( . ) .

Отметим, что в работе А.А.Боровкова' также доказано утверждение теоремы 2.2.2, но при двух дополнительных предположениях: • . ■ ■

(С 1 ) Существуют числа с > О, т > о такие, чуо для всех i ,х >, о Р(1Л ^ t+x / 1 t) ^ , Р(s* t+x / sk. > t) si ;

(C 2) Случайные величины x неограничены ( т.е. Р(т > х) > О

л л

при всех х ).

Уместно сказать, что, как и в случае теоремы 2.2.1, утверждении теоремы 2.2.2 носит окончательный характер, т.к. известно, что при отказе хотя бы от одного из двух условий этой теоремы для iqit ) ,%{t}) не существует предельного собственного распределения.

Перейдем к замкнутым сетям. Рассмотрим конечную М с к

сообщившимися существенными состояниями и матрицей перехода

н

iip- -Ü ; 1 < i,J ^ >' l Pi г'1 ПРИ всех 1 н определим сзмк-'J j=i 1J

нуту» сеть джжсоновского типа с ы одноканальнымн станциями и п вызовами по аналогии с ранее введенной открытой сеть?). Справедлива

ГКроысов а. А., Предельные теоремы для сетей обслуживания Л. // Тоорил вороятн. и ее примен.-ЮЯВ.-Т.ЗТ,N.3. - С.474-400.

ТЕОРШЛ 2.4.1. Если в замкнутой сети обслуживания дже[.оо новского типа при всох к~-',... ,.'>' и С-const распределения случайных величин lsL}+c) нерешетчаты, то имеет место утверждение

теоремы 2.2.2.

Аналогичное утверждение (ко при выполнении дополнительных условий (С О-(с 2) ) было доказано А.А.Еоровкогпм*.

Глава 2 состоит из 4 параграфов, каждый из которых (яд исключением § 2.4) делится на подпункты.

В § 2.1 рассматриваются ациклические сети со стационарными управляющими последовательностями. В п.2.1.2 доказывается, что для ациклических сетей с однсканальными станциями утверждение тооремы 2.2.1 остается справедлив™ и при тационарных управляющих последовательностях. Б п.2.1.3 приводится теорема устойчивости, Б н.2.1.4 рассмотрен пример ациклической сети с регенерирующим входным потоком. В п.2.1.5 формулируются условии эргодичности ациклических сетей д-ексоновсксго типа с многоканальными станциями. В п.2.1.6 доказывается единственность стационарного лспределения в ациклических сетях типа G/GJ.

5 2.2 посвящен исследованию открытых сетей джексоновского типа. В п.2.2.2 доказывается теорема 2.2.1. В п.2.2.3 получены-Теоремы устойчивости. В п.2.2.4 обсуждаются вопросы :»ргч>д/,чно-сл'и и устойчивости открытых сетей джексоновокого типа с много 'канальными станциями.

в 5 2.3 показывается, что для открытых сетей при отказе от независимости и одинаковой распределенности ущкшл.'П аих Iюсле/юмя 1 -гльноотнП ь .условия--: т.' "р-тул;ца;ос1Ги (:г:-и vc-

ЛОЧИЯ Я)|.':.*)>/.'Ci: сг'.'.'ГТиеННЫМ i, ")СбШ';НИ;;М уСЛ'.ВИ.-' (С : ) ) I.. .ел-.

.. гелъность lg (t ),% ( i ) ) является ограниченной по вероятности.

Наконец, в 8 Г 4 доказывается теорема 2.4.'.

П iviане 3 рассматриваются т.н. системы со случайным мно-,;•,.(•,твенним доступом и открытые сети, образованные такого рода онотемами.

Система случайного множественного доступа состоит из.одного обслуживающего прибора и бункера для ожидания (бесконечной емкости). Вызовы поступают в систему в моменты времени »-0,1... партиями об'ома £ . Будем предполагать, что £ есть стационарная метрически, транзитивная последовательность, F.£j < 1 ; Р( С;} 2 ) > О. (11 )

Предполагается, что между вызовами в каждый момент времени невозможно устапог гь связь. Это означает, в частности, что они нч могут образовывать очереди на обслуживание. Другими слонами, в любой момент времени ( п+О ) кажднй вызов, находящийся в си-отеме ( в бункере или во входном потоке) принимает решение: поступать ему на обслуживающий прибор либо остаться в бункере iнаправиться в бункьр) - сообразуясь только с доступной ему информацией о предыстории система и о его личной "истории" ¡более точно - чуть позже!.

Совокупность правил, по которым вызовы принимает решения, будем называть алгоритмом управления.

Предположим, что нам а алан некоторый алгприш упряил« -н.1Я !. Оппк.см функционирование систем;:.

Об.;ьнсч«м чороо I) уммашое количество 1.<,:х>:<ст, ii.v:? пиу 1 н

H; i ;; >;i6 j\i [> f.t.• ; 11 i о-о i. rç.ui -• о пт.-т; .

: i ЧП'Арн'и! bp.il¡¡и U<.»> ! • .! ; : : ; Г- ;

систему. Если же в \ , то обе, /кивания не происходит, в течение интервала времени (л,л+1) обслуживающий прибор либо бездеи ствует ( эсли в^-0 ), либо "блокируется" ( если 1)^2 ), а все поступившие на прибор вызови отправляются в бункер.

Если обозначить через V число вызовов, нахсдячихся в бункере в момент времени (л-0) , то при всех п > о имеют место соотношения:

V 1 = V + I - Нв =)), (12 >

п+1 ~ п 'Л п

где 1(0) - индикатор события-о , а величины в =в (л), конечно

же, зависят от алгоритма л.

Будем называть алгоритм управления А эргодичеосим,если распределения Р( V е . ) сходятся к некоторому собственному при л о> .

В главе 3 для заданной входной последовательности ?

и

исследуется вопрос о возможности построения эргодических алгоритмов управления, принадлежащих определенным классам "децентрализованных" алгоритмов.

"Преднс.орией" системы в момент времени п будем называть совокупность величин:

1) { Ук , к < и },{ , к < п } ■2) { ву , к < л }.

"Индивидуальной историей" вызова ;<• , находящегося в си <пеми в момент иремени л , будем называть посл^дивачелишгл ь

< .....г; •'

где к-к-(х) - момент поступления внзина 1» систему; г} < *. ... <- г; < (I - И5"¡дылул'.не момон си 1.0(1.' и, а кот г,; данниЛ

принимал решения поступать ьа обслуживании» прибор.

Основное требование, которое накладывается на классы рассматриваемых алгоритмов управления, состоит в следующем: о каждый момент времени вызовы с. одинаковой историей должны принимать одни и те же решения. Другими словами, вызовы с одинаковой историей неразличимы для об'екта, управляющего системой. Поэтому все эргодические алгоритмы (если таковйе существуют) с необходимостью обязаны быть стохастическими. Это означает, что в каждый момент времени п решение вызова х , выглядит так.:_ с вероятностью рп х поступать на обслуживающий прибор (где р , , естественно, зависит от предыстории и »л-

Л , X

горитмн), и число р одно и то же для всех вызовов с одина-

П , X

ковой историей.

Назовем алгоритм-управления централизованным, если в каждый момент времени п он может использовать всю информацию о предыстории системы, и децентрализованным, если в каждый момент времени п ому доступны из предыстории системы лишь значения { -)к , к < п }, где 7а= иш1' {Вк ,2).

Проелейшим децентрализованным алгоритмом управления является хорошо известный алгоритм -АШХА, при котором р *1>-сопя( Л.чя нсе\ вызовов и всех моментов вримони п . Однако, как новео ню, <>в не является ьргчншческмм.

Начнем с. рассмотрения класса п.онтралп.ю-ю-.ишл; г,.!",-"]..го,кв •,: ,1 } , для ког<".| ¡к-ли"• ^ям <ч>

¡¡.¡.•••¡.»¡I.!>п.и>Н''й истории Iо"',01 ■■")! 1. 0; „чпчни ъ « л • >■.•

Известно*'**, что если образуют последовательно! п. и.о. р.с.в., то при < е-' алгоритм AQ с , при котон м р ^ р {лп) = 1/шах(1,1/ ) , является эргоднческим. Если mi

ПРО п

> е~- , TO V S Ъ>П(Л) ■* 01 П.Н. при п -* <*> ДЛЯ ЛЮбоГО

А е л., . Более общо, если F образуют стационарную метрически

I / "" Л .

транзитивную последовательность, то из рассуждений работн

А.А.Боровкова4*"5, нетрудно получить, что при < e-i ььедшпл п

выше централизованный алгоритм А() также будет оргодичсским.

В.Гачек показал, что если {; есть последовательное^

и.о.p.c.в., Ец < е~1 и Е( вхр (ö£?)) < <я при некотором 5 > О,

то для нее существует эргодический алгоритм а1 ь %п вида 1

Рп=ч " • + V/(V2) + ; (13)

где I? в (0,1) и Cj > о > е„ -■ некоторые константы. Б работе

3.А.Михайлова***'* доказано, что если ? есть последователь

л

— 1 2

ность н.о.р.с.в., Е£? < е и < ои , то существует депонт-рализованный алгоритм е такой, что последовательность I.-'

U h

ограничена по вероятности, т.е. sup Р( I/ 1л2) > х ) -» о при

п

п -» оо . в § 3.2 формулируется следующее утверждение.

ТЕОРЕМА 3.2.1,. Пусть } - стационарная метрически транзитивная последовательность, < в"1 . Тогда найдутся посто-

• Payolle С., Gelernte л. and Labefcoullti J., Stability au'J op

mal control of the packet aw L tc.hirv; broadcast channel.// ,J. r.;'

Ал hoc . Cornput. Mach . - 1 977. -V. ?4 . - P. 375-306.

»* Фалин P.Я., Случайные пропессн в структурно • сложных оис.ч«;

ма;< обслукипан" .. Лисе.... д.ф.-м.н.- М. , М'',У, ЮбГь

*»« По|»;ьк1 «в A.A., Асимптотический анализ в- ;тн1»к: чичнич-ч с*

той.// лап.-) '.fr;. п.г,, -о. г ста- ]:.■;"-..;.

*»*» Jin.i'.'i: В., Hi ttinfj-tinw arid оссира t iun--1. iia- bf оиг.г, f >»•;.! ic.| by ilri П. a, *a 1 yr- i л vii tb api-. I i out i' ' i.;. /'/ /• av. ; J r-oba!.. -1 -V .' U\. -P.',

**■>>* Ми;- afb'ioü Ь. А. Л *' if. , J' [); s '!•;:. к- i-l.: анализ ус л,,:1!!! и'.;:' а ;1

лннме с/, с (, с^ , такие что для последовательности ^ п ) , построенной по алгоритму Ду вида (13), существует стационар пая мажоранта .{ У } (из этого, в частности, следует ограниченность по вероятности последовательности { I»' } ), Бели, к тому ян,

Р( 5л+1=о / ^ ) > р > о (и)

п.и. при всех л > О дня некоторого р-сопвь , то алгоритм А1 явияотся эргодическим.

Заметим, что для н.о.р.с.в. условие (14) следует из

< 1 . Отметим также, что можно привести шше, более слабые варианты условия (14), при которых теорема 3.2.1 имеет место.

Теорема 3.2.1 обобщает предшествующие результаты в двух направлениях: 1) снимает все ограничения на существование моментов выше первого для ; 2) рассматривает случай стационарной метрически транзитивной последовательности {) с произвольными зависимостями между ее элементами.

Перейдем к рассмотрении более широкого, чем а0 , класса алгоритмов. А именно, допустим» что в каждый момент времени п управлению доступна следующая частичная информация об индивидуальной истории вызовов: известно, поступил данный анз в в момент л или ранее. Другими слонами, для каждого вызова л- , находящегося в систем в момент ( лчо ) , известно, какое из событий ( к'х < п }, { к - п ) имеет место. Следовательно, все рнзоны, находящиеся в системе в момент времени { л<0 ¡, условно рп.-'бпнаится на две группы - £ вг овпв, пгни<-;ш;чх и момент л, !| и- 1ыг>'Н»ип, находящихся бункере в момент ; ч О ¡.

('!.>• .:,|(ЧЧЧЧ! Ч-:|>0:( Л «» , КЛй<*.<; .'ПИ ОриТМ-!!», К >Г'.р>-' Ч(-ПЧ

использовать данную информация об индивидуальной истории вызовов, и черва s = - соответствующий подкласс децентрализованных алгоритмов. Ясно, "то каждый алгоритм л е А, определяется набором вероятностей ((р^ »рп )) , зависящих от доступной предыстории, где р'п -вероятность, с которой каждый из вызовов принимает тешэпио поступать па обслуяивэкедий прибор, а р - соответствующая вероятность для каждого из V вызовов.

Обозначим Г/,=Р(t?-Л-), А-=0,1,... и при 0 $ г < 1

$(■') - Т. .

к-О А

d = su р ф(г )>>охрГ(1-г )ф'(¿-)Abir j s sup h(r).

Отметим, что ранее рассматривались липь случаи р' - и р'п ■- 0 (последний, как нетрудно г.идэть, с помоцъю замени времени можно свести к случаю /У ^ р- , что соответствует алгоритмам из класса ¿0 ). В случае р' & 1 было показано", что если ц есть последовательность н.о.р.с.в. и

а < min ( 1/2 , г0 вхр ( /уг7 - 1 ) ), (15)

то централизованный алгоритм вида

рп = с/тах(1 ,!»'п) , где с = 1 - г}/г0 , (16)

является оргодичестсим. Если ке в (15) заменить неравенство на противоположное, то в классе й^ (при р' « 1 ) не существует эргодических алгоритмов. Л.А.Боровковым** получен следуплин -результат: если { £ ) есть стационарная метрически транзитивп.л

П

последовательность и выполнены условия (14) и (15), то алг ритм

«Fayollo G. .С-ЧетЪе Е. and Laboioulle J., StabilJ ty aod op I j.d'al control of tht packet switching broadens t ^ЬсплеЗ. // J.A.vaoc. Comput-rMc'ch. - 1977. -V. 24. -P. У7Ь-?'В6.

»* Боровков A. A., Асимптотический анализ коммуникационных с-зто». // ДАН. -Iöcl?. -Т.296,,'J.5. -С. 3ОГнЗ-ТОоВ.

(16) является оргодическим.

В диссертации доказана следующие утверждения. Ьс,--нер-вих. получено естественное обобщение последнего результата:

ТЕ0Р2МА 3.8.Т. Пусть {£ } - стационарная метрически транзитивная последовательность, .удовлетворяющая условия].: (11) и

s < min( 1,d ) , (18)

и число г0 г [0,1] таково, что а - л( rQ ). Тогда алгоритм /1 е «г., вида

Р.; Г" 1-rf) , рр « k0(r0)/imx(l',wn) ; п s5 0 (19)

является оргодическим.

Кроме того, имеет место■

ТЕОРЕМА 3.3.2. Пусть { f } - последовательность и.о.р. с.в,, и число гп ь [0,1] таково, что d в h{rQ). Если выполнено

(17), то существу:от числа д с. (0,1 ) и N > О , при которых алгоритм управления 'л с вида

' ч Л

^ " ' ^ = tV'ivsb'i.HT^o))*. > 0 (2°'

является аргодаческим. При аачэно знака неравенства в (10) на противоположный в классе п., не существует оргодических алгоритмов.

В 5 3-4 рассматривается более широкий, чем ¡^ , класс алгсритмсь, учитывающих более полно индивидуальную историю вызовов, который,по аналогии с введены;;,:;-; Б.С.Цыбакопкг.: и В.А.Михайловым* алгоритмами дробления для систем с пуассоповским вхо -цом, мы будем называть классом алгоритмов конечного дробления. Более точно, при каждом г-О,!,?.,... вводятся классы ¡¿is) алгоритмов s-дробления и & а1"1 децентрализованных алго. ¡тмов

(^)

-дробления. Формальное описание классов и ' достаточно гро-

моадко к приводится в тексте г сеертацни.

Обозначим через Л' некоторую константу, приближенно равную 0,48778 ( правило отыскания F содержится в тексте диссертации) . Имеет место

ТЕОРЕМА 3.4.3. Пусть Ц ) - последовательность и.о.р.с.в., удовлетворяющих (11). Если a <F , и о можно указать s ^ 0 и построить алгоритм А с а ~ , являющийся оргодпческим для £ .

Отметим, что в работе Б.С.Цнбвкова и Б.А.Михайлова* строится некоторый централизованный зргодпческий (в известном смысле) алгоритм дробления для систем о пуасооновским входом. Теорема- 3.4. является естественным аналогом этого результата в случае произвольной последовательности и.о.р.с. .. £ £ ) с конечным средним. Более того, строится децентрализованный алгоритм управления.

В 5 3.5 рассматриваются системы множественного доступа с (пн !)-конфликтом ( т.е. системы, в которых конфликт происходит, если на прибор поступает одновременно более in вызовов), являющиеся естественным обобщением рассмотренной ранее модели. При этом предполагается, что выполняются условия

Вс.. < г Р ( £, >. /п+1 i > о , Доказываются естественные аналоги приведенных раис-е ут;ш|даш

В й ЗЛ5 полученные пезультнтп переносятся на случ.дй открытых ациклических сотен обслу^ивани;;, оорао-тчншп системам;, случайного миг^ственпог о доступ;;.

« Нмогк^в Р. г;. .Михайлов Р.Л., Олу чайный п.Чмте; тн'пынп д» .¡туи I!..\я, о,мим дробления.,'/ Нр.,.',л.и..-|л;;ичп !iiw.. • i';;/.». Т. ió,f!.-;.- с.б1: ?9.

Наконец, в § 3.7 приводятся теоремы устойчивости для не-когорнх иа рассматриваемых моделей, а также оценки скорости сходимости в теоремах аргоднчности и устойчивости.

ОСНОВНЫЕ Г(УБЛ11КА1|]ИИ АБТОРА ПО ТВ® ДИССЕРТАЦИИ

1 . Об условиях эргоничностл в многоканальных системах массового обслуживания с ожиданием.// Сиб.матем.яс.-1S53.--T.£4,U.6-С.168-175.

?.. Оценки скорости сходимости в теоремах эргодичности и неппеоывности для многоканальных систем обслуживания.// Теория вероятн. и о« примен.-1984.-Т.29,N.S.-С.605-6GG. :

3. О существовании оононлэния в многоканальных системах с ояидаь.юм./7 Тру'ды IV Междуна-р. вильнюсской конф. но теор.ве./о-ятн. и матем.статистике, тез.докладов.-5985.-Т.3.-С,254-255.

4. Об одном способе оценивания скорости сходимости в теоремах эргодичности и непрерывности для многоканальных систем обслуживания.// В сб.. Предельные теоремы теории вероятностей. 1 руда Института математики СО АН СССР.-л985.-Т.5.-С.i26-137.

5. The rrethed of renovating events and its applications in qtieuein-з theory.// Semi-Markov mode]a. Theory and applications. Proceedings of art International Symposium on Sem.i.-Markov processes and their applications. -Plenwr. Press.-liew York-London.-1936.-P.337-350.

o. On stationary majoianta for сtcchantically recurrent eouences.// Труди v Междунар. Вильнюсской конф. no теор.веро-ятн. и матем. статистике, теа". докладов.-198Р.-Т. 1.--С.156.

7. Comparison of service disciplines In G/GI/'гл queues./V ItffilA Research Peport, Ы.1097, 1069.

6- 0 некоторых свойствах открытых сетей обслуживания.// Пробл. передачи информации.-1989.-Т.25.Н.З.-C.SQ-97.

Я. Эргодичность сетей обслуживания.// Сиб.матем.я.-193;.-Т.32,N. 4.-С.183-202.

10. (Совместно с А.А Боровковым). brgotUc and a lability theorems for the stac.hastical.l у recurrent sequences.// Proceedings of 18-th European Meeting of Statia ticiar.s. -Berlin, 1 S&S. -P.1B.

11.(Совместно с A.А.Соровковнм). Stochastically recursive sequences and their generalizations.// Siberian Advances in Mathematics. -1992. -Y.2,11.1 .-P. 16-81

12. The ergodic theorer for a c.1 ass of queueing- systems.// 1-й Всеми])ннй конгресс общ-ва матем. статистшси и теор. вероятностей им Я.Бернулли, тез.докладов.-1986.-Т.2.-С.545.

/