Глава 6. ЗАДАЧА ЭРЛАНГА ДЛЯ КОНЕЧНОГО ПУЧКА

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

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

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

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

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

1. Моментами окончания тех I разговоров, которые ведутся в момент

2. Моментами появления новых вызовов после

3. Длительностями разговоров для вызовов, упомянутых в 2.

Но легко видеть, что ни один из этих трех случайных факторов не зависит от того, что происходило до момента Для фактора 1 это вытекает из принятого нами показательного распределения длительности разговоров, при котором, как мы видели в § 17, длительность остающейся части разговора не зависит от его возраста. Для фактора 2 это следует из того, что поступающий поток вызовов — простейший и, следовательно, не обладает последействием. Наконец, для фактора 3 это очевидно само собой. Таким образом, действительно все три перечисленных фактора не зависят от «прошлого» нашей системы, т. е. от течения процесса до момента а следовательно, не зависит от прошлого и течение процесса после момента ибо оно однозначно определяется указанными тремя факторами.

Таким образом, случайный процесс обладает следующим свойством: если известно то течение процесса после момента в вероятностном смысле независимо от его течения до момента (коротко: если известно настоящее, то будущее не зависит от прошедшего). Случайные процессы, обладающие этим свойством, называют процессами Маркова.

Если в некоторый момент занято линий пучка [т. е. ], то мы будем говорить, что в этот момент система находится в «состоянии всего, таким образом, для системы возможно различных состояний. Обозначим через условную вероятность того, что система, находившаяся в некоторый момент в состоянии по истечении единиц времени перейдет в состояние [вероятность при условии ]. Эти «переходные» вероятности играют основную роль исследовании процессов Маркова. Очевидно, всегда

Если то имеет место соотношение

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

этого перехода, благодаря чему и имеет место формула (18.1).

Формула (18.1), иногда называемая уравнением Чэнмана — Колмогорова, лежит в основании всех исследований о процессах Маркова; в нашем изложении она также будет играть значительную роль.

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

эта вероятность зависит как от так и от начальных данных

Если в уравнении (18.1) помножить обе части на и просуммировать по от 0 до , то в силу (18.2) мы получим

Задача Эрланга, которой мы посвятим настоящую главу состоит в отыскании вероятности застать систему в том ином данном состоянии. В свете изложенного нами выше такая постановка вопроса требует пояснений; случайный процесс нестационарен, вероятности

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

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

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

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

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

Доказательство. Оба утверждения леммы почти очевидны в силу (18.2).

1. Пусть где не зависит от начальных данных; выбирая тогда мы в силу (18.2) имеем следовательно,

2. Пусть, обратно, тогда в силу (18.2) при любом выборе

вероятностей мы имеем

так как

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