Содержание к диссертации
Введение
ГЛАВА 1. Предельные теоремы для дискретных характеристик модели M|G|l|oo при фиксированных загрузках
1.1. Основное уравнение 13
1.2. Асимптотический анализ 18
1.3. Информация об устойчивых законах 26
1.4. Сходимость к устойчивым законам 36
1.5. Свойства траекторий 38
1.6. Представления для времен ожидания 49
ГЛАВА 2. Предельные теоремы для непрерывных характеристик модели M|G|l|oo при фиксированных загрузках
2.1. Основное уравнение 55
2.2. Асимптотический анализ 58
2.3. Сходимость к устойчивым законам 67
2.4. Усиленный закон больших чисел 78
2.5. Представления для времен ожидания 79
2.6. Основные формулы для стационарных времен ожидания 85
ГЛАВА 3. Предельные теоремы в модели M|G|1 |оо в условиях критической загрузки
3.1. Одномерные и многомерные интегральные представления для виртуальных времён ожидания 92
3.2. Предельные теоремы для времён ожидания при критической загрузке 94
3.3. Представления на языке медленно меняющихся функций 101
Литература 104
- Асимптотический анализ
- Свойства траекторий
- Сходимость к устойчивым законам
- Основные формулы для стационарных времен ожидания
Введение к работе
Модели массового обслуживания образуют специальный класс математических моделей, описывающих поведение огромного множества разнообразных сложных систем. Их теоретический анализ необходим на этапе проектирования таких сложных систем, как информационные сети, в частности, интернет-сети, автоматизированные вычислительные системы, системы снабжения, транспортные комплексы, медицинское обслуживание и т.д.
Модели массового обслуживания возникают всюду, где мы имеем дело с клиентами, требованиями, вызовами, которые выстраиваются в очередь с целью приобретения услуг (получения обслуживания) в пунктах, узлах, их предоставляющих. Обслуживанием очередей занимаются так называемые приборы, осуществляющие последовательную "массовую" обработку (обслуживание) вызовов при учете влияния сопутствующих случайных факторов.
Известный специалист по вычислительным системам Л. Клейнрок определяет модели массового обслуживания (очередей) как широкий класс систем, в которых клиенты конкурируют друг с другом за доступ к ограниченным ресурсам. По его мнению " применение теории очередей (теории массового обслуживания) для анализа распределения ресурсов и решения задач о потоках данных в вычислительных системах является, по-видимому, единственным, доступным специалистам по вычислительной технике методом, позволяющим понять сложные связи в таких системах" [14].
По своей сути, практические задачи, приводящие к моделям массового обслуживания, являются оптимизационными. Особенно отчетливо эта особенность проявилась на этапе первичного развития теории, на который большое влияние оказал известный датский ученый А.К. Эрланг (1878-1929) -многолетний сотрудник Копенгагенской телефонной компании.
Функционирование телефонной станции того времени привело к возникновению следующей практической задачи. На телефонную станцию с конечным числом свободных линий (приборов) приходят клиенты (поступают вызовы). Если в момент прихода клиента находится свободная линия, то происходит подключение и начинается разговор (происходит обслуживание вызова). В противном случае клиенту приходится ждать освобождения линий (вызов становится в очередь и ждет освобождения прибора).
В связи с конкуренцией с другими телефонными станциями, слишком долгое ожидание начала обслуживания может заставить клиента обратиться к услугам другой телефонной станции.
С одной стороны, телефонная компания заинтересована в уменьшении числа телефонных линий, требующих на свое приобретение, содержание и эксплуатацию определенных затрат. С другой стороны, уменьшение числа телефонных линий может привести к потенциальным потерям клиентов, что отражается на доходах телефонной компании.
Возникает задача расчета оптимального числа телефонных линий на станции на основе статистически выверенного критерия потерь.
С рассматриваемой точки зрения теория массового обслуживания включается в широкое направление исследований - исследование операций.
При удовлетворении критериям потерь, при которых клиент предпочитает остаться в очереди и ждать начала обслуживания, мы имеем дело с моделями массового обслуживания с ожиданием.
Далее, учет влияния случайных факторов при изучении практических задач, приводящих к моделям массового обслуживания, обуславливает применение методов теории вероятностей для решения этих задач, относит модели массового обслуживания к стохастическим моделям - специальному разделу теории вероятностей.
Исключительная роль теории вероятностей при анализе моделей массового обслуживания, в сравнении с некоторыми другими разделами исследования операций (теория игр, теория информации и кодирования и т.д.), вызвана многими обстоятельствами.
В моделях массового обслуживания прежде, чем дойти до возможности непосредственного решения оптимизационной задачи, следует пройти несколько этапов.
Оптимизационные задачи здесь, как правило, формируются в условиях стационарного режима работы модели. Они заключаются в минимизации так называемых критериев потерь либо в широких классах дисциплин обслуживания (правил выбора вызовов из очереди на обслуживание), либо по типу обслуживания (вида функции распределения времен обслуживания) и т.д.
Сами критерии потерь записываются в терминах основных характеристик модели (времен ожидания, длин очередей, простоев приборов и т.д.).
Таким образом, решение оптимизационной задачи в моделях массового обслуживания предполагает предварительное получение, по крайней мере:
1. Условий существования стационарных характеристик;
2. Расчетных формул для нестационарных характеристик;
3. Расчетных формул для стационарных характеристик из формул для соответствующих нестационарных характеристик при неограниченном росте времени (дискретного или непрерывного).
Теория массового обслуживания за короткий промежуток времени из области исследований инженерных задач телефонной связи превратилась в широкое инженерно-математическое направление с применениями в разных сферах человеческой деятельности. Вплоть до 50-х годов под единым названием «теория массового обслуживания» публиковались много статей, изучающих по сути дела задачи массового обслуживания, но разнообразные по терминологии и сферам применения.
Возникла необходимость четко осознать предмет теории массового обслуживания, создать её терминологию, освободиться от многочисленных дублирований исследований в дальнейшем.
С выходом в свет монографий Б.В.Гнеденко и И.Н.Коваленко [6], Дж.Коэна [36] окончательно оформилась теория массового обслуживания на математическую теорию и инженерную теорию телетрафика.
У многих исследователей возникло естественное желание ограничить предмет математической теории массового обслуживания сравнительно простыми по структуре, но тем не менее достаточно общими моделями, для которых возможно подобрать единый математический аппарат их исследования. Примерами такого подхода служат работы А.А.Боровкова [1,2].
В теории массового обслуживания намечается тенденция выделения математической теории путем подбора сравнительно несложных одноканальных моделей (моделей с одним обслуживающим прибором), поддающихся исследованию известными математическими методами [7, 13, 14].
На практике часто предполагается, что входящий поток (поток поступающих в модель вызовов) является пуассоновским. Предположение о пуассоновости входящего потока не является сильным ограничением, поскольку, как показали интересные исследования Г.А.Ососкова [18] и Б.Григелиониса [8], наложение многих «малых» потоков при достаточно широких условиях приводит к суммарному пуассоновскому.
Предположение о пуассоновости входящих потоков в структурно сложных моделях массового обслуживания (приоритетные модели, динамические модели и т.д.) и сейчас, как правило, является необходимым атрибутом формализации, не вызывая протеста в среде инженеров, применяющих полученные результаты. Более того, результаты по приоритетным и динамическим моделям при таком предположении характеризуют современный уровень, выше которого затруднено понимание результатов инженерами-проектировщиками реальных систем.
Предположение пуассоновости, из-за свойства отсутствия последействия показательного закона, который служит распределением промежутка между соседними моментами поступлений вызовов в пуассоновском потоке, позволяет разработать специфические методы анализа.
В то же время использование предположения об экспоненциальном распределении длительностей обслуживания вызовов менее оправдано. Случаи экспоненциального распределения обслуживания на практике редки.
Слишком ограничительные требования одновременной показательной распределенности времен обслуживания и пуассоновости входящих потоков кардинально сужают возможность применения результатов к реальным системам. К настоящему времени данный этап развития завершен, исчерпал себя. Интерес математиков к таким задачам невелик.
Математическая теория одноканальных моделей с пуассоновским входящим потоком оформилась усилиями А.Я. Хинчина [34], Б.В. Гнеденко и И.Н. Коваленко [6], Г.П. Климова [15]. Их работы привели к систематизации результатов, относящихся к одноканальным моделям, и посвящены получению точных, неасимптотических результатов на языке преобразования Лапласа-Стилтьеса, которые во многих случаях громоздки на вид.
Объективная закономерность развития теории массового обслуживания заключается в применении асимптотического анализа. Следует отметить, что использование асимптотических методов в теории одноканальных систем оправдано: во-первых, наличием большого числа точных результатов, на базе которых асимптотический анализ приводит к качественным результатам; во-вторых, тем, что часто предельные теоремы раскрывают структурные особенности моделей; в-третьих, асимптотические результаты менее громоздкие и более удобные для применения.
В становлении асимптотических методов в теории массового обслуживания важна роль Ю.В. Прохорова [22], А.А. Боровкова [2], Э.А. Даниеляна [11].
Основополагающую роль в становлении асимптотических методов теории массового обслуживания сыграла работа Ю.В. Прохорова [22].
Дадим описание исследуемой модели.
Пусть в одноканальную систему обслуживания с ожиданием вызовы поступают в случайные моменты времени {f„}nSl, где 0 tl t2 .... Время обслуживания п-того вызова(п 1) обозначим vn и пусть un=tn— tn_x, t0 = 0.
Последовательности {ии} и {уп} неотрицательных случайных величин (СВ) определены на одном и том же вероятностном пространстве (Q,3,P). Последовательности {ип} и {vn} независимы (друг от друга) и образуют последовательности независимых одинаково распределенных (НОР) СВ с функциями распределения (ФР) A(t)=\-e at и B{t) на R+ соответственно.
Далее, предполагаем 0 а, = — = Мщ +« и 0 J3X = Mvx +оо, где М а знак математического ожидания, а также #(+0) = 0, что означает, что вероятность «мгновенного» обслуживания равна нулю.
По классификации Кендалла-Башарина данный класс систем обозначается MGloo.
Первый символ характеризует структуру входящего потока вызовов. Второй указывает ФР времени обслуживания. Третий означает число обслуживающих приборов. Четвертый символ говорит о том, что число мест для ожидания неограниченно.
Дисциплина обслуживания — правило выбора вызовов из очереди на обслуживание.
Дисциплина обслуживания консервативна, если при ее использовании внутри модели работа не создается и не исчезает, а лишь привносится в модель извне поступлением вызовов.
Под работой понимается длительность обслуживания.
Возникновение новой работы внутри модели возможно, например, при ненадежном восстанавливаемом приборе. Это - время, затрачиваемое на восстановление прибора.
Исчезновение работы внутри модели возможно, например, при прерывании обслуживания вызова с удалением его из модели. Остаток невыполненного обслуживания соответствует величине исчезнувшей в модели работы.
Примером консервативной дисциплины является дисциплина обслуживания в порядке поступления - FIFO (first in - first out).
В моделях MG1OO оптимальный анализ характеристик зависит от удачного выбора начальных уравнений и методов исследования, что часто приводит к пересмотру и дополнению результатов в модели MGloo. При этом возникают новые постановки. В то же время, общие закономерности поведения характеристик в модели МIG111 оо зависят от загрузки рх = af3x, где оо /3x=jtdB(t). о
Случаи Р\ \, Р\ =1, Р[ 1 дифференцируют поведение процессов при неограниченном росте времени.
Особый случай, известный в литературе под названием "критической загрузки", возникает, когда рх "близко" к единице (рх- \).
Основными характеристиками модели МІ G 11 со являются: w(t) - виртуальное время ожидания вызова в момент / (время, которое ждал бы вызов, поступая в систему в момент времени /); -к - период занятости (промежуток времени, начинающийся с поступления в свободную систему вызова и завершающийся первым после этого момента освобождением системы от вызовов); l(t) - суммарное время простоя прибора до момента t.
Дискретными аналогами этих характеристик являются: wn - время ожидания п -го вызова; в - случайное число обслуженных за период занятости вызовов; /„-суммарное время простоя прибора до поступления п -го вызова.
Важными характеристиками системы являются также п,п \ и
Qn,n \ - длина очереди в момент поступления п -го вызова; {t\ t 0 - длина очереди в момент времени t.
В работах Э.А. Даниеляна, Г.А. Попова [9, 10, 11, 20, 21, 25] и их учеников изучены основные характеристики моделей типа МIG111 оо (включая приоритетные модели) при различных загрузках в предположении J3(s)=je sxdB(x) = l-s- +a-sHl + os(l)), (В.1) о где аг 0,1 / 2.
В диссертационной работе дается асимптотический анализ основных дискретных и непрерывных характеристик MGloo без условия (В.1) и при фиксированных загрузках, а также анализ виртуального времени ожидания в условиях (В.1) и критической загрузки рх -»1.
Научная новизна: - для виртуальных времен ожидания получены одномерные и многомерные предельные теоремы в условиях обобщенной критической загрузки (т.е. загрузка близка к единице не только снизу, но и сверху);
- полностью описан класс функций распределения для виртуальных и актуальных характеристик системы МІ G 11 оо при фиксированных загрузках;
- получены скорости сходимости актуальных характеристик к стационарным характеристикам, а также скорости сходимости виртуальных характеристик к стационарным;
- изучены свойства траекторий процессов связанных с временем ожидания и суммарным временем простоя вызовов.
Использованы:
- прием введения дополнительных событий;
- анализ уравнений в терминах случайных величин, которые связывают времена ожидания и простоя с заранее заданными случайными величинами входящего потока и обслуживания вызовов;
- асимптотические методы математического анализа.
Результаты помогут разработчикам ИВС и АСУ на стадии проектирования реальных систем для оптимальной организации процессов функционирования. Вид результатов обеспечивает их практическую реализацию на ЭВМ.
Результаты могут быть использованы в решении различных задач моделирования в экономике, в социально-курортном сервисе и туризме, в производственных процессах, в транспорте и т.д.
Результаты диссертационной работы докладывались на Всероссийских симпозиумах по прикладной и промышленной математике (Йошкар-Ола, 2001; Ростов-на-Дону, 2002; Петрозаводск, 2003, Сочи, 2003).
По диссертационной работе опубликованы работы [26 - 30].
Диссертационная работа изложена на 107 страницах. Состоит из введения, трех глав и списка литературы, содержащего 40 наименований.
Во введении обоснованы актуальность темы исследования, определена цель работы, даны постановки задач и обзор литературы.
Асимптотический анализ
Уже при /7 = 2 метод неэффективен. В литературе существует много результатов по оценке скорости сходимости при 1 р 2. Обозначим аг =МХ} {МХХ)2 и пусть Ф(х)= -4=- [e du, - оо л: +00 - стандартный нормальный закон с нулевым математическим ожиданием и с единичной дисперсией. Теоремы 1.3. Пусть МХХ +оо. Тогда существуют равномерные по х пределы В теореме 1.3 используется вытекающая из теор. 20, с. 27 [3] Лемма 1.1. Пусть последовательности случайных векторов и СВ соответственно определены на одном и том же вероятностном пространстве. Если: р Лемма 1.1 сформулирована в большей общности, чем необходимо для настоящего параграфа, с целью использования в дальнейшем. Доказательство теоремы 1.3 основано на равенствах (1.1.5): на теореме 1.1 и на центральной предельной теореме (ЦПТ) для сумм НОР СВ: Поэтому, применяя ЦПТ (1.2,16) к (1,2.15) и используя лемму 1.1, выводим (1.2.13). В силу формул (1.1.11), меняя местами последовательности {ип} и {v„}, при рх 1 предельное равенство (1.2,14) следует из (1.2.13) с рх \. Возможен перенос оценок скоростей сходимости в ЦПТ из теории суммирования НОР СВ на наш случай. Из обилия имеющихся в литературе р неэффективен. В литературе существует много результатов по оценке скорости сходимости при 1 р 2. Обозначим аг =МХ} {МХХ)2 и пусть Ф(х)= -4=- [e du, - оо л: +00 - стандартный нормальный закон с нулевым математическим ожиданием и с единичной дисперсией. Теоремы 1.3. Пусть МХХ +оо. Тогда существуют равномерные по х пределы В теореме 1.3 используется вытекающая из теор. 20, с. 27 [3] Лемма 1.1. Пусть последовательности случайных векторов и СВ соответственно определены на одном и том же вероятностном пространстве. Если: р Лемма 1.1 сформулирована в большей общности, чем необходимо для настоящего параграфа, с целью использования в дальнейшем. Доказательство теоремы 1.3 основано на равенствах (1.1.5): на теореме 1.1 и на центральной предельной теореме (ЦПТ) для сумм НОР СВ: Поэтому, применяя ЦПТ (1.2,16) к (1,2.15) и используя лемму 1.1, выводим (1.2.13). В силу формул (1.1.11), меняя местами последовательности {ип} и {v„}, при рх 1 предельное равенство (1.2,14) следует из (1.2.13) с рх \. Возможен перенос оценок скоростей сходимости в ЦПТ из теории суммирования НОР СВ на наш случай. Из обилия имеющихся в литературе результатов выберем наиболее простой по форме. Обозначая через Fn(x) и Gn(x) вероятности под знаком предела в левой части (1.2.13) и (1.2.14) соответственно, можно сформулировать следующий результат (см. [3]) Вокруг определения. Не сосредоточенная в нуле ФР F устойчива, если для любого п 1 существуют константы а„ є R+ и ап є Rl такие, что
Здесь X и {Хп} -НОРСВ с ФР F, Sn =ХХ+Х2 +... + Х„, п \. Символ d указывает на совпадение ФР обеих частей случайного равенства, связанного этим символом. Тогда (см., теор. 1, гл. 6, 1, с. 199-200 [32]) необходимо Здесь є и а - масштаб и показатель устойчивой ФР F. Если в (1.3.1) я„=0, « 1,то ФР F называют строго устойчивой. Для устойчивого F{x) С показателем а Ф 1 существует константа Ъ такая, что F(x + b) строго устойчиво (теор. 2, гл. 6, 1, с. 200 - 201 [32]), причем где X, Xlt Х2 независимы и имеют ФР F(x + b). Будем говорить, что ФР F и Fx принадлежат одному типу, если найдутся константы cteR1 и aeR+ такие, что В противном случаи F и Fx принадлежат разным типам. Легко проверить, что, если F устойчиво и F, - одного типа с ним, то Fx устойчиво с тем же показателем. В (1.3.4) возник еще один параметр а устойчивого закона зультатов выберем наиболее простой по форме. Обозначая через Fn(x) и Gn(x) вероятности под знаком предела в левой части (1.2.13) и (1.2.14) соответственно, можно сформулировать следующий результат (см. [3]) Вокруг определения. Не сосредоточенная в нуле ФР F устойчива, если для любого п 1 существуют константы а„ є R+ и ап є Rl такие, что Здесь X и {Хп} -НОРСВ с ФР F, Sn =ХХ+Х2 +... + Х„, п \. Символ d указывает на совпадение ФР обеих частей случайного равенства, связанного этим символом. Тогда (см., теор. 1, гл. 6, 1, с. 199-200 [32]) необходимо Здесь є и а - масштаб и показатель устойчивой ФР F. Если в (1.3.1) я„=0, « 1,то ФР F называют строго устойчивой. Для устойчивого F{x) С показателем а Ф 1 существует константа Ъ такая, что F(x + b) строго устойчиво (теор. 2, гл. 6, 1, с. 200 - 201 [32]), причем где X, Xlt Х2 независимы и имеют ФР F(x + b). Будем говорить, что ФР F и Fx принадлежат одному типу, если найдутся константы cteR1 и aeR+ такие, что В противном случаи F и Fx принадлежат разным типам. Легко проверить, что, если F устойчиво и F, - одного типа с ним, то Fx устойчиво с тем же показателем. В (1.3.4) возник еще один параметр а устойчивого закона - сдвиг.
Свойства траекторий
В настоящем параграфе в предположении принадлежности ФР К{х), хєЯх области нормального притяжения устойчивого закона доказаны предельные теоремы сходимости к устойчивым законам для следующих характеристик модели М G111 оо: 1. {wj прир, 1; 2. {/„} прир І. Рассматривается модель М G111 оо при 0 рх +оо и рх Ф 1. С целью получения аналога предельной теоремы 1.3 в случае МК\ = -и», предполагаем существование пределов lim ха-(\-К(х))=Ср, lim ха -К(-х)= Cq, (1.4.1) где 1 а 2,С 0,/? 0,# 0, p + q = l. -37-которые в силу (1.3.21), означают, что ФР К(х) принадлежит области нормального притяжения устойчивого закона с показателем а є (1,2) и с асимметрией р = р - q є [-1, і]. Поэтому, если S„=Xl+X2+ + Xnin U где {Хп}- последовательность НОР СВ с ФР К(х), дгє Д1, то, в силу (1.3.20) и (1.3.25) справедливо предельное соотношение где устойчивый закон Fap\x) имеет показатель а є (1,2), асимметрию Р= p-q и логарифм его характеристической функции определяется формулой (1.3.26). Аналог теоремы 1.3 формулируется следующим образом. Теорема 1.4. Пусть МХХ = -но и выполнены условия (1.4.1). Тогда существуют равномерные по х пределы = «,/?МпРи А ! Доказательство основано на равенствах (1.3.26): на теореме 1.1 и на предельном равенстве (1.4.2). (1.4.4) (1.4.5) -38-Именно, пусть рх 1. По теореме 1.1, / является собственной СВ. Следовательно, / - /, Р , ... —»0 при п -» +00. (С-п)1/а Поэтому, применяя к (1.4.5) утверждение (1.4.2) и лемму 1.1, выводим (1.4.3). Далее, так как устойчивые законы непрерывны (см., 1.3. по этому поводу см. также зад. 2, гл. 6, с. 252 [32]), то сходимость в (1.4.3) равномерна по х. Пусть Рх \. Вывод (1.4.4) осуществляется стандартным способом смены местами последовательностей {ип} и {vn}, что, в силу формул (1.1.10), позволяет для получения (1.4.4) использовать аналог (1.4.3) в новой модели М G 11 оо, совпадающий с (1.4.4). В настоящем параграфе изучаются свойства траекторий последовательностей {wn} и {/„} Основное внимание уделяется УЗБЧ и законам повторного логарифма (ЗИЛ), являющемся примерами так называемых законов 0 и 1. О законах 0 и 1. Рассматривается модель М Gloo. Сохраняются обозначения, введенные ранее. На примере последовательности \Хп } НОР СВ с ФР К{х), xeR\ определенной на вероятностном пространстве (Q,3,P) сформируем два закона 0 и 1. -алгебру Зда и ее элементы (события) называют остаточными или хвостовыми. Обозначим Приведем примеры остаточных событий: событие не является остаточным. Для остаточных событий А є Зда действует следующий закон 0 и 1 Колмогорова (см., [35]):
Взаимно однозначное отображение Y = (у1,у2,...) множества {1,2,...} в себя называется конечной перестановкой, если уп = п для всех п за исключением разве лишь конечного их числа. Обозначим Пусть #(# )- борелевская о-- алгебра в Л00 и при А = {ХеВ} и BSB(RCO). Событие А = {ХеВ}, где В є B(R) называется перестановочным, если для любой конечной перестановки Y событие Y(A) совпадает с А. Для перестановочных событий А действует закон 0 и 1 Хьюитта и Сэвиджа (см., [35]): имеет место (1.5.2). В частности, событие (1.5.1) является перестановочным. Более того, события из 3=Р3И, где 3й = j{S„,Sn+l,...), являются перестановочными. Усиленный закон больших чисел - пример законов 0 и 1. Наша цель заключается в переносе УЗБЧ для {Sn } на последовательности \wn} и {/„}, которые, в отличие от первой последовательности, образуют цепи Маркова. Теорема 1.5. Доказательство. Покажем, что из (1.5.3) следует(1.5.4). Обозначим через А, В, С события, на которых где з є Q, соответственно. Так как tx - собственна СВ, справедливо (1.5.3) и для {Sn } имеет место УЗБЧ, то Выведем (1.5.3), рассматривая случаи: а) рх 1; б) рх = 1; в) рх 1 имеет конечное число положительных членов с вероятностью 1. Поэтому найдется собственная целочисленная СВ v, принимающая значения 1,2,..., такая что на событии {v «}, п 1 при всех к п выполнены соотношения w» 0, w +i = wk+Xk=- = wn+Xn +- +Xk. Тогда для каждого п и у є {v л}Г) С, где событие С определено ранее, имеем б) Пусть рх -1, т.е. Рх-ах = 0. Идея доказательства такова. Наряду с нашей моделью, рассмотрим последовательность моделей М G 1 х , в к- той, к 1 из которых: сохраняем последовательность {«„}; {v„} заменяем на ty„\ вида v =vn +„ , Здесь vn и ffl при каждом п \ независимы и „ / - последовательность положительных НОР СВ с мф = р\к) 0. Обозначим через w \ п \, к \ время ожидания п- того поступившего вызова в к - той модели. Очевидно, что w м п,п 1,к 1и любом со є Q. В силу а), Мы утверждаем, что переход к пределу к - -и» под знаком вероятности в левой части (1.5.5) допустим. Действительно, обозначим событие в левой части (1.5.5) под знаком вероятности через Ак, к \. Пусть Осталось заметить, что Р Равенства (1.5.6) - (1.5.7) доказывают утверждение. в) При р, 1 доказательство аналогично доказательству в случае а). Теорема 1.5 доказана. Законы повторного логарифма также являются примерами законов 0 и 1 Пусть {Хп}- последовательность НОР СВ с ФР К(х), х є Rl.
Сходимость к устойчивым законам
Проверяется равенство Поэтому, согласно таблице, - =. X, + 4a- j2 -Х2 имеет нормальную ФР с нулевым математическим у/а ожиданием и дисперсией а откуда и из (2.2.25) следует(2.2.18). Дальнейшее доказательство такое же, что и для теоремы 1.3. з-за непрерывности предельной ФР Ф в теоремах 1.3 и 2.3, сходимость в них равномерна по д:. Случай МХ\ = 4 » приводит к теоремам сходимости к устойчивым законам. Для их получения необходима информация об устойчивых законах, которая приводится в 1.2. В настоящем параграфе в предположении принадлежности ФР К(х), xeR1 области нормального притяжения устойчивого закона доказаны предельные теоремы сходимости к устойчивым законам для следующих характеристик модели МIG111 оо: 1. {w(t):t 0}npn р, 1; 2. {/(ґ):ґ 0}при рх \. Рассматривается модель М G111 оо при 0 рх +оо и рх Ф 1. Наша цель заключается в получении аналога теоремы 2.3 в случае Метод доказательства будет тем же, что и в теореме 2.3. Он диктует необходимость установления нескольких вспомогательных утверждений. а) Пусть {ип} и {vn}- последовательности НОР СВ с ФР А(х) = 1 - е ах и В(х), х є R+, Мих =a{= — eR+ и Mvx = рх є R+ соответственно. Обозначим семейства случайных функций, определяемых следующим образом: Ut=Un и Vt = Vn при « / « + 1,« 0- целые числа. Из (1.4.2) вытекает Следствие 2.1. Пусть выполнены В (2.3.2) знак «+» берется при t О, а «-» при t 0. Действительно, если выполнены условия (1.4.1) с С 0, р 0, q 0, p + q = \, то, как и при выводе (1.4.2), из общей теории следует непрерывности Fal (х), из (2.3.3) вытекает существование пределов (2.3.1). б) В процессе восстановления {/„} обозначим через N(t), t 0 число восстановлений за [0, t). Лемма 2.2. Пусть выполнено первое из условий (1.4.1) с С 0, qe(0, і]. Тогда (2.3.4) где логарифм характеристической функции предельного закона определяется формулой (2.3.2). Предельное равенство (2.3.4) можно вывести из более общего утверждения (см. [32], гл. 11, 5, с. 423-424), однако, интерес может представить приводимый ниже способ доказательства. Доказательство. Для любого у
О справедливы равенства Тем самым, при t - +оо одновременно у — +оо, сохраняя х О фиксированным. При фиксированном х 0 и всех t 0 рассматриваем (2.3.6) как уравнение относительно у: Нахождение решения уравнения (2.3.7) затруднительно, однако, можно ПОЛУЧИТЬ аСИМПТОТИКу решеНИЯ ПрИ t — +00 . Так как второй член левой части (2.3.7) есть о(у) (ведь при г- +оо имеем у — +оо), то из (2.3.7) при t - +оо имеем Подставляя (2.3.8) в (2.3.7), при t — +оо находим Подставляя (2.3.10) в левую часть (2.3.5) и замечая, что, в силу (2.3.1) и (2.3.6), правая часть (2.3.5) при f- +oo стремится к Fal(x), убеждаемся в справедливости (2.3.4). в) Обозначим Пусть для последовательности {„} НОР СВ с ФР G{x), xeR1 обозначено и при заданном а є (1,2) существуют пределы Доказательство . Для любых AER+ И BeR+t интегрируя по частям, выводим (во втором интеграле перед интегрированием по частям х заменено на (- JC)). Если интегралы слева сходятся при А - -и» и В -» -ко соответственно, то вклад в предельные интегралы от интегрирования по промежуткам [Л,+а ) и (-оо,-5] не меньше, чем первые слагаемые в правых частях (2.3.13) стремятся к нулю. Иначе, интегралы в правых частях (2.3.13) расходились бы. Переходя к пределу У4- +ОО И Л- +ОО, получаем (2.3.12), как сумму пределов правых частей (2.3.13). Обратно, если (2.3.13) имеет место, то интегралы в правых частях (2.3.13) сходятся. Но интегралы слева в (2.3.13) не превосходят интегралов справа, откуда следует их сходимость. Тогда у ФР F существует абсолютный момент порядка у 0. Лемма 2.3. Пусть выполнены условия (2.3.11). Тогда В частности, Мы докажем (2.3.14) непрямым методом обращения к общим фактам теории устойчивых законов. Доказательство. Известно следующее утверждение (см. [32], гл. 9, 6. следствие, с. 351): Выберем C = l, p = q = — . Из вида (2.3.11) логарифма характеристической функции выбранного устойчивого закона и симметричных устойчивых законов (см., [32], с. 638) следует, что выбранный закон является симметричным устойчивым законом. Следовательно, выбранный закон Fa 0 (с нулевым математическим ожиданием при 1 а 2 ) имеет асимметрию /3 = 0, логарифм характеристической функции удовлетворяет предельным соотношениям Пусть {Я„}- последовательность НОР СВ с симметричной устойчивой ФР Fa 0(х), XGR\HQ зависящая от {„} и следствия 1.1, ( 2.3.11) и (2.3.16) заключаем
Основные формулы для стационарных времен ожидания
Теми же аргументами, что и в доказательстве теоремы 2.6, убеждаемся в применимости теоремы восстановления Смита, откуда и из (2.5.15) находим lim P(w(t) х) (= lim и(0)= 77"JРЫу) xbr] y)dy, Формула (2.5.14) может быть представлена в более удобной форме. Следствие 2.5. В условиях теоремы 2.6 при х 0 справедливо равенство Доказательство. Согласно теореме Фуббини, математическое ожидание интеграла в правой части (2.5.14) равно следующему выражению Последнее равенство справедливо в промежутке [яг, 77) внутри первого периода регенерации прибор свободен. Поэтому ;tr(w(/) х)= 0 при х є [я-, rj). Здесь Z(w(t) x)=\-X(w(t) x). (2.5.18) -85-Подставляя выражение (2.5.17) в (2.5.14), при х 0 получаем что, будучи подставлено в (2.5.19), приводит к (2.5.16). Имея представления для стационарной ФР W (x), х 0 времен ожидания можно получить представл являющееся слабым пределом при f-»+oo процесса {w(t):t 6}. В настоящем параграфе мы покажем, что ФР W(x) и W (x)=P\w х), х 0 совпадают в модели MGloo. Возникает вопрос: какова связь между стационарными временами ожидания w и w в модели MG 1 QO? Различные связи между W [x) и W(x), хєИ+ при рх 1 в модели MGloo устанавливают формулы Такача и Хука, входящие в список основных формул. Вывод этих формул и некоторых их следствий составляют содержание настоящего параграфа. Формула Такача. Введем CB v с ФР неарифметическая ФР. Тогда имеет место формула называемая формулой Такача. В (2.6.3) CB w и v независимы. Формулу (2.6.3) можно записать с помощью свертки ФР (см. (2.6.2)): Модель MGloo при наших предположениях апериодична. Именно, пусть в момент t0 = 0 начался период занятости к и в- случайное число вызовов, обслуженных за п. Апериодичность означает, что наибольший общий делитель тех целых т 1, для которых равен 1. Здесь wп, п 1 - время ожидания п - того поступившего вызова. Ясно, что wx = О, wm 0 при т = 2,в. В нашем случае (2.6.5) имеет место с т = 1: P(v, 2 )= Р(# = і) 0. Так как в нашем случае модель MGloo апериодична и Л(х)-неарифметическая ФР, то применимы результаты 2.5и1.6.Их детальное сравнение и приводит к теореме 2.7. Доказательство. Пусть в момент t0 = 0 начался период занятости ж, где tn - момент поступления (п +1)- го вызова со временем ожидания ww+].
Имеем где TJ- период регенерации процесса {w(f): t О}. В соответствии с (2.5.5) и (1.6.10), (2.5.14) запишем равенства В дальнейшем, для любого события С полагаем: j(C) = l при осуществлении С и J (С) = 0 в противном случае. Произведем выкладки, обозначив Sn = Vn - tn, п 1, S0 = 0. Выделяя в выражении справа последнее слагаемое первой суммы, произведя замену переменной суммирования п-\ = к второй суммы и выделяя во второй сумме первое слагаемое, получаем Обозначим при фиксированном х О п = max(0,х- wn)-max(0,jc - wn - vn)= min(vw ,тах(0,х - w„)), « 1. Введем ения для моментов СВ w . Для любого р 0 справедливо равенство Действительно, из (2.5.11) получаем где использована теорема Фуббини. Вычислив внутренний интеграл, приходим к формуле (2.5.20). В списке основных формул для стационарных времен ожидания в модели MG 1 оо на первом месте стоит формула Линдли (1.1.9): при рх 1 и х где CB w, v, и независимы и имеют ФР W(x), В(х), А(Х) соответственно. Формула (2.6.1) выведена в 1.1. Напомним, что w возникает как слабый предел последовательности \wn } при п — +оо. Существует и другое стационарное время ожидания в модели MGloo. Это w , являющееся слабым пределом при f-»+oo процесса {w(t):t 6}. В настоящем параграфе мы покажем, что ФР W(x) и W (x)=P\w х), х 0 совпадают в модели MGloo. Возникает вопрос: какова связь между стационарными временами ожидания w и w в модели MG 1 QO? Различные связи между W [x) и W(x), хєИ+ при рх 1 в модели MGloo устанавливают формулы Такача и Хука, входящие в список основных формул. Вывод этих формул и некоторых их следствий составляют содержание настоящего параграфа. Формула Такача. Введем CB v с ФР неарифметическая ФР. Тогда имеет место формула называемая формулой Такача. В (2.6.3) CB w и v независимы. Формулу (2.6.3) можно записать с помощью свертки ФР (см. (2.6.2)): Модель MGloo при наших предположениях апериодична. Именно, пусть в момент t0 = 0 начался период занятости к и в- случайное число вызовов, обслуженных за п. Апериодичность означает, что наибольший общий делитель тех целых т 1, для которых равен 1. Здесь wп, п 1 - время ожидания п - того поступившего вызова. Ясно, что wx = О, wm 0 при т = 2,в. В нашем случае (2.6.5) имеет место с т = 1: P(v, 2 )= Р(# = і) 0. Так как в нашем случае модель MGloo апериодична и Л(х)-неарифметическая ФР, то применимы результаты 2.5и1.6.Их детальное сравнение и приводит к теореме 2.7. Доказательство. Пусть в момент t0 = 0 начался период занятости ж, где tn - момент поступления (п +1)- го вызова со временем ожидания ww+]. Имеем где TJ- период регенерации процесса {w(f): t О}. В соответствии с (2.5.5) и (1.6.10), (2.5.14) запишем равенства В дальнейшем, для любого события С полагаем: j(C) = l при осуществлении С и J (С) = 0 в противном случае. Произведем выкладки, обозначив Sn = Vn - tn, п 1, S0 = 0. Выделяя в выражении справа последнее слагаемое первой суммы, произведя замену переменной суммирования п-\ = к второй суммы и выделяя во второй сумме первое слагаемое, получаем Обозначим при фиксированном х О п = max(0,х- wn)-max(0,jc - wn - vn)= min(vw ,тах(0,х - w„)), « 1. Введем в рассмотрение последовательность расширяющихся а - алгебр {3„}, где 30={о,П} - тривиальная а- алгебра, а 3„, п \ порождена СВ !/,,...,!/„ и v,,...,v„. Так как событие {# я}єЗ„ при п 0, то напр., [38], гл. 2, 7). Следовательно, Так как 0 Мв + х при рх 1, то, сократив Мв в последнем равенстве и умножив обе его части на яг, приходим к формуле (2.6.3). Формула Хука. Введем СВ и и ФР
