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

[[Файл:Markovkate 01.svg|thumb|right|Пример цепи с двумя состояниями]]
'''Це́пь Ма́ркова''' — последовательность [[Случайное событие|случайных событий]] с конечным или [[Счётное множество|счётным]] числом [[Элементарный исход|исходов]], где вероятность наступления каждого события зависит только от состояния, достигнутого в предыдущем событии<ref>{{Cite web|url=https://www.lexico.com/en/definition/markov_chain|title="Markov chain {{!}} Definition of Markov chain in US English by Oxford Dictionaries"|author=|website=Oxford Dictionaries {{!}} English.|date=2017-12-14|publisher=Lexico Dictionaries {{!}} English|lang=en|accessdate=2020-04-01|archive-date=2021-02-25|archive-url=https://web.archive.org/web/20210225122702/https://www.lexico.com/en/definition/markov_chain|url-status=dead}}</ref>. Характеризуется тем свойством, что, говоря нестрого, при текущем настоящем состоянии системы, её будущее состояние не зависит от прошлого. Названа в честь [[Марков, Андрей Андреевич (старший)|А. А. Маркова (старшего)]], который впервые ввёл это понятие в работе 1906 года.<ref>{{книга |заглавие=Markov Chains: From Theory to Implementation and Experimentation |издательство=[[John Wiley & Sons]] |год=2017 |isbn=978-1-119-38755-8 |место=USA, NJ |страницы=2—8 |язык=en |автор=Gagniuc, Paul A.}}</ref>

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

=== Определение ===
Последовательность [[Дискретное распределение|дискретных]] [[Случайная величина|случайных величин]] <math>\{X_n\}_{n \geqslant 0}</math> называется простой цепью Маркова (с дискретным временем), если
: <math>\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>\{X_n\}</math> называется '''простра́нством состоя́ний''' цепи, а номер <math>n</math> — номером шага.

=== Переходная матрица и однородные цепи ===
[[Матрица (математика)|Матрица]] <math>P{(n)}</math>, где
: <math>P_{ij}{(n)} \equiv \mathbb{P}(X_{n+1} = j \mid X_n = i)</math>
называется '''ма́трицей перехо́дных вероя́тностей''' на <math>n</math>-м шаге, а [[Вектор (алгебра)|вектор]] <math>\mathbf{p} = (p_1,p_2,\ldots)^{\top}</math>, где
: <math>p_i \equiv \mathbb{P}(X_0 = i)</math>
— '''нача́льным распределе́нием''' цепи Маркова.

Очевидно, матрица переходных вероятностей является [[Стохастическая матрица|стохастической]] справа, то есть
: <math>\sum\limits_{j} P_{ij}(n) = 1, \quad \forall n \in \mathbb{N}</math>.

Цепь Маркова называется '''одноро́дной''', если матрица переходных вероятностей не зависит от номера шага, то есть
: <math>P_{ij}{(n)} = P_{ij},\quad \forall n \in \mathbb{N}</math>.
В противном случае цепь Маркова называется неоднородной. В дальнейшем будем предполагать, что имеем дело с однородными цепями Маркова.

=== Конечномерные распределения и матрица перехода за n шагов ===
Из свойств [[Условная вероятность|условной вероятности]] и определения однородной цепи Маркова получаем:
: <math>\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>\mathbb{P}(X_n = i_n \mid X_0 = i_0) = (P^n)_{i_0,i_n}</math>,
то есть матрица переходных вероятностей за <math>n</math> шагов однородной цепи Маркова есть <math>n</math>-я степень матрицы переходных вероятностей за 1 шаг. Наконец,
: <math>\mathbb{P}(X_n = i_n) = \left((P^T)^n \mathbf{p}\right)_{i_n}</math>.

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

=== Примеры ===
* [[Ветвящийся процесс]];
* [[Случайное блуждание]];

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

=== Определение ===
Семейство дискретных случайных величин <math>\{X_t\}_{t \geqslant 0}</math> называется цепью Маркова (с непрерывным временем), если
: <math>\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)</math>.

Цепь Маркова с непрерывным временем называется однородной, если
: <math>\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>\mathbf{p} = (p_1,p_2,\ldots)^{\top},\; p_i = \mathbb{P}(X_0 = i),\quad i=1,2,\ldots</math>
и '''ма́трицей перехо́дных фу́нкций''' (''переходных вероятностей'')
: <math>\mathbf{P}(h)=(P_{ij}(h)) = \mathbb{P}(X_h = j \mid X_0 = i)</math>.
Матрица переходных вероятностей удовлетворяет [[Уравнение Колмогорова — Чепмена|уравнению Колмогорова — Чепмена]]: <math>\mathbf{P}(t+s)=\mathbf{P}(t)\mathbf{P}(s)</math> или
: <math>P_{ij}(t+s)=\sum_k P_{ik}(t)P_{kj}(s).</math>

=== Матрица интенсивностей и дифференциальные уравнения Колмогорова ===
По определению матрица интенсивностей <math>\mathbf{Q}=\lim_{h \to 0}\frac{\mathbf{P}(h)-\mathbf{I}}{h}</math>, или, что эквивалентно,
: <math>\mathbf{Q}=(q_{ij})=\left(\frac{dP_{ij}(h)}{dh}\right)_{h=0}</math>.
Из уравнения Колмогорова — Чепмена следуют два уравнения:
* '''[[Прямое уравнение Колмогорова]]'''
*: <math>\frac{d \mathbf{P}(t)}{d t}=\mathbf{P}(t)\mathbf{Q},</math>
* '''[[Обратное уравнение Колмогорова]]'''
*: <math>\frac{d \mathbf{P}(t)}{d t}=\mathbf{Q}\mathbf{P}(t).</math>
Для обоих уравнений начальным условием выбирается <math>\mathbf{P}(0)=\mathbf{I}</math>. Соответствующее решение <math>\mathbf{P}(t)=\exp(\mathbf{Q}t).</math>

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

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

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

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

=== Граф переходов, связность и эргодические цепи Маркова ===
Для цепи Маркова с непрерывным временем строится [[Граф (математика)|ориентированный граф]] переходов (кратко — граф переходов) по следующим правилам:
* Множество вершин графа совпадает со множеством состояний цепи.
* Вершины <math>i,j \, (i\neq j)</math> соединяются ориентированным ребром <math>i \to j </math>, если <math>q_{ij}>0</math> (то есть интенсивность потока из <math>i</math>-го состояния в <math>j</math>-е положительна).

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

* Следующие три свойства А, Б, В конечной цепи Маркова эквивалентны (обладающие ими цепи иногда называют '''слабо эргодическими'''):
: А. Для любых двух различных вершин графа переходов <math>i,j \, (i\neq j)</math> найдется такая вершина <math>k</math> графа («общий сток»), что существуют ориентированные пути от вершины <math>i</math> к вершине <math>k</math> и от вершины <math>j</math> к вершине <math>k</math>. ''Замечание'': возможен случай <math>k=i</math> или <math>k=j</math>; в этом случае тривиальный (пустой) путь от <math>i</math> к <math>i</math> или от <math>j</math> к <math>j</math> также считается ориентированным путём.
: Б. Нулевое собственное число матрицы <math>\mathbf{Q}</math> невырождено.
: В. При <math>t \to \infty</math> матрица <math>\mathbf{P}(t)</math> стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).
* Следующие пять свойств А, Б, В, Г, Д конечной цепи Маркова эквивалентны (обладающие ими цепи называют '''эргодическими'''):
: А. Граф переходов цепи ориентированно связен.
: Б. Нулевое собственное число матрицы <math>\mathbf{Q}</math> невырождено и ему соответствует строго положительный левый собственный вектор (равновесное распределение).
: В. Для некоторого <math>t>0</math> матрица <math>\mathbf{P}(t)</math> строго положительна (то есть <math>P_{ij}(t) > 0</math> для всех <math>i, j</math>).
: Г. Для всех <math>t>0</math> матрица <math>\mathbf{P}(t)</math> строго положительна.
: Д. При <math>t \to \infty</math> матрица <math>\mathbf{P}(t)</math> стремится к строго положительной матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

=== Примеры ===
[[Файл:MarkovTriangle.png|thumb|350px|Рис. Примеры графов переходов для цепей Маркова:
a) цепь не является слабо эргодической (не существует общего стока для состояний <math>A_2, \, A_3</math>);

b) слабо эргодическая цепь (граф переходов не является ориентированно связным)

c) эргодическая цепь (граф переходов ориентированно связан).
]]

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

== Основное кинетическое уравнение ==
{{Основная|Основное кинетическое уравнение}}
'''Основное кинетическое уравнение''' описывает эволюцию распределения вероятностей в цепи Маркова с непрерывным временем. «Основное уравнение» здесь — не эпитет, а перевод термина {{lang-en|Master equation}}. Для вектора-строки распределения вероятностей <math>\pi</math> основное кинетическое уравнение имеет вид:
: <math>\frac{d \pi}{d t} = \pi \mathbf{Q}</math>
и совпадает, по существу, с [[Прямое уравнение Колмогорова|прямым уравнением Колмогорова]]. В физической литературе чаще используют векторы-столбцы вероятностей и записывают основное кинетическое уравнение в виде, который явно использует закон сохранения полной вероятности:
: <math>\frac{d p_i}{d t} = \sum_{j, \, j \neq i} (T_{ij}p_j - T_{ji}p_i),</math>
где <math>T_{ij}=q_{ji}.</math>

Если для основного кинетического уравнения существует положительное равновесие <math>p_i^* > 0</math>, то его можно записать в форме
: <math>\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>h(x) \, (x>0) </math> — [[выпуклая функция]] одного переменного. Для любого положительного распределения вероятностей (<math>p_i > 0</math>) определим ''функцию Моримото'' <math>H_h(p)</math>:
: <math>H_h(p)=\sum_i p_i^* h\left(\frac{p_i}{p_i^*}\right)</math>.
Производная <math>H_h(p)</math> по времени, если <math>p(t)</math> удовлетворяет основному кинетическому уравнению, есть
: <math>\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>h(x)</math>.

==== Примеры функций Моримото <math>H_h(p)</math> ====
* <math>h(x)= |x-1|</math>, <math>H_h(p)=\sum_i |p_i-p_i^*|</math>;
: эта функция — расстояние от текущего распределения вероятностей до равновесного в <math>l_1</math>-[[Норма (математика)|норме]]. Сдвиг по времени является сжатием пространства вероятностных распределений в этой норме. (О свойствах сжатий см. статью [[Теорема Банаха о неподвижной точке]].)
* <math>h(x)= x \ln x</math>, <math>H_h(p)=\sum_i p_i \ln\left(\frac{p_i}{p_i^*}\right)</math>;
: эта функция — (минус) [[энтропия]] Кульбака (см. [[Расстояние Кульбака — Лейблера]]). В физике она соответствует [[Свободная энергия|свободной энергии]], деленной на <math>kT</math> (где <math>k</math> — [[постоянная Больцмана]], <math>T</math> — абсолютная [[температура]]):
: если <math>p_i^*=\exp(\mu_0-U_i/kT)</math> ([[распределение Больцмана]]), то
: <math>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>h(x)= -\ln x</math>, <math>H_h(p)=-\sum_i p_i^* \ln\left(\frac{p_i}{p_i^*}\right)</math>;
: эта функция — аналог свободной энергии для энтропии Бурга, широко используемой в обработке сигналов:
:: <math>S_{\rm Burg}=\sum_i \ln p_i</math>
* <math>h(x)= \frac{(x-1)^2}{2}</math>, <math>H_h(p)=\sum_i \frac{(p_i-p_i^*)^2}{2p_i^*}</math>;
: это квадратичное приближение для (минус) энтропии Кульбака вблизи точки равновесия. С точностью до постоянного во времени слагаемого эта функция совпадает с (минус) энтропией Фишера, которую даёт следующий выбор,
* <math>h(x)= \frac{x^2}{2}</math>, <math>H_h(p)=\sum_i \frac{p_i^2}{2p_i^*}</math>;
: это (минус) [[Информация Фишера|энтропия Фишера]].
* <math>h(x)= \frac{x^q - 1}{q-1}, \, q>0, \, q\neq 1</math>, <math>H_h(p)=\frac{1}{q-1}\left[\sum_i p_i^* \left(\frac{p_i}{p_i^*}\right)^q - 1\right]</math>;
: это один из аналогов свободной энергии для {{iw|Энтропия Тсаллиса|энтропии Тсаллиса|en|Tsallis entropy}}.
: <math>S_{q {\rm Tsallis}}(p) = {1 \over q - 1} \left( 1 - \sum_i p^q_i \right).</math>
: служит основой для статистической физики неэкстенсивных величин. При <math>q \to 1</math> она стремится к классической энтропии Больцмана — Гиббса — Шеннона, а соответствующая функция Моримото — к (минус) энтропии Кульбака.

== Практическое применение ==
{{основная статья|Скрытая марковская модель}}
{{Дополнить раздел|дата=2015-12-02}}
Одной из первых научных дисциплин, в которой цепи Маркова нашли практическое применение, стала [[лингвистика]] (в частности [[текстология]]). Сам Марков для иллюстрации своих результатов исследовал зависимость в чередовании гласных и согласных в первых главах «[[Евгений Онегин|Евгения Онегина]]» и «[[Детские годы Багрова-внука|Детских годов Багрова-внука]]»<ref>{{книга |автор=Майстров, Л. Е. |заглавие=Развитие понятия вероятности |ответственный= |ссылка= https://books.google.com/books?id=JW0LAQAAIAAJ|место= |издательство=Наука |год= 1980|том= |страниц= 269|страницы= 188|isbn= |ref= }}</ref>.

== Примечания ==
{{примечания}}

== Литература ==
* {{книга|автор=Кельберт М. Я., Сухов Ю. М.|заглавие=Вероятность и статистика в примерах и задачах. Т. ІІ: Марковские цепи как отправная точка теории случайных процессов и их приложения |год=2010|ссылка=|место=М.|издательство=МЦНМО|тираж=|страниц=295 |isbn=978-5-94057-252-7}}
* ''Марков А. А.'', Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 2-я серия. — Том 15. (1906) — С. 135—156.
* {{БРЭ|автор=А. В. Прохоров|статья=Маркова цепь|ссылка=https://old.bigenc.ru/mathematics/text/2187018|архив=|архив дата=}}
* ''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.
* ''[[Яглом, Акива Моисеевич|Яглом А. М.]], [[Яглом, Исаак Моисеевич|Яглом И. М.]]'', [https://web.archive.org/web/20080215194911/http://ilib.mirror1.mccme.ru/djvu/yaglom/verojatnost.htm Вероятность и информация]. — М., Наука, 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.
* ''Рудой Ю. Г.'', [http://mi.mathnet.ru/tmf178 Обобщенная информационная энтропия и неканоническое распределение в равновесной статистической механике], ТМФ, 135:1 (2003), 3-54.
* ''Gorban, Alexander N.; Gorban, Pavel A.; Judge, George.'' [http://www.mdpi.com/1099-4300/12/5/1145/ Entropy: The Markov Ordering Approach]. [http://www.mdpi.com/journal/entropy Entropy] 12, no. 5 (2010), 1145—1193.

== Ссылки ==
* {{cite web|author=SolidMinus|title=Разработка класса для работы с цепями Маркова|url=https://habrahabr.ru/post/302392/|date=2016-06-01|publisher=Хабрахабр|accessdate=2016-08-18|language=ru}}

{{Внешние ссылки}}
{{Состояния цепи Маркова}}
{{Типы искусственных нейронных сетей}}
{{Машинное обучение}}
{{перевести|en|Markov chain}}

[[Категория:Марковские процессы]]