Цепь Маркова

Пример цепи с двумя состояниями

Це́пь Ма́ркова — последовательность случайных событий с конечным или счётным числом исходов, где вероятность наступления каждого события зависит только от состояния, достигнутого в предыдущем событии. Характеризуется тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Названа в честь А. А. Маркова (старшего), который впервые ввёл это понятие в работе 1906 года.

Цепь Маркова с дискретным временем

Определение

Последовательность дискретных случайных величин [math]\displaystyle{ \{X_n\}_{n \geqslant 0} }[/math] называется простой цепью Маркова (с дискретным временем), если

[math]\displaystyle{ \mathbb{P}(X_{n+1} = i_{n+1} \mid X_n = i_n, X_{n-1} = i_{n-1},\ldots, X_0 = i_0) = \mathbb{P}(X_{n+1} = i_{n+1} \mid X_n = i_n) }[/math].

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

Область значений случайных величин [math]\displaystyle{ \{X_n\} }[/math] называется простра́нством состоя́ний цепи, а номер [math]\displaystyle{ n }[/math] — номером шага.

Переходная матрица и однородные цепи

Матрица [math]\displaystyle{ P{(n)} }[/math], где

[math]\displaystyle{ P_{ij}{(n)} \equiv \mathbb{P}(X_{n+1} = j \mid X_n = i) }[/math]

называется ма́трицей перехо́дных вероя́тностей на [math]\displaystyle{ n }[/math]-м шаге, а вектор [math]\displaystyle{ \mathbf{p} = (p_1,p_2,\ldots)^{\top} }[/math], где

[math]\displaystyle{ p_i \equiv \mathbb{P}(X_0 = i) }[/math]

— нача́льным распределе́нием цепи Маркова.

Очевидно, матрица переходных вероятностей является стохастической справа, то есть

[math]\displaystyle{ \sum\limits_{j} P_{ij}(n) = 1, \quad \forall n \in \mathbb{N} }[/math].

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

[math]\displaystyle{ P_{ij}{(n)} = P_{ij},\quad \forall n \in \mathbb{N} }[/math].

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

Конечномерные распределения и матрица перехода за n шагов

Из свойств условной вероятности и определения однородной цепи Маркова получаем:

[math]\displaystyle{ \mathbb{P}(X_{n} = i_{n} , \ldots, X_0 = i_0) = P_{i_{n-1},i_n} \cdots P_{i_0,i_1} P_{i_0} }[/math],

откуда вытекает специальный случай уравнения Колмогорова — Чепмена:

[math]\displaystyle{ \mathbb{P}(X_n = i_n \mid X_0 = i_0) = (P^n)_{i_0,i_n} }[/math],

то есть матрица переходных вероятностей за [math]\displaystyle{ n }[/math] шагов однородной цепи Маркова есть [math]\displaystyle{ n }[/math]-я степень матрицы переходных вероятностей за 1 шаг. Наконец,

[math]\displaystyle{ \mathbb{P}(X_n = i_n) = \left((P^T)^n \mathbf{p}\right)_{i_n} }[/math].

Типы состояний

• Возвратное состояние.
• Возвратная цепь Маркова.
• Достижимое состояние.
• Неразложимая цепь Маркова.
• Периодическое состояние.
• Периодическая цепь Маркова.
• Поглощающее состояние. Состояние [math]\displaystyle{ i }[/math] называется поглощающим, если [math]\displaystyle{ P_{i,i}=1 }[/math].
• Эргодическое состояние.

Примеры

• Ветвящийся процесс;
• Случайное блуждание;

Цепь Маркова с непрерывным временем

Определение

Семейство дискретных случайных величин [math]\displaystyle{ \{X_t\}_{t \geqslant 0} }[/math] называется цепью Маркова (с непрерывным временем), если

[math]\displaystyle{ \mathbb{P}(X_{t+h} = x_{t+h} \mid X_s = x_s,\; 0 \lt s \leqslant t ) = \mathbb{P}(X_{t+h} = x_{t+h} \mid X_t = x_t) }[/math].

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

[math]\displaystyle{ \mathbb{P}(X_{t+h} = x_{t+h} \mid X_t = x_t) = \mathbb{P}(X_{h} = x_{h} \mid X_0 = x_0) }[/math].

Матрица переходных функций и уравнение Колмогорова — Чепмена

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

[math]\displaystyle{ \mathbf{p} = (p_1,p_2,\ldots)^{\top},\; p_i = \mathbb{P}(X_0 = i),\quad i=1,2,\ldots }[/math]

и ма́трицей перехо́дных фу́нкций (переходных вероятностей)

[math]\displaystyle{ \mathbf{P}(h)=(P_{ij}(h)) = \mathbb{P}(X_h = j \mid X_0 = i) }[/math].

Матрица переходных вероятностей удовлетворяет уравнению Колмогорова — Чепмена: [math]\displaystyle{ \mathbf{P}(t+s)=\mathbf{P}(t)\mathbf{P}(s) }[/math] или

[math]\displaystyle{ P_{ij}(t+s)=\sum_k P_{ik}(t)P_{kj}(s). }[/math]

Матрица интенсивностей и дифференциальные уравнения Колмогорова

По определению матрица интенсивностей [math]\displaystyle{ \mathbf{Q}=\lim_{h \to 0}\frac{\mathbf{P}(h)-\mathbf{I}}{h} }[/math], или, что эквивалентно,

[math]\displaystyle{ \mathbf{Q}=(q_{ij})=\left(\frac{dP_{ij}(h)}{dh}\right)_{h=0} }[/math].

Из уравнения Колмогорова — Чепмена следуют два уравнения:

• Прямое уравнение Колмогорова

  [math]\displaystyle{ \frac{d \mathbf{P}(t)}{d t}=\mathbf{P}(t)\mathbf{Q}, }[/math]

• Обратное уравнение Колмогорова

  [math]\displaystyle{ \frac{d \mathbf{P}(t)}{d t}=\mathbf{Q}\mathbf{P}(t). }[/math]

Для обоих уравнений начальным условием выбирается [math]\displaystyle{ \mathbf{P}(0)=\mathbf{I} }[/math]. Соответствующее решение [math]\displaystyle{ \mathbf{P}(t)=\exp(\mathbf{Q}t). }[/math]

Свойства матриц P и Q

Для любого [math]\displaystyle{ t\gt 0 }[/math] матрица [math]\displaystyle{ \mathbf{P}(t) }[/math] обладает следующими свойствами:

1. Матричные элементы [math]\displaystyle{ \mathbf{P}(t) }[/math] неотрицательны: [math]\displaystyle{ P_{ij}(t) \geqslant 0 }[/math] (неотрицательность вероятностей).
2. Сумма элементов в каждой строке [math]\displaystyle{ \mathbf{P}(t) }[/math] равна 1: [math]\displaystyle{ \sum_j P_{ij}(t) = 1 }[/math] (полная вероятность), то есть матрица [math]\displaystyle{ \mathbf{P}(t) }[/math] является стохастической справа (или по строкам).
3. Все собственные числа [math]\displaystyle{ \lambda }[/math] матрицы [math]\displaystyle{ \mathbf{P}(t) }[/math] не превосходят 1 по абсолютной величине: [math]\displaystyle{ |\lambda| \leqslant 1 }[/math]. Если [math]\displaystyle{ |\lambda| = 1 }[/math], то [math]\displaystyle{ \lambda = 1 }[/math].
4. Собственному числу [math]\displaystyle{ \lambda=1 }[/math] матрицы [math]\displaystyle{ \mathbf{P}(t) }[/math] соответствует как минимум один неотрицательный левый собственный вектор-строка (равновесие): [math]\displaystyle{ (p_1^*,\, p_2^*, ...); }[/math] [math]\displaystyle{ p_i^* \geqslant 0; }[/math] [math]\displaystyle{ \sum_i p_i^*=1; }[/math] [math]\displaystyle{ \sum_i p_i^* P_{ij}(t) = p_j^* }[/math].
5. Для собственного числа [math]\displaystyle{ \lambda=1 }[/math] матрицы [math]\displaystyle{ \mathbf{P}(t) }[/math] все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

Матрица [math]\displaystyle{ \mathbf{Q} }[/math] обладает следующими свойствами:

1. Внедиагональные матричные элементы [math]\displaystyle{ \mathbf{Q} }[/math] неотрицательны: [math]\displaystyle{ q_{ij} \geqslant 0 \; i\neq j }[/math].
2. Диагональные матричные элементы [math]\displaystyle{ \mathbf{Q} }[/math] неположительны: [math]\displaystyle{ q_{ii} \leqslant 0 }[/math].
3. Сумма элементов в каждой строке [math]\displaystyle{ \mathbf{Q} }[/math] равна 0: [math]\displaystyle{ \sum_j q_{ij}=0 . }[/math]
4. Действительная часть всех собственных чисел [math]\displaystyle{ \mu }[/math] матрицы [math]\displaystyle{ \mathbf{Q} }[/math] неположительна: [math]\displaystyle{ Re(\mu) \leqslant 0 }[/math]. Если [math]\displaystyle{ Re(\mu) = 0 }[/math], то [math]\displaystyle{ \mu = 0 . }[/math]
5. Собственному числу [math]\displaystyle{ \mu=0 }[/math] матрицы [math]\displaystyle{ \mathbf{Q} }[/math] соответствует как минимум один неотрицательный левый собственный вектор-строка (равновесие): [math]\displaystyle{ (p_1^*,\, p_2^*, ...); }[/math] [math]\displaystyle{ p_i^* \geqslant 0; }[/math] [math]\displaystyle{ \sum_i p_i^*=1; }[/math] [math]\displaystyle{ \sum_i p_i^* q_{ij}= 0 . }[/math]
6. Для собственного числа [math]\displaystyle{ \mu=0 }[/math] матрицы [math]\displaystyle{ \mathbf{Q} }[/math] все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

Граф переходов, связность и эргодические цепи Маркова

Для цепи Маркова с непрерывным временем строится ориентированный граф переходов (кратко — граф переходов) по следующим правилам:

• Множество вершин графа совпадает со множеством состояний цепи.
• Вершины [math]\displaystyle{ i,j \, (i\neq j) }[/math] соединяются ориентированным ребром [math]\displaystyle{ i \to j }[/math], если [math]\displaystyle{ q_{ij}\gt 0 }[/math] (то есть интенсивность потока из [math]\displaystyle{ i }[/math]-го состояния в [math]\displaystyle{ j }[/math]-е положительна).

Топологические свойства графа переходов связаны со спектральными свойствами матрицы [math]\displaystyle{ \mathbf{Q} }[/math]. В частности, для конечных цепей Маркова верны следующие теоремы:

• Следующие три свойства А, Б, В конечной цепи Маркова эквивалентны (обладающие ими цепи иногда называют слабо эргодическими):

А. Для любых двух различных вершин графа переходов [math]\displaystyle{ i,j \, (i\neq j) }[/math] найдется такая вершина [math]\displaystyle{ k }[/math] графа («общий сток»), что существуют ориентированные пути от вершины [math]\displaystyle{ i }[/math] к вершине [math]\displaystyle{ k }[/math] и от вершины [math]\displaystyle{ j }[/math] к вершине [math]\displaystyle{ k }[/math]. Замечание: возможен случай [math]\displaystyle{ k=i }[/math] или [math]\displaystyle{ k=j }[/math]; в этом случае тривиальный (пустой) путь от [math]\displaystyle{ i }[/math] к [math]\displaystyle{ i }[/math] или от [math]\displaystyle{ j }[/math] к [math]\displaystyle{ j }[/math] также считается ориентированным путём.

Б. Нулевое собственное число матрицы [math]\displaystyle{ \mathbf{Q} }[/math] невырождено.

В. При [math]\displaystyle{ t \to \infty }[/math] матрица [math]\displaystyle{ \mathbf{P}(t) }[/math] стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

• Следующие пять свойств А, Б, В, Г, Д конечной цепи Маркова эквивалентны (обладающие ими цепи называют эргодическими):

А. Граф переходов цепи ориентированно связен.

Б. Нулевое собственное число матрицы [math]\displaystyle{ \mathbf{Q} }[/math] невырождено и ему соответствует строго положительный левый собственный вектор (равновесное распределение).

В. Для некоторого [math]\displaystyle{ t\gt 0 }[/math] матрица [math]\displaystyle{ \mathbf{P}(t) }[/math] строго положительна (то есть [math]\displaystyle{ P_{ij}(t) \gt 0 }[/math] для всех [math]\displaystyle{ i, j }[/math]).

Г. Для всех [math]\displaystyle{ t\gt 0 }[/math] матрица [math]\displaystyle{ \mathbf{P}(t) }[/math] строго положительна.

Д. При [math]\displaystyle{ t \to \infty }[/math] матрица [math]\displaystyle{ \mathbf{P}(t) }[/math] стремится к строго положительной матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

Примеры

Рис. Примеры графов переходов для цепей Маркова: a) цепь не является слабо эргодической (не существует общего стока для состояний [math]\displaystyle{ A_2, \, A_3 }[/math]); b) слабо эргодическая цепь (граф переходов не является ориентированно связным) c) эргодическая цепь (граф переходов ориентированно связан).

Рассмотрим цепи Маркова с тремя состояниями и с непрерывным временем, соответствующие графам переходов, представленным на рис. В случае (a) отличны от нуля только следующие недиагональные элементы матрицы интенсивностей — [math]\displaystyle{ q_{12}, \, q_{13} }[/math], в случае (b) отличны от нуля только [math]\displaystyle{ q_{12}, \, q_{31} \, q_{32} }[/math], а в случае (c) — [math]\displaystyle{ q_{12}, \, q_{31} \, q_{23} }[/math]. Остальные элементы определяются свойствами матрицы [math]\displaystyle{ \mathbf{Q} }[/math] (сумма элементов в каждой строке равна 0). В результате для графов (a), (b), (c) матрицы интенсивностей имеют вид: [math]\displaystyle{ \mathbf{Q}_a=\begin{pmatrix} -(q_{12}+q_{13})& q_{12} & q_{13}\\ 0& 0 & 0 \\ 0& 0 & 0 \end{pmatrix}, }[/math] [math]\displaystyle{ \mathbf{Q}_b=\begin{pmatrix} -q_{12}& q_{12} & 0 \\ 0& 0 & 0 \\ q_{31}& q_{32} & -(q_{31}+q_{32}) \end{pmatrix}, }[/math] [math]\displaystyle{ \mathbf{Q}_c=\begin{pmatrix} -q_{12}& q_{12} & 0 \\ 0& -q_{23} & q_{23} \\ q_{31}& 0& -q_{31} \end{pmatrix}, }[/math]

Основное кинетическое уравнение

Основная статья: Основное кинетическое уравнение

Основное кинетическое уравнение описывает эволюцию распределения вероятностей в цепи Маркова с непрерывным временем. «Основное уравнение» здесь — не эпитет, а перевод термина англ. Master equation. Для вектора-строки распределения вероятностей [math]\displaystyle{ \pi }[/math] основное кинетическое уравнение имеет вид:

[math]\displaystyle{ \frac{d \pi}{d t} = \pi \mathbf{Q} }[/math]

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

[math]\displaystyle{ \frac{d p_i}{d t} = \sum_{j, \, j \neq i} (T_{ij}p_j - T_{ji}p_i), }[/math]

где [math]\displaystyle{ T_{ij}=q_{ji}. }[/math]

Если для основного кинетического уравнения существует положительное равновесие [math]\displaystyle{ p_i^* \gt 0 }[/math], то его можно записать в форме

[math]\displaystyle{ \frac{d p_i}{d t} = \sum_{j, \, j \neq i} T_{ij}p_j^*\left(\frac{p_j}{p_j^*} - \frac{p_i}{p_i^*}\right). }[/math]

Функции Ляпунова для основного кинетического уравнения

Для основного кинетического уравнения существует богатое семейство выпуклых функций Ляпунова — монотонно меняющихся со временем функций распределения вероятностей. Пусть [math]\displaystyle{ h(x) \, (x\gt 0) }[/math] — выпуклая функция одного переменного. Для любого положительного распределения вероятностей ([math]\displaystyle{ p_i \gt 0 }[/math]) определим функцию Моримото [math]\displaystyle{ H_h(p) }[/math]:

[math]\displaystyle{ H_h(p)=\sum_i p_i^* h\left(\frac{p_i}{p_i^*}\right) }[/math].

Производная [math]\displaystyle{ H_h(p) }[/math] по времени, если [math]\displaystyle{ p(t) }[/math] удовлетворяет основному кинетическому уравнению, есть

[math]\displaystyle{ \frac{d H_h(p(t))}{dt }=\sum_{i,j \, i \neq j} T_{ij}p_j^* \left[h\left(\frac{p_i}{p_i^*}\right)- h\left(\frac{p_j}{p_j^*}\right) + h'\left(\frac{p_i}{p_i^*}\right)\left(\frac{p_j}{p_j^*}-\frac{p_i}{p_i^*}\right)\right] \leqslant 0 }[/math].

Последнее неравенство справедливо из-за выпуклости [math]\displaystyle{ h(x) }[/math].

Примеры функций Моримото [math]\displaystyle{ H_h(p) }[/math]

• [math]\displaystyle{ h(x)= |x-1| }[/math], [math]\displaystyle{ H_h(p)=\sum_i |p_i-p_i^*| }[/math];

эта функция — расстояние от текущего распределения вероятностей до равновесного в [math]\displaystyle{ l_1 }[/math]-норме. Сдвиг по времени является сжатием пространства вероятностных распределений в этой норме. (О свойствах сжатий см. статью Теорема Банаха о неподвижной точке.)

• [math]\displaystyle{ h(x)= x \ln x }[/math], [math]\displaystyle{ H_h(p)=\sum_i p_i \ln\left(\frac{p_i}{p_i^*}\right) }[/math];

эта функция — (минус) энтропия Кульбака (см. Расстояние Кульбака — Лейблера). В физике она соответствует свободной энергии, деленной на [math]\displaystyle{ kT }[/math] (где [math]\displaystyle{ k }[/math] — постоянная Больцмана, [math]\displaystyle{ T }[/math] — абсолютная температура):

если [math]\displaystyle{ p_i^*=\exp(\mu_0-U_i/kT) }[/math] (распределение Больцмана), то

[math]\displaystyle{ H_h(p)=\sum_i p_i \ln p_i + \sum_i p_i U_i/kT -\mu_0 = (\langle U \rangle - TS)/kT }[/math].

• [math]\displaystyle{ h(x)= -\ln x }[/math], [math]\displaystyle{ H_h(p)=-\sum_i p_i^* \ln\left(\frac{p_i}{p_i^*}\right) }[/math];

эта функция — аналог свободной энергии для энтропии Бурга, широко используемой в обработке сигналов:

[math]\displaystyle{ S_{\rm Burg}=\sum_i \ln p_i }[/math]

• [math]\displaystyle{ h(x)= \frac{(x-1)^2}{2} }[/math], [math]\displaystyle{ H_h(p)=\sum_i \frac{(p_i-p_i^*)^2}{2p_i^*} }[/math];

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

• [math]\displaystyle{ h(x)= \frac{x^2}{2} }[/math], [math]\displaystyle{ H_h(p)=\sum_i \frac{p_i^2}{2p_i^*} }[/math];

это (минус) энтропия Фишера.

• [math]\displaystyle{ h(x)= \frac{x^q - 1}{q-1}, \, q\gt 0, \, q\neq 1 }[/math], [math]\displaystyle{ H_h(p)=\frac{1}{q-1}\left[\sum_i p_i^* \left(\frac{p_i}{p_i^*}\right)^q - 1\right] }[/math];

это один из аналогов свободной энергии для энтропии Тсаллиса.

[math]\displaystyle{ S_{q {\rm Tsallis}}(p) = {1 \over q - 1} \left( 1 - \sum_i p^q_i \right). }[/math]

служит основой для статистической физики неэкстенсивных величин. При [math]\displaystyle{ q \to 1 }[/math] она стремится к классической энтропии Больцмана — Гиббса — Шеннона, а соответствующая функция Моримото — к (минус) энтропии Кульбака.

Практическое применение

Основная статья: Скрытая марковская модель

Одной из первых научных дисциплин, в которой цепи Маркова нашли практическое применение, стала лингвистика (в частности текстология). Сам Марков для иллюстрации своих результатов исследовал зависимость в чередовании гласных и согласных в первых главах «Евгения Онегина» и «Детских годов Багрова-внука».

Литература

• Кельберт М. Я., Сухов Ю. М. Вероятность и статистика в примерах и задачах. Т. ІІ: Марковские цепи как отправная точка теории случайных процессов и их приложения. — М.: МЦНМО, 2010. — 295 с. — ISBN 978-5-94057-252-7.
• Марков А. А., Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 2-я серия. — Том 15. (1906) — С. 135—156.
• Маркова цепь / А. В. Прохоров // Большая российская энциклопедия : [в 35 т.] / гл. ред. Ю. С. Осипов. — М. : Большая российская энциклопедия, 2004—2017.
• Kemeny J. G., Snell J. L., Finite Markov chains. — The University Series in Undergraduate Mathematics. — Princeton: Van Nostrand, 1960
  • Перевод: Кемени Дж. Дж., Снелл Дж. Л. Конечные цепи Маркова. — М.: Наука. 1970. — 272 с.
• Чжун Кай-лай Однородные цепи Маркова. Перев. с англ. — М.: Мир, 1964. — 425 с.
• Нуммелин Э., Общие неприводимые цепи Маркова и неотрицательные операторы. — М.: Мир, 1989. — 207 с.
• Morimoto T., Markov processes and the H-theorem. — J. Phys. Soc. Jap. 12 (1963), 328—331.
• Яглом А. М., Яглом И. М., Вероятность и информация. — М., Наука, 1973. — 512 с.
• Kullback S., Information theory and statistics. — Wiley, New York, 1959.
• Burg J.P., The Relationship Between Maximum Entropy Spectra and Maximum Likelihood Spectra, Geophysics 37(2) (1972), 375—376.
• Tsallis C., Possible generalization of Boltzmann-Gibbs statistics. J. Stat. Phys. 52 (1988), 479—487.
• Рудой Ю. Г., Обобщенная информационная энтропия и неканоническое распределение в равновесной статистической механике, ТМФ, 135:1 (2003), 3-54.
• Gorban, Alexander N.; Gorban, Pavel A.; Judge, George. Entropy: The Markov Ordering Approach. Entropy 12, no. 5 (2010), 1145—1193.

Ссылки

• SolidMinus. Разработка класса для работы с цепями Маркова (рус.). Хабрахабр (1 июня 2016). Дата обращения: 18 августа 2016.