Цепь Маркова

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

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

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

ОпределениеПравить

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

$\mathbb{P}(X_{n+1}=i_{n+1}\mid <!--\; \mid \; -->X_n=i_n,X_{n-<!--\; -\; -->1}=i_{n-<!--\; -\; -->1},\dots <!--\; \dots \; -->,X_0=i_0)=\mathbb{P}(X_{n+1}=i_{n+1}\mid <!--\; \mid \; -->X_n=i_n)$${\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})$ .

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

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

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

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

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

называется ма́трицей перехо́дных вероя́тностей на $n$$n$ -м шаге, а вектор $\mathbf{p}=(p_1,p_2,\dots <!--\; \dots \; -->{)}^{\mathrm{\top <!--\; \top \; -->}}$${\mathbf {p}}=(p_{1},p_{2},\ldots )^{{\top }}$ , где

$p_i\equiv <!--\; \equiv \; -->\mathbb{P}(X_0=i)$$p_{i}\equiv {\mathbb {P}}(X_{0}=i)$ 

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

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

$\underset{j}{\sum <!--\; \sum \; -->}{P}_{ij}(n)=1,\mathrm{\forall <!--\; \forall \; -->}n\in <!--\; \in \; -->\mathbb{N}$$\sum \limits _{{j}}P_{{ij}}(n)=1,\quad \forall n\in {\mathbb {N}}$ .

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

$P_{ij}(n)=P_{ij},\mathrm{\forall <!--\; \forall \; -->}n\in <!--\; \in \; -->\mathbb{N}$$P_{{ij}}{(n)}=P_{{ij}},\quad \forall n\in {\mathbb {N}}$ .

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

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

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

$\mathbb{P}(X_n=i_n,\dots <!--\; \dots \; -->,X_0=i_0)=P_{i_{n-<!--\; -\; -->1},i_n}\cdots <!--\; \cdots \; -->P_{i_0,i_1}{P}_{i_0}$${\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}}}$ ,

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

$\mathbb{P}(X_n=i_n\mid <!--\; \mid \; -->X_0=i_0)=(P^n{)}_{i_0,i_n}$${\mathbb {P}}(X_{n}=i_{n}\mid X_{0}=i_{0})=(P^{n})_{{i_{0},i_{n}}}$ ,

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

$\mathbb{P}(X_n=i_n)={\left((P^T{)}^n\mathbf{p}\right)}_{i_n}$${\mathbb {P}}(X_{n}=i_{n})=\left((P^{T})^{n}{\mathbf {p}}\right)_{{i_{n}}}$ .

Типы состоянийПравить

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

ПримерыПравить

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

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

ОпределениеПравить

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

${\mathbb {P}}(X_{{t+h}}=x_{{t+h}}\mid X_{s}=x_{s},\;0<s\leqslant t)={\mathbb {P}}(X_{{t+h}}=x_{{t+h}}\mid X_{t}=x_{t})$ .

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

$\mathbb{P}(X_{t+h}=x_{t+h}\mid <!--\; \mid \; -->X_t=x_t)=\mathbb{P}(X_h=x_h\mid <!--\; \mid \; -->X_0=x_0)$${\mathbb {P}}(X_{{t+h}}=x_{{t+h}}\mid X_{t}=x_{t})={\mathbb {P}}(X_{{h}}=x_{{h}}\mid X_{0}=x_{0})$ .

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

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

$\mathbf{p}=(p_1,p_2,\dots <!--\; \dots \; -->{)}^{\mathrm{\top <!--\; \top \; -->}},p_i=\mathbb{P}(X_0=i),i=1,2,\dots <!--\; \dots \; -->$${\mathbf {p}}=(p_{1},p_{2},\ldots )^{{\top }},\;p_{i}={\mathbb {P}}(X_{0}=i),\quad i=1,2,\ldots$ 

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

$\mathbf{P}(h)=(P_{ij}(h))=\mathbb{P}(X_h=j\mid <!--\; \mid \; -->X_0=i)$${\mathbf {P}}(h)=(P_{{ij}}(h))={\mathbb {P}}(X_{h}=j\mid X_{0}=i)$ .

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

$P_{ij}(t+s)=\underset{k}{\sum <!--\; \sum \; -->}{P}_{ik}(t)P_{kj}(s).$$P_{{ij}}(t+s)=\sum _{k}P_{{ik}}(t)P_{{kj}}(s).$ 

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

По определению матрица интенсивностей $\mathbf{Q}=\underset{h\to <!--\; \to \; -->0}{lim}\frac{\mathbf{P}(h)-<!--\; -\; -->\mathbf{I}}{h}$${\mathbf {Q}}=\lim _{{h\to 0}}{\frac {{\mathbf {P}}(h)-{\mathbf {I}}}{h}}$ , или, что эквивалентно,

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

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

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

  $\frac{d\mathbf{P}(t)}{dt}=\mathbf{P}(t)\mathbf{Q},$${\frac {d{\mathbf {P}}(t)}{dt}}={\mathbf {P}}(t){\mathbf {Q}},$ 

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

  $\frac{d\mathbf{P}(t)}{dt}=\mathbf{Q}\mathbf{P}(t).$${\frac {d{\mathbf {P}}(t)}{dt}}={\mathbf {Q}}{\mathbf {P}}(t).$ 

Для обоих уравнений начальным условием выбирается $\mathbf{P}(0)=\mathbf{I}$${\mathbf {P}}(0)={\mathbf {I}}$ . Соответствующее решение $\mathbf{P}(t)=\exp <!--\; \; -->(\mathbf{Q}t).$${\mathbf {P}}(t)=\exp({\mathbf {Q}}t).$ 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПримерыПравить

 

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

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

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

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

Основное кинетическое уравнение описывает эволюцию распределения вероятностей в цепи Маркова с непрерывным временем. «Основное уравнение» здесь — не эпитет, а перевод термина англ. Master equation. Для вектора-строки распределения вероятностей $\mathrm{\pi <!--\; \pi \; -->}$$\pi$  основное кинетическое уравнение имеет вид:

$\frac{d\mathrm{\pi <!--\; \pi \; -->}}{dt}=\mathrm{\pi <!--\; \pi \; -->}\mathbf{Q}$${\frac {d\pi }{dt}}=\pi {\mathbf {Q}}$ 

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

$\frac{d{p}_i}{dt}=\underset{j,j\ne <!--\; \ne \; -->i}{\sum <!--\; \sum \; -->}(T_{ij}{p}_j-<!--\; -\; -->T_{ji}{p}_i),$${\frac {dp_{i}}{dt}}=\sum _{{j,\,j\neq i}}(T_{{ij}}p_{j}-T_{{ji}}p_{i}),$ 

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

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

$\frac{d{p}_i}{dt}=\underset{j,j\ne <!--\; \ne \; -->i}{\sum <!--\; \sum \; -->}{T}_{ij}{p}_j^{\ast <!--\; \ast \; -->}\left(\frac{p_j}{p_j^{\ast <!--\; \ast \; -->}}-<!--\; -\; -->\frac{p_i}{p_i^{\ast <!--\; \ast \; -->}}\right).$${\frac {dp_{i}}{dt}}=\sum _{{j,\,j\neq i}}T_{{ij}}p_{j}^{*}\left({\frac {p_{j}}{p_{j}^{*}}}-{\frac {p_{i}}{p_{i}^{*}}}\right).$ 

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

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

$H_h(p)=\underset{i}{\sum <!--\; \sum \; -->}{p}_i^{\ast <!--\; \ast \; -->}h\left(\frac{p_i}{p_i^{\ast <!--\; \ast \; -->}}\right)$$H_{h}(p)=\sum _{i}p_{i}^{*}h\left({\frac {p_{i}}{p_{i}^{*}}}\right)$ .

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

$\frac{d{H}_h(p(t))}{dt}=\underset{i,ji\ne <!--\; \ne \; -->j}{\sum <!--\; \sum \; -->}{T}_{ij}{p}_j^{\ast <!--\; \ast \; -->}\left[h\left(\frac{p_i}{p_i^{\ast <!--\; \ast \; -->}}\right)-<!--\; -\; -->h\left(\frac{p_j}{p_j^{\ast <!--\; \ast \; -->}}\right)+h^{\prime }\left(\frac{p_i}{p_i^{\ast <!--\; \ast \; -->}}\right)\left(\frac{p_j}{p_j^{\ast <!--\; \ast \; -->}}-<!--\; -\; -->\frac{p_i}{p_i^{\ast <!--\; \ast \; -->}}\right)\right]⩽<!--\; ⩽\; -->0$${\frac {dH_{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$ .

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

Примеры функций Моримото $H_h(p)$$H_{h}(p)$ Править

• $h(x)=|x-<!--\; -\; -->1|$$h(x)=|x-1|$ , $H_h(p)=\underset{i}{\sum <!--\; \sum \; -->}|p_i-<!--\; -\; -->p_i^{\ast <!--\; \ast \; -->}|$$H_{h}(p)=\sum _{i}|p_{i}-p_{i}^{*}|$ ;

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

• $h(x)=x\ln <!--\; \; -->x$$h(x)=x\ln x$ , $H_h(p)=\underset{i}{\sum <!--\; \sum \; -->}{p}_i\ln <!--\; \; -->\left(\frac{p_i}{p_i^{\ast <!--\; \ast \; -->}}\right)$$H_{h}(p)=\sum _{i}p_{i}\ln \left({\frac {p_{i}}{p_{i}^{*}}}\right)$ ;

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

если $p_i^{\ast <!--\; \ast \; -->}=\exp <!--\; \; -->({\mathrm{\mu <!--\; \mu \; -->}}_0-<!--\; -\; -->U_i/kT)$$p_{i}^{*}=\exp(\mu _{0}-U_{i}/kT)$  (распределение Больцмана), то

$H_h(p)=\underset{i}{\sum <!--\; \sum \; -->}{p}_i\ln <!--\; \; -->p_i+\underset{i}{\sum <!--\; \sum \; -->}{p}_i{U}_i/kT-<!--\; -\; -->{\mathrm{\mu <!--\; \mu \; -->}}_0=(⟨<!--\; ⟨\; -->U⟩<!--\; ⟩\; -->-<!--\; -\; -->TS)/kT$$H_{h}(p)=\sum _{i}p_{i}\ln p_{i}+\sum _{i}p_{i}U_{i}/kT-\mu _{0}=(\langle U\rangle -TS)/kT$ .

• $h(x)=-<!--\; -\; -->\ln <!--\; \; -->x$$h(x)=-\ln x$ , $H_h(p)=-<!--\; -\; -->\underset{i}{\sum <!--\; \sum \; -->}{p}_i^{\ast <!--\; \ast \; -->}\ln <!--\; \; -->\left(\frac{p_i}{p_i^{\ast <!--\; \ast \; -->}}\right)$$H_{h}(p)=-\sum _{i}p_{i}^{*}\ln \left({\frac {p_{i}}{p_{i}^{*}}}\right)$ ;

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

$S_{\mathrm{B}\mathrm{u}\mathrm{r}\mathrm{g}}=\underset{i}{\sum <!--\; \sum \; -->}\ln <!--\; \; -->p_i$$S_{{{\rm {Burg}}}}=\sum _{i}\ln p_{i}$ 

• $h(x)=\frac{(x-<!--\; -\; -->1{)}^2}{2}$$h(x)={\frac {(x-1)^{2}}{2}}$ , $H_h(p)=\underset{i}{\sum <!--\; \sum \; -->}\frac{(p_i-<!--\; -\; -->p_i^{\ast <!--\; \ast \; -->}{)}^2}{2p_i^{\ast <!--\; \ast \; -->}}$$H_{h}(p)=\sum _{i}{\frac {(p_{i}-p_{i}^{*})^{2}}{2p_{i}^{*}}}$ ;

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

• $h(x)=\frac{x^2}{2}$$h(x)={\frac {x^{2}}{2}}$ , $H_h(p)=\underset{i}{\sum <!--\; \sum \; -->}\frac{p_i^2}{2p_i^{\ast <!--\; \ast \; -->}}$$H_{h}(p)=\sum _{i}{\frac {p_{i}^{2}}{2p_{i}^{*}}}$ ;

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

• $h(x)=\frac{x^q-<!--\; -\; -->1}{q-<!--\; -\; -->1},q>0,q\ne <!--\; \ne \; -->1$$h(x)={\frac {x^{q}-1}{q-1}},\,q>0,\,q\neq 1$ , $H_h(p)=\frac{1}{q-<!--\; -\; -->1}\left[\underset{i}{\sum <!--\; \sum \; -->}{p}_i^{\ast <!--\; \ast \; -->}{\left(\frac{p_i}{p_i^{\ast <!--\; \ast \; -->}}\right)}^q-<!--\; -\; -->1\right]$$H_{h}(p)={\frac {1}{q-1}}\left[\sum _{i}p_{i}^{*}\left({\frac {p_{i}}{p_{i}^{*}}}\right)^{q}-1\right]$ ;

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

$S_{q\mathrm{T}\mathrm{s}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{s}}(p)=\frac{1}{q-<!--\; -\; -->1}\left(1-<!--\; -\; -->\underset{i}{\sum <!--\; \sum \; -->}{p}_i^q\right).$$S_{{q{{\rm {Tsallis}}}}}(p)={1 \over q-1}\left(1-\sum _{i}p_{i}^{q}\right).$ 

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

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

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

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

ЛитератураПравить

• Кельберт М. Я., Сухов Ю. М. Вероятность и статистика в примерах и задачах. Т. ІІ: Марковские цепи как отправная точка теории случайных процессов и их приложения. — М.: МЦНМО, 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.