Главная > Разное > Работы по математической теории массового обслуживания
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

ПОТОКИ СЛУЧАЙНЫХ СОБЫТИЙ БЕЗ ПОСЛЕДЕЙСТВИЯ

§ 1. Постановка задачи

Поток однородных случайных событий представляет собой случайный процесс в котором функция (число событий, наступающих в промежутке времени неубывающая и способна принимать лишь целые неотрицательные значения. Полное стохастическое описание такого потока мы получаем, задавая для любого натурального числа и для любой группы из моментов времени закон распределения вектора Вместо этого можно, очевидно, задать и закон распределения вектора

Поток событий называется стационарным, если закон распределения вектора — зависит только от чисел но не зависит от а (и, следовательно, при любом а 0 совпадает с законом распределения вышеприведенного вектора Поток называется потоком без последействия, если для любой системы попарно не пересекающихся промежутков времени разности представляют собой взаимно независимые случайные величины. Если целое) означает вероятность равенства (т. е. вероятность того, что в течение промежутка наступит событий данного потока), то поток без последействия, очевидно, полностью описывается заданием системы функций

так как тем самым задается распределение разности для любого промежутка Если данный поток к тому же стационарный, то величина зависит только от и может быть обозначена через наступления событий в произвольном промежутке длины

Если к требованиям стационарности и отсутствия последействия добавить еще условие

то, как известно ([1], глава 1),

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

Недавно Редхеффером [2] и автором ([1], § 8) найдена общая форма стационарных потоков без последействия без дополнительного требования . С другой стороны, уже давно известна форма потока без последействия, удовлетворяющего требованию (1), но, вообще говоря, нестационарного.

За последнее время, с одной стороны, обнаружилось, что для приложений имеет значение исследование потоков без последействия весьма общего вида. С другой стороны, удалось найти методы, сделавшие возможным исследования такого рода для некоторых специальных задач (см., например, рассмотрение известной задачи Эрланга у Пальма [3] или у автора [1], § 24; см. также работу Такача [4] о дробовом эффекте). Поэтому естественно встает вопрос об общей форме потоков без последействия. Настоящая работа имеет целью дать ответ на этот вопрос; полученное решение задачи можно признать удовлетворительным, так как все элементы произвола искомой структуры выявлены в нем с исчерпывающей ясностью.

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

Если любая неотрицательная, конечная, неубывающая функция от то формулы

всегда определяют некоторый поток без последействия, ведущая функция которого совпадает с Имеиио этот поток обычно и рассматривают, когда исходят от ведущей функции Однако такое ограничение, вообще говоря, представляется необоснованным. Как мы увидим, потоки типа (2) образуют лишь частный случай финитных потоков без последействия, так что, ограничиваясь потоками типа (2), мы подменили бы общее исследование проблемы рассмотрением частных случаев. Правда, потоки типа (2) обрлзуют собою, как мы увидим, в известном смысле фундамент всей совокупности финитных потоков без последействия; но это как раз и надо показать с полной ясностью для того, чтобы специальное исследование потоков типа (2) получило хотя бы временное обоснование.

§ 2. Леммы о финитных потоках

Для решения поставленной задачи понадобится ряд элементарных и по большей части легко доказуемых вспомогательных предложений. Многие из этих лемм не связаны с отсутствием последействия и имеют силу для всех финитных потоков; такими леммами мы и займемся в настоящем параграфе; во всех последующих предложениях этого параграфа данный поток предполагается финитным, а во всем остальном — произвольным.

Лемма 1. При всегда

Доказательство. Очевидно, разность есть вероятность того, что в промежутке наступит более событий данного потока. Поэтому на основании неравенства Чебышева

и, следовательно,

Лемма 2. При и 0 существует предел

Доказательство. Положим для

Так как есть вероятность того, что в промежутке наступит по меньшей мере событий, величина при положительном и убывающем не может возрастать. Поэтому всегда существует

В силу соотношения существует и предел (3), ч. т. д.

Условимся называть точку (момент времени) регулярной или сингулярной точкой данного финитного потока, смотря по тому, будет ли или

Лемма 3. Все точки непрерывности функции регулярные, а все ее точки разрыва — сингулярные точки данного потока.

Доказательство. Так как

то в случае мы имеем

что доказывает первое утверждение леммы 3.

Далее, при любом целом

Пусть задано произвольно. Закрепим сначала некоторое и выберем число столь большим, чтобы было

тогда и подавно при

и, следовательно,

Но здесь

Если (т. е. регулярная точка потока), то

поэтому при достаточно малом

и неравенство (4) дает при достаточно малом

следовательно, и второе утверждение леммы 3 также доказано.

Лемма 4. Финитный поток может иметь не более счетного множества сингулярных точек.

Доказательство непосредственно вытекает из леммы 3.

Лемма 5. Пусть финитный поток, и V — поток тех событий потока моменты наступления которых отл от некоторого фиксированного момента Тогда есть регулярная точка потока

Доказательство. Пусть Обозначим через вероятность того, что в области

наступит по меньшей мере одно событие потока Если промежуток содержит события потока то то же самое должно иметь место и для по меньшей мере одной из областей Поэтому, если обозначить вообще через вероятность наличия событий потока V в промежутке мы будем иметь

Аналогичным образом находим для любого натурального числа

Пусть теперь означает вероятность того, что в область попадет к событий потока тогда

где означает математическое ожидание числа событий потока в области Так как поток следовательно, и поток финитный, то ряд сходятся; в силу сходится поэтому и ряд . Но тогда (5) показывает, что следовательно, есть регулярная точка потока

Условимся во всем дальнейшем называть финитный поток регулярным, если он не имеет ни одной сингулярной точки, так что любое является для него регулярной точкой. Тогда из леммы 3 непосредственно следует

Лемма 6. Необходимым и достаточным условием регулярности потока служит непрерывность его ведущей функции.

Наконец, понадобится еще следующая

Лемма 7. Если и данный поток — регулярный, то равномерно в отрезке

Доказательство. В силу леммы 1

и утверждение леммы 7 вытекает из равномерной непрерывности функции в любом конечном отрезке.

§ 3. Леммы о регулярных потоках без последействия

Лемма 8. Для любого регулярного потока без последействия и любых

Доказательство. Допустим, что и положим . Так как данный поток — без последействия, то и, следовательно, либо либо Безграничное

продолжеиие этого процесса известным образом приводит нас к точке обладающей следующим свойством: при любом промежуток содержит другой промежуток для которого но тогда и подавно при любом мы имеем откуда что стоит в противоречии с регулярностью данного потока. Лемма 8 доказана.

Условимся во всем дальнейшем называть функцию

(где ряд в правой части при любых сходится по меньшей мере для производящей функцией данного потока. Если этот поток — регулярный и без последействия, то по лемме следовательно, разложение

функции по степеням сходится в некоторой окрестности точки По известным свойствам производящих функций мы имеем для потоков без последействия при

и, следовательно,

что в свою очередь имеет следствием

Поэтому, если положить то и мы получаем в некоторой окрестности точки разложение

Для установления общего вида регулярного потока без последействия имеют существенное значение свойства функций изучению этих свойств и будет посвящен конец настоящего параграфа.

Лемма 9. При и достаточно малом

здесь положено коэффициенты зависят только от индексов (и не зависят от суммирование распространяется на все системы индексов подчиненные условиям

Соотношение (8) представляет собою элементарную формулу дифференциального исчисления, имеющую место для любой -кратно дифференцируемой функции Доказательство автоматически проводится индукцией по формула (8) тривиальна] и может быть предоставлено читателю.

Лемма 10. Пусть и данный поток — регулярный и без последействия. Пусть Тогда в формуле (7)

Предварительное замечание. В силу леммы 8 в правой части (9) все знаменатели отличны от нуля.

Доказательство. Входе последующего рассуждения мы под всегда будем понимать значение производной при

Так как в силу (7)

то соотношение (8) при дает

Так как, очевидно, то отсюда

где область суммирования определяется соотношениями

а коэффициенты подобно прежним не зависят от Если мы разобьем промежуток на промежутков как это описано в формулировке леммы 10, то соотношение (10) имеет место для всех промежутков и притом с одними и теми же коэффициентами Написав все эти соотношения и складывая их почленно, мы получаем

Чтобы доказать лемму надо только установить, что при второе слагаемое правой части формулы (11) становится бесконечно малым. Это же в свою очередь будет доказано, если мы убедимся, что для любой фиксированной, принадлежащей области суммирования системы индексов величина

стремится к нулю при

С этой целью заметим прежде всего, что при область суммирования

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

Обратимся теперь к исследованию величины . В силу леммы 7 при любом и достаточно малом

и, следовательно,

Но при мы имеем

и следовательно,

в то время как при это отношение равно 1. Но в силу условий среди индексов найдется по крайней мере два положительных.

Пусть, например, такими будут индексы Тогда приведенные выше оценки дают

Так то мы можем принять, что лемма 10 уже доказана с вместо поэтому последняя сумма при имеет пределом . А так как достаточно малом может быть выбрано сколь угодно малым, то при чем лемма 10 и доказана.

Лемма 11. При есть неубывающая функция от ряд

сходится при любых для всех

Доказательство. Первое утверждение непосредственно вытекает из леммы 10, в силу которой Далее, из леммы 10 следует при любом

[последнее равенство вытекает из того, что в силу леммы при стремится к 1 равномерно относительно Так как правая часть этого равенства не зависит от то доказано и второе утверждение леммы. Наконец, из этого второго утверждения следует, что формула (7) имеет место при . В частности, при это дает

чем доказано и третье утверждение леммы 11.

Лемма 12. Каждая функция всюду непрерывна.

Доказательство. Допустим, что для некоторого и некоторого

Так как все функции неубывающие, то тогда

Но

Поэтому при достаточно малом

или

где -положительная постоянная. А отсюда следует, что

что противоречит допущению о регулярности данного потока. Этим лемма 12 доказана.

§ 4. Общая форма регулярных потоков без последействия

Леммы § 3 в своей совокупности показывают, что производящая функция любого регулярного потока без последействия имеет вид

где функции обладают следующими свойствами:

1° Все функции всюду непрерывны.

2° При любом функция монотонна (неубывающая при и невозрастающая при

3° Ряд сходится при любом

4° Сумма при любом

Теперь мы докажем обратное предложение: если есть функция вида (12), где функции удовлетворяют требованиям то существует регулярный поток без последействия, производящая функция которого совпадает с функцией

Так как в силу свойства 2° разность и неотрицательна, то, как известно, существует поток без последействия для которого

Р) означает вероятность того, что в промежутке наступит событий потока требуемое для этого условие, чтобы при всего было

легко проверяется непосредственным подсчетом. Производящая функция потока равна

Рассмотрим теперь суперпозицию определенных иами потоков которые будем предполагать взаимно независимыми. Легко убедиться, что производящая функция потока (который, очевидно, есть поток без последействия) совпадает с

В самом деле, если положить

(этим соотношением определяется число то, очевидно, для любого

где суммирование распространяется на область

Но в силу взаимной независимости потоков сумма в правой части (13), очевидно, равна вероятности того, что

в промежутке наступит событий суммарного потока . В силу (13), число совпадает с этой вероятностью, а это и значит, что есть производящая функция потока

Но в силу свойства 4° мы имеем

Этим показано, что данная функция действительно есть производящая функция некоторого потока без последействия Нам остается только убедиться, что построенный нами поток регулярный.

В силу свойства 3° для любых и 0 найдется такое что

Так как поток имеет непрерывную (в силу свойства 1°) ведущую функцию то он регулярен в силу леммы 6. Следовательно, для любой фиксированной точки при достаточно малом и при

Но при

[так как есть ведущая функция потока Из (15) и (14) следует поэтому при

Поэтому для суммарного потока мы получаем при

есть вероятность того, что в промежутке наступит по меньшей мере одно событие потока Но это означает, что у — регулярная точка потока а так как выбор этой точки произволен, то поток -регулярный,

Мы можем, таким образом, сформулировать результаты §§ 3 и 4 в виде следующего предложения.

Теорема Каждый регулярный поток без последействия имеет производящую функцию вида (12), где функции удовлетворяют требованиям обратно, каждая такая функция есть производящая функция некоторого регулярного потока без последействия.

Посмотрим теперь еще, какой вид принимает общая форма (12) для некоторых известных классов потоков без последействия.

1. Пусть данный поток при любом а 0 удовлетворяет требованию

и пусть при любом существует предел

Тогда формула (9) леммы 10 легко дает

откуда в силу свойства 4°

и формула (12) получает вид

Это — давно известный результат (см. [1], стр. 17, или [6], стр. 183).

2. Пусть данный поток — стационарный; положим

тогда формула (9) леммы 10 дает при любом

и формула (12) получает вид

Это полиостью совпадает с формулой (8.6) ([11, стр. 31) и является известным результатом Peдxeффepa [2] и автора.

§ 5. Общая форма финитных потоков без последействия

До сих пор мы рассматривали только регулярные потоки, т. е. такие, ведущая функция которых всюду непрерывна. Теперь мы обратимся к рассмотрению любого финитного потока без последействия, так что функция всюду

конечна, но может быть как угодно разрывной. Как мы знаем из § 2, точки разрыва функция это сингулярные точки данного потока.

Условимся теперь называть поток сингулярным, если обладает следующими тремя свойствами:

1) События потока могут наступать лишь в некоторые заранее определенные моменты времени; эти моменты, которые мы будем называть ступенями потока образуют не более чем счетное множество.

2) Числа событий, падающих на различные ступени, представляют собою взаимно независимые случайные величины.

3) Пусть означает вероятность того, что на ступень придется событий; тогда при любом

Свойство 2) выражает собой отсутствие последействия, а свойство -финитность потока Очевидно, сингулярный поток однозначно определяется заданием чисел и Структура такого потока представляется поэтому совершенно прозрачной: выбор чисел подчинен только требованиям в остальном же остается произвольным.

Пусть теперь дай произвольный финитный поток К без последействия. Обозначим через сингулярные точки этого потока, занумерованные в произвольном порядке. Мы будем рассматривать поток К как суперпозицию двух потоков Будем считать некоторое событие потока К принадлежащим потоку если оно наступает в один из моментов в противном случае мы будем считать его принадлежащим потоку Можно убедиться (чего мы здесь делать не будем), что оба потока без последействия, и что они взаимно независимы (ср. работу Марчевского [5]).

Докажем в первую очередь регулярность потока Пусть означает совокупность событий потока К, моменты наступления которых отличны от . В силу леммы 5 точка является регулярной для потока а значит и

подавно — для потока Но точка отличная от всех по самому определению чисел регулярна для потока К, а значит и для Таким образом, поток не имеет сингулярных точек и, следовательно, регулярен.

Что касается потока то сингулярность его очевидна из самого определения; ступенями его служат числа Мы покажем еще, что его характеристические вероятности соответственно совпадают с определенными в § 2 числами

Пусть поток определяется как выше, и пусть означает вероятность того, что в промежутке наступит событий потока Тогда для потока К мы, очевидно, имеем при

Так как (в силу леммы 5) есть регулярная точка потока то при

Поэтому соотношение (16) при дает в пределе

Резюмируя результаты настоящего параграфа, мы приходим к следующему предложению.

Теорема II. Всякий финитный поток без последействия может рассматриваться как суперпозиция двух взаимно независимых потоков того же типа, из которых один — регулярный, а другой — сингулярный; ступенями сингулярной компоненты служат при том сингулярные точки данного потока, а характеристическими вероятностями -соответствующие числа данного потока,

Непосредствеиио очевидно, что и обратно — любая суперпозиция описанного типа представляет собою некоторый финитный поток без последействия.

Теоремы 1 и II вместе взятые дают легко обозримое описание совокупности всех финитных потоков случайных событий без последействия, что и было целью настоящего исследования.

ЛИТЕРАТУРА

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление