8. Полумарковские процессы

Полумарковские процессы широко используются в теории надежности и теории массового обслуживания [6, 25, 27,28, 146]. Они объединяют теорию цепей Маркова, разрывных марковских процессов и теорию восстановления (см. § 31). Приведем сначала определение полумарковского процесса.

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

Рис 8.1. Иллюстрация поведения полумарковского процесса.

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

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

Из приведенного определения следует, что если игнорировать случайный характер времени ожидания и интересоваться только моментами перехода, то процесс будет представлять собой однородную цепь Маркова (в литературе ее часто называют вложенной цепью Маркова, а в общем случае — вложенным марковским процессом). Однако при учете пребывания процесса в разных состояниях в течение случайного отрезка времени процесс не будет удовлетворять уравнению Маркова (если не все времена ожидания распределены экспоненциально). Следовательно, процесс является марковским только в моменты перехода. Сказанное оправдывает название «полумарковский процесс» или «полумарковская цепь».

При заданном начальном состоянии дальнейшее поведение полумарковского процесса (полумарковской цепи) полностью определяется матрицей вероятностей перехода и матрицей функций распределения или (для непрерывных случайных неличин матрицей плотностей вероятностей

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

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

(8.2)

Среднее значение безусловного времени ожидания в состоянии равно

Для дальнейшего введем следующее обозначение

Перейдем теперь к решению основной задачи, возникающей при анализе полумарковских процессов, - вычислению вероятностей состояний.

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

где — символ Кронекера: при и при .

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

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

Применяя преобразование Лапласа к уравнению (5), получаем

Из (4) имеем

Полученная система алгебраических уравнений связывает преобразование Лапласа от интервально-переходных вероятностей с основными характеристиками процесса.

Чтобы воспользоваться известными результатами матричного исчисления, запишем систему уравнений (7) в матричном виде. Для этого введем матрицы , а также диагональные матрицы . Для учета специфического вида суммирования в (7) определим специальный вид умножения матриц, обозначив эту операцию символом . Если А, В и С — квадратные матрицы размерности , то означает, что . Другими словами, операция обозначает лишь умножение элементов матриц [29].

Теперь уравнение (7) можно записать в следующем виде:

или

где — единичная матрица. Предполагается, что обратная матрица в (10) существует.

Из уравнения (10) следует, что интервально-переходные вероятности зависят только от произведения и , а не от каждого из сомножителей в отдельности. Уравнение (10) определяет интервально-переходные вероятности через основные характеристики полумарковского процесса, которые считаются заданными. Решение этого уравнения позволяет исследовать как режим установления, так и стационарное состояние. Если же интересоваться только стационарным состоянием, то в уравнении (10) возможны упрощения.

В теории преобразований Лапласа хорошо известен следующий асимптотический результат:

если существует хотя бы один из этих пределов.

На основании (10) можем написать

Рассмотрим каждый из пределов в правой части (12) отдельно.

На основании (8) можем написать

где — единичная матрица. Учитывая условие нормировки плотностей вероятностей , нетрудно убедиться, что . Поэтому значение предела в правой части равенства (13) оказывается неопределенным. Применяя правило Лопиталя для раскрытия неопределенности, находим

Здесь — диагональная матрица размерности средних безусловных времен ожидания в каждом из состояний (3).

Найдем теперь предел первого сомножителя в правой части (12). Обозначив

можем написать

Из условия нормировки плотностей вероятностей следует, что

Поэтому при все элементы матрицы равны единице. С учетом определенной выше операции перемножения матриц из (15) получаем

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

Учитывая предположенную единственность решения этой системы уравнений и сравнивая (16) с (17) или (2.34), можно прийти к заключению, что в качестве решения матричного уравнения (15) можно взять квадратную матрицу размерности , строка которой пропорциональна матрице-строке финальных вероятностей , т. е.

где — некоторый коэффициент пропорциональности.

Следовательно, для стационарного состояния уравнение (12) принимает вид

(8.18)

Отсюда следует, что элементы матрицы Ф должны удовлетворять соотношению

Для определения коэффициентов воспользуемся условием, что сумма финальных интервально-переходных вероятностей должна равняться единице:

Поэтому

Коэффициенты пропорциональности оказываются одинаковыми для всех состояний.

На основании (19) и (21) можем написать

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

Укажем, что, кроме рассмотренной задачи, для полумарковских процессов, как и для цепей Маркова (см., например, § 4) могут быть сформулированы и решены другие задачи [29]. Приведем здесь две из таких задач.

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

Пусть — номер состояния, которое система занимает в момент времени — время, когда произошел переход. Тогда нужно знать условную вероятность

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

Очевидно, что

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

поскольку есть безусловная вероятность времени ожидания .

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

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

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

Если система стартовала из состояния , то вероятность оказаться ей в состоянии после переходов за время определяется вероятностью того, что система достигает состояния в первый раз после переходов за время i и затем возвращается в состояние за переходов в течение времени , причем необходимо взять сумму по всем значениям от 1 до и проинтегрировать по всем значениям от 0 до . При справедливо равенство

так как невозможно переместиться из состояния в состояние , не совершая переходов.

Уравнение (28) можно записать в следующем виде:

Для решения уравнений (26) и (30) можно применять разные методы, в том числе и метод преобразований Лапласа.

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

Пример I. Цепь Маркова. Пусть полумарковский процесс с дискретным временем задан матрицей одношаговых вероятностей перехода и времена ожидания в каждом состоянии одинаковы и равны единице, т. е.

В данном случае

Согласно (10) имеем

или

где

В теории матриц доказывается [143], что справедливо соотношение

Поэтому

Из обратного преобразования Лапласа получаем

На основании этих выражений находим матрицу интервально-переходных вероятностей

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

Пример 2. Дискретный марковский процесс. Пусть полумарковский процесс с непрерывным временем имеет заданную матрицу вероятностей перехода и одинаковые экспоненциально-распределенные времена ожидания во всех состояниях (со средним значением ):

В рассматриваемом примере

Теперь записываем основное уравнение (10)

Так как матрица не зависит от s, то можем записать

Отсюда получаем обратное преобразование Лапласа

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

Пример 3. Альтернирующий процесс восстановления (см. с. 427). Пусть система имеет только два состояния и , причем матрица вероятносгей перехода имеет простой вид

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

В частном случае, когда , приведенное выражение принимает вид

Из обратного преобразования Лапласа легко находится интересующая нас матрица интервально-переходных вероятностей

Отсюда при имеем

что, как и следовало ожидать, совпадает с . При получим

Этот результат находится в согласии с формулой (22).