Цепь Маркова

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

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

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

Определение

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

$\mathbb{P}(X_{n+1}=i_{n+1}\mid X_n=i_n,X_{n-1}=i_{n-1},\dots ,X_0=i_0)=\mathbb{P}(X_{n+1}=i_{n+1}\mid X_n=i_n)$.

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

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

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

Матрица $P(n)$, где

$P_{ij}(n)\equiv \mathbb{P}(X_{n+1}=j\mid X_n=i)$

называется ма́трицей перехо́дных вероя́тностей на $n$-м шаге, а вектор $𝐩=(p_1,p_2,\dots {)}^{\mathrm{\top }}$, где

$p_i\equiv \mathbb{P}(X_0=i)$

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

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

$\sum _j{P}_{ij}(n)=1,\mathrm{\forall }n\in \mathbb{N}$.

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

$P_{ij}(n)=P_{ij},\mathrm{\forall }n\in \mathbb{N}$.

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

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

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

$\mathbb{P}(X_n=i_n,\dots ,X_0=i_0)=P_{i_{n-1},i_n}\cdots P_{i_0,i_1}{P}_{i_0}$,

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

$\mathbb{P}(X_n=i_n\mid X_0=i_0)=(P^n{)}_{i_0,i_n}$,

то есть матрица переходных вероятностей за $n$ шагов однородной цепи Маркова есть $n$-я степень матрицы переходных вероятностей за 1 шаг. Наконец,

$\mathbb{P}(X_n=i_n)={((P^T{)}^n𝐩)}_{i_n}$.

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

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

Примеры

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

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

Определение

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

$\mathbb{P}(X_{t+h}=x_{t+h}\mid X_s=x_s,0<s⩽t)=\mathbb{P}(X_{t+h}=x_{t+h}\mid X_t=x_t)$.

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

$\mathbb{P}(X_{t+h}=x_{t+h}\mid X_t=x_t)=\mathbb{P}(X_h=x_h\mid X_0=x_0)$.

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

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

$𝐩=(p_1,p_2,\dots {)}^{\mathrm{\top }},p_i=\mathbb{P}(X_0=i),i=1,2,\dots$

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

$𝐏(h)=(P_{ij}(h))=\mathbb{P}(X_h=j\mid X_0=i)$.

Матрица переходных вероятностей удовлетворяет уравнению Колмогорова — Чепмена: $𝐏(t+s)=𝐏(t)𝐏(s)$ или

$P_{ij}(t+s)=\sum _k{P}_{ik}(t)P_{kj}(s).$

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

По определению матрица интенсивностей $𝐐=\underset{h\to 0}{\lim }\frac{𝐏(h)-𝐈}{h}$, или, что эквивалентно,

$𝐐=(q_{ij})={\left(\frac{d{P}_{ij}(h)}{dh}\right)}_{h=0}$.

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

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

  $\frac{d𝐏(t)}{dt}=𝐏(t)𝐐,$

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

  $\frac{d𝐏(t)}{dt}=𝐐𝐏(t).$

Для обоих уравнений начальным условием выбирается $𝐏(0)=𝐈$. Соответствующее решение $𝐏(t)=\exp (𝐐t).$

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

Для любого $t>0$ матрица $𝐏(t)$ обладает следующими свойствами:

1. Матричные элементы $𝐏(t)$ неотрицательны: $P_{ij}(t)⩾0$ (неотрицательность вероятностей).
2. Сумма элементов в каждой строке $𝐏(t)$ равна 1: $\sum _j{P}_{ij}(t)=1$ (полная вероятность), то есть матрица $𝐏(t)$ является стохастической справа (или по строкам).
3. Все собственные числа $\lambda$ матрицы $𝐏(t)$ не превосходят 1 по абсолютной величине: $|\lambda |⩽1$. Если $|\lambda |=1$, то $\lambda =1$.
4. Собственному числу $\lambda =1$ матрицы $𝐏(t)$ соответствует как минимум один неотрицательный левый собственный вектор-строка (равновесие): $(p_1^{*},p_2^{*},...);$ $p_i^{*}⩾0;$ $\sum _i{p}_i^{*}=1;$ $\sum _i{p}_i^{*}{P}_{ij}(t)=p_j^{*}$.
5. Для собственного числа $\lambda =1$ матрицы $𝐏(t)$ все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

Матрица $𝐐$ обладает следующими свойствами:

1. Внедиагональные матричные элементы $𝐐$ неотрицательны: $q_{ij}⩾0i\ne j$.
2. Диагональные матричные элементы $𝐐$ неположительны: $q_{ii}⩽0$.
3. Сумма элементов в каждой строке $𝐐$ равна 0: $\sum _j{q}_{ij}=0.$
4. Действительная часть всех собственных чисел $\mu$ матрицы $𝐐$ неположительна: $Re(\mu )⩽0$. Если $Re(\mu )=0$, то $\mu =0.$
5. Собственному числу $\mu =0$ матрицы $𝐐$ соответствует как минимум один неотрицательный левый собственный вектор-строка (равновесие): $(p_1^{*},p_2^{*},...);$ $p_i^{*}⩾0;$ $\sum _i{p}_i^{*}=1;$ $\sum _i{p}_i^{*}{q}_{ij}=0.$
6. Для собственного числа $\mu =0$ матрицы $𝐐$ все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

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

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

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

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

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

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

Б. Нулевое собственное число матрицы $𝐐$ невырождено.

В. При $t\to \mathrm{\infty }$ матрица $𝐏(t)$ стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

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

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

Б. Нулевое собственное число матрицы $𝐐$ невырождено и ему соответствует строго положительный левый собственный вектор (равновесное распределение).

В. Для некоторого $t>0$ матрица $𝐏(t)$ строго положительна (то есть $P_{ij}(t)>0$ для всех $i,j$).

Г. Для всех $t>0$ матрица $𝐏(t)$ строго положительна.

Д. При $t\to \mathrm{\infty }$ матрица $𝐏(t)$ стремится к строго положительной матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

Примеры

Файл:MarkovTriangle.png

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

Рассмотрим цепи Маркова с тремя состояниями и с непрерывным временем, соответствующие графам переходов, представленным на рис. В случае (a) отличны от нуля только следующие недиагональные элементы матрицы интенсивностей — $q_{12},q_{13}$, в случае (b) отличны от нуля только $q_{12},q_{31}{q}_{32}$, а в случае (c) — $q_{12},q_{31}{q}_{23}$. Остальные элементы определяются свойствами матрицы $𝐐$ (сумма элементов в каждой строке равна 0). В результате для графов (a), (b), (c) матрицы интенсивностей имеют вид: ${𝐐}_a=\left(\begin{array}{ccc}-(q_{12}+q_{13})& q_{12}& q_{13}\\ 0& 0& 0\\ 0& 0& 0\end{array}\right),$ ${𝐐}_b=\left(\begin{array}{ccc}-q_{12}& q_{12}& 0\\ 0& 0& 0\\ q_{31}& q_{32}& -(q_{31}+q_{32})\end{array}\right),$ ${𝐐}_c=\left(\begin{array}{ccc}-q_{12}& q_{12}& 0\\ 0& -q_{23}& q_{23}\\ q_{31}& 0& -q_{31}\end{array}\right),$

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

Шаблон:Основная Основное кинетическое уравнение описывает эволюцию распределения вероятностей в цепи Маркова с непрерывным временем. «Основное уравнение» здесь — не эпитет, а перевод термина Шаблон:Lang-en. Для вектора-строки распределения вероятностей $\pi$ основное кинетическое уравнение имеет вид:

$\frac{d\pi }{dt}=\pi 𝐐$

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

$\frac{d{p}_i}{dt}=\sum _{j,j\ne i}(T_{ij}{p}_j-T_{ji}{p}_i),$

где $T_{ij}=q_{ji}.$

Если для основного кинетического уравнения существует положительное равновесие $p_i^{*}>0$, то его можно записать в форме

$\frac{d{p}_i}{dt}=\sum _{j,j\ne i}{T}_{ij}{p}_j^{*}(\frac{p_j}{p_j^{*}}-\frac{p_i}{p_i^{*}}).$

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

Для основного кинетического уравнения существует богатое семейство выпуклых функций Ляпунова — монотонно меняющихся со временем функций распределения вероятностей. Пусть $h(x)(x>0)$ — выпуклая функция одного переменного. Для любого положительного распределения вероятностей ($p_i>0$) определим функцию Моримото $H_h(p)$:

$H_h(p)=\sum _i{p}_i^{*}h\left(\frac{p_i}{p_i^{*}}\right)$.

Производная $H_h(p)$ по времени, если $p(t)$ удовлетворяет основному кинетическому уравнению, есть

$\frac{d{H}_h(p(t))}{dt}=\sum _{i,ji\ne j}{T}_{ij}{p}_j^{*}[h\left(\frac{p_i}{p_i^{*}}\right)-h\left(\frac{p_j}{p_j^{*}}\right)+h^{\prime }\left(\frac{p_i}{p_i^{*}}\right)(\frac{p_j}{p_j^{*}}-\frac{p_i}{p_i^{*}})]⩽0$.

Последнее неравенство справедливо из-за выпуклости $h(x)$.

Примеры функций Моримото $H_h(p)$

• $h(x)=|x-1|$, $H_h(p)=\sum _i|p_i-p_i^{*}|$;

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

• $h(x)=x\ln x$, $H_h(p)=\sum _i{p}_i\ln \left(\frac{p_i}{p_i^{*}}\right)$;

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

если $p_i^{*}=\exp ({\mu }_0-U_i/kT)$ (распределение Больцмана), то

$H_h(p)=\sum _i{p}_i\ln p_i+\sum _i{p}_i{U}_i/kT-{\mu }_0=(⟨U⟩-TS)/kT$.

• $h(x)=-\ln x$, $H_h(p)=-\sum _i{p}_i^{*}\ln \left(\frac{p_i}{p_i^{*}}\right)$;

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

$S_{\mathrm{B}\mathrm{u}\mathrm{r}\mathrm{g}}=\sum _i\ln p_i$

• $h(x)=\frac{(x-1{)}^2}{2}$, $H_h(p)=\sum _i\frac{(p_i-p_i^{*}{)}^2}{2p_i^{*}}$;

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

• $h(x)=\frac{x^2}{2}$, $H_h(p)=\sum _i\frac{p_i^2}{2p_i^{*}}$;

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

• $h(x)=\frac{x^q-1}{q-1},q>0,q\ne 1$, $H_h(p)=\frac{1}{q-1}[\sum _i{p}_i^{*}{\left(\frac{p_i}{p_i^{*}}\right)}^q-1]$;

это один из аналогов свободной энергии для Шаблон:Iw.

$S_{q\mathrm{T}\mathrm{s}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{s}}(p)=\frac{1}{q-1}(1-\sum _i{p}_i^q).$

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

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

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

Литература

• Шаблон:Книга
• Марков А. А., Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 2-я серия. — Том 15. (1906) — С. 135—156.
• Шаблон:БРЭ
• 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.

Ссылки

• Шаблон:Cite web