1.6.2 Метод вложенных цепей Маркова в приложении для системы GIM1

Кратко опишем применение метода вложенных цепей Маркова для анализа системы GIM1 - у которой рекуррентным является входящий поток, а показательное распределение имеет время обслуживания запроса. Пусть A(t) - функция распределения интервалов между моментами поступления запросов, - ее преобразование Лапласа - Стилтьеса, а - интенсивность потока. Интенсивность показательно распределенного времени обслуживания будем обозначать

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

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

Формула (1.55) получается из следующих соображений. Поскольку то между вложенными моментами постоянно шло обслуживание запросов и число обслужившихся за это время запросов равно Так как время обслуживания имеет показательное распределение с параметром то поток моментов окончания обслуживания является простейшим (см. Утверждение 2), поэтому (см. Утверждение 1) вероятность того, что за время t будет обслужено запросов есть:

Усредняя по всевозможным значениям длины интервала между моментами поступления, получаем формулу (1.55). Формула (1.56) следует из условия нормировки.

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

будет уже известное нам условие

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

Уравнения равновесия для стационарных вероятностей распределения вложенной цепи с учетом (1.55)-(1.57) выписываются в виде:

Решение системы линейных алгебраических уравнений (1.59) будем искать в виде:

Подставляя (1.60) в (1.59), получаем, что неизвестное число а удовлетворяет уравнению:

Покажем, что при выполнении условия (1.58) уравнение (1.61) имеет единственный действительный корень .

Обозначим . Нам необходимо убедиться, что уравнение у имеет единственный действительный корень . Для этого исследуем свойства функции :

Последнее неравенство справедливо в силу свойства 7 преобразования Лапласа - Стилтьеса.

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

Неизвестная константа С в (1.60) легко находится из условия нормировки: и имеет вид:

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

где константа а является корнем уравнения (1.61).

Найдем теперь стационарные вероятности наличия запросов в системе в произвольный момент времени. Фиксируем произвольный момент времени. В данный момент в системе может находиться запросов, если в последний перед этим моментом момент поступления запроса в системе было запросов и за время и, прошедшее с момента поступления, запросов ушли из системы, закончив обслуживание. Учитывая, что время и имеет функцию распределения (см. раздел 2), заключаем, что:

Подставляя в это соотношение вероятности в виде (1-62) и суммируя, получаем:

откуда, учитывая связь преобразований Лапласа и Лапласа - Стилтьеса и уравнение (1.61), получаем:

Вероятность находим из условия нормировки в виде:

Средние число L запросов в системе и число запросов в очереди в произвольный момент времени находятся как:

Найдем теперь стационарное распределение W(x) времени ожидания произвольного запроса в системе. Запрос, заставший систему пустой (вероятность этого есть ), имеет нулевое время ожидания. Поскольку сумма независимых показательных случайных величин с параматром есть эрланговская случайная величина порядка , то запрос, заставший в системе запросов, ждет в течение времени, распределенного по закону Эрланга с параметрами Отсюда получаем:

(1.67)

Среднее время W ожидания равно Сравнивая это выражение с (1.66), видим, что формула Литтла справедлива и для данной СМО.