Определение и динамика цепи Маркова

Рассмотрим систему å, находящуюся в каждый из дискретных моментов  в одном из  состояний .

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

.     (1.1)

 

Каждый элемент матрицы  определяет вероятность того, что если å в момент  находилось в состоянии , то в момент  она окажется в состоянии :

                                          (1.2)

Причем (и это основное свойство марковских процессов) вероятность перехода из  в  не зависит от предыдущих состояний.

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

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

                                                          (1.3)

где  выступают в роли условных вероятностей перехода в состояние  при условии, что система находится в состоянии .

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

.                                                             (1.4)

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

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

,

,

…·

,                                                                   (1.5)

где  - k -я степень матрицы P.

Нетрудно убедиться, что сумма вероятностей нахождения системы во всех состояниях (т.е. сумма элементов вектора ) на каждом шаге остается равной единице.

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

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

Рассмотрим классификацию состояний цепи Маркова. Множество всех состояний может быть разбито на непересекающиеся подмножества, или классы: невозвратные и эргодические. Их свойства определяются следующим образом. Если процесс покинул класс состояний первого типа, он никогда в него не возвращается. Если процесс попал в класс состояний второго типа, то он никогда его не покидает. Невозвратное множество мы будем обозначать , а эргодическое - . При этом , . Если эргодическое множество содержит только одно состояние, то это состояние называется поглощающим. Для такого состояния  элемент переходной матрицы  должен быть равен 1, следовательно, все остальные элементы соответствующей строки равны 0. Цепь, все эргодические состояния которой являются поглощающими, называется поглощающей цепью.

Для цепи Маркова с  состояниями, в которой имеются как невозвратные, так и эргодические множества, структура матрицы вероятностей переходов (возможно, после перенумерации состояний) имеет канонический вид

                                                           (1.6)

где  - количество состояний в невозвратном множестве;

 - количество состояний в эргодическом множестве.

Матрица Q размерности  определяет поведение процесса до выхода из множества невозвратных состояний.

Матрица R размерности  определяет вероятности перехода из множества невозвратных состояний в эргодическое множество.

Матрица  размерности  определяет динамику эргодических состояний.

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

При возведении матрицы P в степень перемножаются блоки, указанные в (1.9), и произвольная степень канонической матрицы имеет вид

                                                                   (1.7)

 

1.1.2 Оценка длительности пребывания процесса
в множестве невозвратных состояний

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

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

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

- вычисление математического ожидания величин , т.е.  и средних значений трудоемкости процесса;

- вычисление дисперсий , т.е.  и среднеквадратичных отклонений трудоемкости процесса.

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

Для дальнейшего нам понадобится формула, оценивающая матрицу . Рассмотрим тождество

Поскольку при , то .

Матрица  неособенная, т.к. , в чем легко убедиться.

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

.                                                             (1.8)

Перейдем теперь к оценке среднего «время жизни» состояний процесса, относящихся к невозвратному множеству.

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

Можно показать, что матрица математических ожиданий чисел  равна N, т.е. , где .                                                            (1.9)

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

, если , в противном случае.

Вероятность того, что , обозначим .

Легко видеть, что .

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

Здесь - элемент , .

Таким образом, среднее число шагов, которое проводит процесс в невозвратном состоянии, , начавшись в , всегда конечно и определяется i -й строкой матрицы .

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

,                                                                          (1.10)

где I – единичная матрица.

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

Зная , можно вычислить среднюю трудоемкость процесса по формуле

,                                                                     (1.11)

где -  трудоемкость j – го шага процесса в соответствующих единицах.

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

,                                                            (1.12)

где индексы   и   обозначают соответственно выделение диагональных элементов матрицы  и возведение в квадрат каждого элемента этой матрицы.