Меню Главная Случайная статья Настройки Цепь Маркова Материал из https://ru.wikipedia.org Цепь Маркова — последовательность случайных событий с конечным или счётным числом исходов, где вероятность наступления каждого события зависит только от состояния, достигнутого в предыдущем событии[1]. Характеризуется тем свойством, что, говоря нестрого, при текущем настоящем состоянии системы, её будущее состояние не зависит от прошлого. Названа в честь А. А. Маркова (старшего), который впервые ввёл это понятие в работе 1906 года[2]. В случае цепи Маркова ${\displaystyle N}$-го порядка вероятность наступления каждого события зависит от состояния, достигнутого в ${\displaystyle N}$ предыдущих событиях. Содержание 1 Цепь Маркова с дискретным временем 1.1 Определение 1.2 Переходная матрица и однородные цепи 1.3 Конечномерные распределения и матрица перехода за n шагов 1.4 Типы состояний 1.5 Примеры 2 Цепь Маркова с непрерывным временем 2.1 Определение 2.2 Матрица переходных функций и уравнение Колмогорова — Чепмена 2.3 Матрица интенсивностей и дифференциальные уравнения Колмогорова 2.4 Свойства матриц P и Q 2.5 Граф переходов, связность и эргодические цепи Маркова 2.6 Примеры 3 Основное кинетическое уравнение 3.1 Функции Ляпунова для основного кинетического уравнения 3.1.1 Примеры функций Моримото '"`UNIQ--postMath-00000083-QINU`"' 4 Практическое применение 5 Примечания 6 Литература 7 Ссылки Цепь Маркова с дискретным временем Определение Последовательность дискретных случайных величин ${\displaystyle \{X_{n}\}_{n\geqslant 0}}$ называется простой цепью Маркова (цепью Маркова первого порядка) (с дискретным временем), если ${\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})}$. Таким образом, в простейшем случае условное распределение последующего состояния цепи Маркова зависит только от текущего состояния и не зависит от всех предыдущих состояний (в отличие от цепей Маркова высших порядков). Последовательность дискретных случайных величин ${\displaystyle \{X_{n}\}_{n\geqslant 0}}$ называется цепью Маркова ${\displaystyle N}$-го порядка (с дискретным временем), если ${\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},X_{n-1}=i_{n-1},\ldots ,X_{n-N+1}=i_{n-N+1})}$. Таким образом, в условное распределение последующего состояния цепи Маркова ${\displaystyle N}$-го порядка зависит от текущего состояния и от ${\displaystyle N-1}$ предыдущих состояний. Область значений случайных величин ${\displaystyle \{X_{n}\}}$ называется пространством состояний цепи, а номер ${\displaystyle n}$ — номером шага. Переходная матрица и однородные цепи Матрица ${\displaystyle P{(n)}}$, где ${\displaystyle P_{ij}{(n)}\equiv \mathbb {P} (X_{n+1}=j\mid X_{n}=i)}$ называется матрицей переходных вероятностей на ${\displaystyle n}$-м шаге, а вектор ${\displaystyle \mathbf {p} =(p_{1},p_{2},\ldots )^{\top }}$, где ${\displaystyle p_{i}\equiv \mathbb {P} (X_{0}=i)}$ — начальным распределением цепи Маркова. Очевидно, матрица переходных вероятностей является стохастической справа, то есть ${\displaystyle \sum \limits _{j}P_{ij}(n)=1,\quad \forall n\in \mathbb {N} }$. Цепь Маркова называется однородной, если матрица переходных вероятностей не зависит от номера шага, то есть ${\displaystyle P_{ij}{(n)}=P_{ij},\quad \forall n\in \mathbb {N} }$. В противном случае цепь Маркова называется неоднородной. В дальнейшем будем предполагать, что имеем дело с однородными цепями Маркова. Конечномерные распределения и матрица перехода за n шагов Из свойств условной вероятности и определения однородной цепи Маркова получаем: ${\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}}}$, откуда вытекает специальный случай уравнения Колмогорова — Чепмена: ${\displaystyle \mathbb {P} (X_{n}=i_{n}\mid X_{0}=i_{0})=(P^{n})_{i_{0},i_{n}}}$, то есть матрица переходных вероятностей за ${\displaystyle n}$ шагов однородной цепи Маркова есть ${\displaystyle n}$-я степень матрицы переходных вероятностей за 1 шаг. Наконец, ${\displaystyle \mathbb {P} (X_{n}=i_{n})=\left((P^{T})^{n}\mathbf {p} \right)_{i_{n}}}$. Типы состояний Возвратное состояние. Возвратная цепь Маркова. Достижимое состояние. Неразложимая цепь Маркова. Периодическое состояние. Периодическая цепь Маркова. Поглощающее состояние. Состояние ${\displaystyle i}$ называется поглощающим, если ${\displaystyle P_{i,i}=1}$. Эргодическое состояние. Примеры Ветвящийся процесс; Случайное блуждание; Цепь Маркова с непрерывным временем Определение Семейство дискретных случайных величин ${\displaystyle \{X_{t}\}_{t\geqslant 0}}$ называется цепью Маркова (с непрерывным временем), если ${\displaystyle \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})}$. Цепь Маркова с непрерывным временем называется однородной, если ${\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})}$. Матрица переходных функций и уравнение Колмогорова — Чепмена Аналогично случаю дискретного времени, конечномерные распределения однородной цепи Маркова с непрерывным временем полностью определены начальным распределением ${\displaystyle \mathbf {p} =(p_{1},p_{2},\ldots )^{\top },\;p_{i}=\mathbb {P} (X_{0}=i),\quad i=1,2,\ldots }$ и матрицей переходных функций (переходных вероятностей) ${\displaystyle \mathbf {P} (h)=(P_{ij}(h))=\mathbb {P} (X_{h}=j\mid X_{0}=i)}$. Матрица переходных вероятностей удовлетворяет уравнению Колмогорова — Чепмена: ${\displaystyle \mathbf {P} (t+s)=\mathbf {P} (t)\mathbf {P} (s)}$ или ${\displaystyle P_{ij}(t+s)=\sum _{k}P_{ik}(t)P_{kj}(s).}$ Матрица интенсивностей и дифференциальные уравнения Колмогорова По определению матрица интенсивностей ${\displaystyle \mathbf {Q} =\lim _{h\to 0}{\frac {\mathbf {P} (h)-\mathbf {I} }{h}}}$, или, что эквивалентно, ${\displaystyle \mathbf {Q} =(q_{ij})=\left({\frac {dP_{ij}(h)}{dh}}\right)_{h=0}}$. Из уравнения Колмогорова — Чепмена следуют два уравнения: Прямое уравнение Колмогорова ${\displaystyle {\frac {d\mathbf {P} (t)}{dt}}=\mathbf {P} (t)\mathbf {Q} ,}$ Обратное уравнение Колмогорова ${\displaystyle {\frac {d\mathbf {P} (t)}{dt}}=\mathbf {Q} \mathbf {P} (t).}$ Для обоих уравнений начальным условием выбирается ${\displaystyle \mathbf {P} (0)=\mathbf {I} }$. Соответствующее решение ${\displaystyle \mathbf {P} (t)=\exp(\mathbf {Q} t).}$ Свойства матриц P и Q Для любого ${\displaystyle t>0}$ матрица ${\displaystyle \mathbf {P} (t)}$ обладает следующими свойствами: Матричные элементы ${\displaystyle \mathbf {P} (t)}$ неотрицательны: ${\displaystyle P_{ij}(t)\geqslant 0}$ (неотрицательность вероятностей). Сумма элементов в каждой строке ${\displaystyle \mathbf {P} (t)}$ равна 1: ${\displaystyle \sum _{j}P_{ij}(t)=1}$ (полная вероятность), то есть матрица ${\displaystyle \mathbf {P} (t)}$ является стохастической справа (или по строкам). Все собственные числа ${\displaystyle \lambda }$ матрицы ${\displaystyle \mathbf {P} (t)}$ не превосходят 1 по абсолютной величине: ${\displaystyle |\lambda |\leqslant 1}$. Если ${\displaystyle |\lambda |=1}$, то ${\displaystyle \lambda =1}$. Собственному числу ${\displaystyle \lambda =1}$ матрицы ${\displaystyle \mathbf {P} (t)}$ соответствует как минимум один неотрицательный левый собственный вектор-строка (равновесие): ${\displaystyle (p_{1}^{*},\,p_{2}^{*},...);}$ ${\displaystyle p_{i}^{*}\geqslant 0;}$ ${\displaystyle \sum _{i}p_{i}^{*}=1;}$ ${\displaystyle \sum _{i}p_{i}^{*}P_{ij}(t)=p_{j}^{*}}$. Для собственного числа ${\displaystyle \lambda =1}$ матрицы ${\displaystyle \mathbf {P} (t)}$ все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны. Матрица ${\displaystyle \mathbf {Q} }$ обладает следующими свойствами: Внедиагональные матричные элементы ${\displaystyle \mathbf {Q} }$ неотрицательны: ${\displaystyle q_{ij}\geqslant 0\;i\neq j}$. Диагональные матричные элементы ${\displaystyle \mathbf {Q} }$ неположительны: ${\displaystyle q_{ii}\leqslant 0}$. Сумма элементов в каждой строке ${\displaystyle \mathbf {Q} }$ равна 0: ${\displaystyle \sum _{j}q_{ij}=0.}$ Действительная часть всех собственных чисел ${\displaystyle \mu }$ матрицы ${\displaystyle \mathbf {Q} }$ неположительна: ${\displaystyle Re(\mu )\leqslant 0}$. Если ${\displaystyle Re(\mu )=0}$, то ${\displaystyle \mu =0.}$ Собственному числу ${\displaystyle \mu =0}$ матрицы ${\displaystyle \mathbf {Q} }$ соответствует как минимум один неотрицательный левый собственный вектор-строка (равновесие): ${\displaystyle (p_{1}^{*},\,p_{2}^{*},...);}$ ${\displaystyle p_{i}^{*}\geqslant 0;}$ ${\displaystyle \sum _{i}p_{i}^{*}=1;}$ ${\displaystyle \sum _{i}p_{i}^{*}q_{ij}=0.}$ Для собственного числа ${\displaystyle \mu =0}$ матрицы ${\displaystyle \mathbf {Q} }$ все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны. Граф переходов, связность и эргодические цепи Маркова Для цепи Маркова с непрерывным временем строится ориентированный граф переходов (кратко — граф переходов) по следующим правилам: Множество вершин графа совпадает со множеством состояний цепи. Вершины ${\displaystyle i,j\,(i\neq j)}$ соединяются ориентированным ребром ${\displaystyle i\to j}$, если ${\displaystyle q_{ij}>0}$ (то есть интенсивность потока из ${\displaystyle i}$-го состояния в ${\displaystyle j}$-е положительна). Топологические свойства графа переходов связаны со спектральными свойствами матрицы ${\displaystyle \mathbf {Q} }$. В частности, для конечных цепей Маркова верны следующие теоремы: Следующие три свойства А, Б, В конечной цепи Маркова эквивалентны (обладающие ими цепи иногда называют слабо эргодическими): А. Для любых двух различных вершин графа переходов ${\displaystyle i,j\,(i\neq j)}$ найдется такая вершина ${\displaystyle k}$ графа («общий сток»), что существуют ориентированные пути от вершины ${\displaystyle i}$ к вершине ${\displaystyle k}$ и от вершины ${\displaystyle j}$ к вершине ${\displaystyle k}$. Замечание: возможен случай ${\displaystyle k=i}$ или ${\displaystyle k=j}$; в этом случае тривиальный (пустой) путь от ${\displaystyle i}$ к ${\displaystyle i}$ или от ${\displaystyle j}$ к ${\displaystyle j}$ также считается ориентированным путём. Б. Нулевое собственное число матрицы ${\displaystyle \mathbf {Q} }$ невырождено. В. При ${\displaystyle t\to \infty }$ матрица ${\displaystyle \mathbf {P} (t)}$ стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением). Следующие пять свойств А, Б, В, Г, Д конечной цепи Маркова эквивалентны (обладающие ими цепи называют эргодическими): А. Граф переходов цепи ориентированно связен. Б. Нулевое собственное число матрицы ${\displaystyle \mathbf {Q} }$ невырождено и ему соответствует строго положительный левый собственный вектор (равновесное распределение). В. Для некоторого ${\displaystyle t>0}$ матрица ${\displaystyle \mathbf {P} (t)}$ строго положительна (то есть ${\displaystyle P_{ij}(t)>0}$ для всех ${\displaystyle i,j}$). Г. Для всех ${\displaystyle t>0}$ матрица ${\displaystyle \mathbf {P} (t)}$ строго положительна. Д. При ${\displaystyle t\to \infty }$ матрица ${\displaystyle \mathbf {P} (t)}$ стремится к строго положительной матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением). Примеры Рассмотрим цепи Маркова с тремя состояниями и с непрерывным временем, соответствующие графам переходов, представленным на рис. В случае (a) отличны от нуля только следующие недиагональные элементы матрицы интенсивностей — ${\displaystyle q_{12},\,q_{13}}$, в случае (b) отличны от нуля только ${\displaystyle q_{12},\,q_{31}\,q_{32}}$, а в случае (c) — ${\displaystyle q_{12},\,q_{31}\,q_{23}}$. Остальные элементы определяются свойствами матрицы ${\displaystyle \mathbf {Q} }$ (сумма элементов в каждой строке равна 0). В результате для графов (a), (b), (c) матрицы интенсивностей имеют вид: ${\displaystyle \mathbf {Q} _{a}={\begin{pmatrix}-(q_{12}+q_{13})&q_{12}&q_{13}\\0&0&0\\0&0&0\end{pmatrix}},}$ ${\displaystyle \mathbf {Q} _{b}={\begin{pmatrix}-q_{12}&q_{12}&0\\0&0&0\\q_{31}&q_{32}&-(q_{31}+q_{32})\end{pmatrix}},}$ ${\displaystyle \mathbf {Q} _{c}={\begin{pmatrix}-q_{12}&q_{12}&0\\0&-q_{23}&q_{23}\\q_{31}&0&-q_{31}\end{pmatrix}},}$ Основное кинетическое уравнение Основное кинетическое уравнение описывает эволюцию распределения вероятностей в цепи Маркова с непрерывным временем. «Основное уравнение» здесь — не эпитет, а перевод термина англ. Master equation. Для вектора-строки распределения вероятностей ${\displaystyle \pi }$ основное кинетическое уравнение имеет вид: ${\displaystyle {\frac {d\pi }{dt}}=\pi \mathbf {Q} }$ и совпадает, по существу, с прямым уравнением Колмогорова. В физической литературе чаще используют векторы-столбцы вероятностей и записывают основное кинетическое уравнение в виде, который явно использует закон сохранения полной вероятности: ${\displaystyle {\frac {dp_{i}}{dt}}=\sum _{j,\,j\neq i}(T_{ij}p_{j}-T_{ji}p_{i}),}$ где ${\displaystyle T_{ij}=q_{ji}.}$ Если для основного кинетического уравнения существует положительное равновесие ${\displaystyle p_{i}^{*}>0}$, то его можно записать в форме ${\displaystyle {\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).}$ Функции Ляпунова для основного кинетического уравнения Для основного кинетического уравнения существует богатое семейство выпуклых функций Ляпунова — монотонно меняющихся со временем функций распределения вероятностей. Пусть ${\displaystyle h(x)\,(x>0)}$ — выпуклая функция одного переменного. Для любого положительного распределения вероятностей (${\displaystyle p_{i}>0}$) определим функцию Моримото ${\displaystyle H_{h}(p)}$: ${\displaystyle H_{h}(p)=\sum _{i}p_{i}^{*}h\left({\frac {p_{i}}{p_{i}^{*}}}\right)}$. Производная ${\displaystyle H_{h}(p)}$ по времени, если ${\displaystyle p(t)}$ удовлетворяет основному кинетическому уравнению, есть ${\displaystyle {\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}$. Последнее неравенство справедливо из-за выпуклости ${\displaystyle h(x)}$. ${\displaystyle h(x)=|x-1|}$, ${\displaystyle H_{h}(p)=\sum _{i}|p_{i}-p_{i}^{*}|}$; эта функция — расстояние от текущего распределения вероятностей до равновесного в ${\displaystyle l_{1}}$-норме. Сдвиг по времени является сжатием пространства вероятностных распределений в этой норме. (О свойствах сжатий см. статью Теорема Банаха о неподвижной точке.) ${\displaystyle h(x)=x\ln x}$, ${\displaystyle H_{h}(p)=\sum _{i}p_{i}\ln \left({\frac {p_{i}}{p_{i}^{*}}}\right)}$; эта функция — (минус) энтропия Кульбака (см. Расстояние Кульбака — Лейблера). В физике она соответствует свободной энергии, деленной на ${\displaystyle kT}$ (где ${\displaystyle k}$ — постоянная Больцмана, ${\displaystyle T}$ — абсолютная температура): если ${\displaystyle p_{i}^{*}=\exp(\mu _{0}-U_{i}/kT)}$ (распределение Больцмана), то ${\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}$. ${\displaystyle h(x)=-\ln x}$, ${\displaystyle H_{h}(p)=-\sum _{i}p_{i}^{*}\ln \left({\frac {p_{i}}{p_{i}^{*}}}\right)}$; эта функция — аналог свободной энергии для энтропии Бурга, широко используемой в обработке сигналов: ${\displaystyle S_{\rm {Burg}}=\sum _{i}\ln p_{i}}$ ${\displaystyle h(x)={\frac {(x-1)^{2}}{2}}}$, ${\displaystyle H_{h}(p)=\sum _{i}{\frac {(p_{i}-p_{i}^{*})^{2}}{2p_{i}^{*}}}}$; это квадратичное приближение для (минус) энтропии Кульбака вблизи точки равновесия. С точностью до постоянного во времени слагаемого эта функция совпадает с (минус) энтропией Фишера, которую даёт следующий выбор, ${\displaystyle h(x)={\frac {x^{2}}{2}}}$, ${\displaystyle H_{h}(p)=\sum _{i}{\frac {p_{i}^{2}}{2p_{i}^{*}}}}$; это (минус) энтропия Фишера. ${\displaystyle h(x)={\frac {x^{q}-1}{q-1}},\,q>0,\,q\neq 1}$, ${\displaystyle H_{h}(p)={\frac {1}{q-1}}\left[\sum _{i}p_{i}^{*}\left({\frac {p_{i}}{p_{i}^{*}}}\right)^{q}-1\right]}$; это один из аналогов свободной энергии для энтропии Тсаллиса. ${\displaystyle S_{q{\rm {Tsallis}}}(p)={1 \over q-1}\left(1-\sum _{i}p_{i}^{q}\right).}$ служит основой для статистической физики неэкстенсивных величин. При ${\displaystyle q\to 1}$ она стремится к классической энтропии Больцмана — Гиббса — Шеннона, а соответствующая функция Моримото — к (минус) энтропии Кульбака. Практическое применение Одной из первых научных дисциплин, в которой цепи Маркова нашли практическое применение, стала лингвистика (в частности текстология). Сам Марков для иллюстрации своих результатов исследовал зависимость в чередовании гласных и согласных в первых главах «Евгения Онегина» и «Детских годов Багрова-внука»[3]. Цепи Маркова используют для генерации текста[4], моделирования процессов смешивания сыпучих материалов[5], управленческом мониторинге[6], языковых моделях[7]. Примечания "Markov chain | Definition of Markov chain in US English by Oxford Dictionaries" (англ.). Oxford Dictionaries | English.. Lexico Dictionaries | English (14 декабря 2017). Дата обращения: 1 апреля 2020. Архивировано из оригинала 25 февраля 2021 года. Gagniuc, Paul A. Markov Chains: From Theory to Implementation and Experimentation (англ.). — USA, NJ: John Wiley & Sons, 2017. — P. 2—8. — ISBN 978-1-119-38755-8. Анатолий Ализар. Генерация фраз с 56-битной энтропией по цепям Маркова  (неопр.). Хакер. Хакер (журнал). Использование цепей Маркова для моделирования процесса смешивания - Современные наукоемкие технологии (научный журнал)  (неопр.). top-technologies.ru. Дата обращения: 7 мая 2025. Рыжкова Т. В. Цепь Маркова, моделирующая изменения в клиентской базе // Вестник Российского экономического университета им. Г. В. Плеханова. — 2008. — Вып. 3. — С. 83–95. — ISSN 2413-2829. Проза нейросетей: как языковые модели научились говорить по-людски  (рус.). Компьютерра (15 октября 2022). Дата обращения: 7 мая 2025. Литература Марков А. А. Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 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.