Цепи Маркова
дата публикации: 2016-07-16

Цепи Маркова представляют собой достаточно давно известный математический аппарат для описания случайных процессов. Начнем с простого примера. Пусть имеется несколько состояний S_i, i \in (0..n). Некая сущность, которую будем далее называть системой, может изначально находиться в любом из этих состояний с вероятностями b_i (вектор вероятностей начального распределения \bf B_0), а так же перемещаться между состояниями с вероятностями p_{i,j}, j \in (0..n) (матрица переходных вероятностей \bf P), где i — начальное состояние, j — конечное состояние. Сумма вероятностей всех возможных переходов из i определяется соотношением \sum_{j=0}^n p_{i,j} = 1 , что вполне очевидно. Также понятно, что существует ненулевая вероятность остаться на текущей позиции.

Иногда цепи Маркова используются для описания процесса принятия решений, в этом случае обычно вводят несколько дополняющих модель определений, опишем основные два. Набор действий (событий) a_{i,k}, k \in (0..m_i) , который определен для каждого состояния S_i в количестве m_i+1 . При этом вероятность перехода из состояния i в состояние j зависит от конкретного действия a_{i,k} и может быть определена как p_{i,j,k}. Второе определение - стоимость перехода r_{i,j,k} , которая может быть и положительна и отрицательна. Введение понятия стоимости позволяет строить на базе цепей Маркова мультиагентные системы. Схематически систему можно представить следующим рисунком, однако далее договоримся рассматривать цепь без набора действий и стоимостей перехода.

Схема цепи Маркова

Переход из состояния в состояние осуществляется через дискретные промежутки времени, которые обозначим через h . При этом если цепь является однородной, то вероятность переходов не зависит от шага и является постоянной, то есть вероятности p_{i,j} задаются на начальном этапе и неизменны. Однако не стоит думать, что переход i \rightarrow j будет эквивалентен переходу i \rightarrow k \rightarrow j . Для оценки вероятности многоступенчатого перехода верно соотношение:

p_{i,i+m} = p_{i,i+1} \cdot p_{i+1,i+2} \cdot ... \cdot p_{i+m-1,i+m}.

Сама по себе полученная формула не настолько интересна, так как описывает только одну траекторию в m шагов. Куда интереснее рассмотреть все возможные траектории попадания в определенное состояние по схеме i \rightarrow k \rightarrow j, где k принимает любое значение из доступного множества. Для доказательства воспользуемся формулой условной вероятности (формулой Байеса). Все возможные траектории движения системы из состояния i в состояние j за два шага минуя состояние k \in (0..n) будут равны:

\begin{cases} & i \rightarrow 0 \rightarrow j \\ & i \rightarrow 1 \rightarrow j \\ & ... \\ & i \rightarrow k \rightarrow j \\ & ... \\ & i \rightarrow n \rightarrow j \end{cases}

а значит итоговая вероятность определится формулой:

p_{i,j} = \sum_{k=0}^n p_{i,k} \cdot p_{k,j}.

Данная формула называется формулой Колмогорова-Чепмена для дискретного марковского процесса и определяет алгоритм перемоножения матрицы самой на себя, что позволяет вычислить вероятности распределения системы через n шагов по следующей формуле:

\bf B_n = \bf P^n \cdot \bf B_0,

то есть вероятность нахождения системы после n переходов определяется соответствующей степенью матрицы переходов.

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

p_{i,j}(t+h) = \sum_{k=0}^n p_{i,k}(t) \cdot p_{k,j}(h).

Введем понятие интенсивности переходов через следующий предел:

\bf Q = \lim_{h \rightarrow 0 } \frac{\bf P(h) - \bf I}{h} = \frac{d \bf P}{dt},

где \bf Q — матрица интенсивностей, \bf I — единичная диагональная матрица, которая по сути описывает марковский процесс, находящийся всегда в одном и том же состоянии. Понятно, что таким образом определяется производная матрицы состояний марковского процесса. В итоговом варианте уравнение Колмогорова принимает следующий вид:

\frac{d \bf P(t)}{dt} = \bf P(t) \cdot \bf Q.

Решением системы при детерминированном начальном состоянии будет соотношение:

\bf P(t) = exp(-\bf Q \cdot t).

Итак, мы рассмотрели базовые моменты марковского процесса и построили некоторые закономерности.