Марковская цепь — различия между версиями
Rybak (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показана 71 промежуточная версия 10 участников) | |||
Строка 1: | Строка 1: | ||
− | + | {{Определение | |
− | {{ | + | |definition = |
+ | '''Цепь Маркова''' (англ. ''Markov chain'') {{---}} последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем, что при фиксированном настоящем будущее независимо от прошлого. | ||
− | + | Процесс в каждый момент времени находится в одном из <tex> n </tex> состояний. | |
− | + | При этом, если он находится в состоянии с номером <tex> i </tex>, то он перейдет в состояние <tex> j </tex> с вероятностью <tex> p_{ij} </tex>. | |
− | |||
− | При этом, если он | ||
− | Матрицу <tex>P = ||p_{ij}||</tex> называют '''матрицей переходов'''. | + | Матрицу <tex> P = ||p_{ij}|| </tex> называют '''матрицей переходов''' (англ. ''transition matrix''). |
}} | }} | ||
− | |||
− | |||
На матрицу переходов накладываются следующие условия: | На матрицу переходов накладываются следующие условия: | ||
Строка 20: | Строка 17: | ||
Такая матрица называется ''стохастической''. | Такая матрица называется ''стохастической''. | ||
− | + | Марковскую цепь можно представить в виде [[Основные определения теории графов#Ориентированные графы | графа]], в котором вершины — это состояния процесса, а ребра — переходы между состояниями, и на ребре из <tex> i </tex> в <tex> j </tex> написана вероятность перехода из <tex> i </tex> в <tex> j </tex>, то есть <tex> p_{ij} </tex>. | |
+ | |||
+ | == Распределение вероятностей == | ||
+ | |||
+ | Марковскую цепь в любой момент времени <tex> t </tex> можно охарактеризовать вектором-строкой <tex> c_t </tex> — распределением вероятностей по состояниям цепи (<tex> c_{ti} </tex> — вероятность цепи в момент времени <tex> t </tex> быть в состоянии <tex> i </tex>). | ||
+ | |||
+ | Если <tex> c_i </tex> — текущее распределение вероятностей, то можно узнать распределение на следующем шаге, умножив вектор на матрицу перехода: | ||
+ | |||
+ | <tex> c_{i + 1} = c_{i} \times P </tex>. | ||
+ | |||
+ | Из ассоциативности произведения матриц следует, что для того, чтобы узнать распределение вероятностей через <tex> t </tex> шагов, нужно умножить <tex> c_i </tex> на матрицу перехода, возведённую в степень <tex> t </tex>: | ||
− | + | <tex> c_{i + t} = c_{i} \times P^t </tex>. | |
− | + | Для марковской цепи иногда задают начальное распределение <tex> c_0 </tex>, хотя во многих классах марковских цепей распределение по прошествии большого периода времени от него не зависит (такое распределение называют '''предельным''' (англ. ''limiting distribution'')). | |
− | + | == Достижимость и сообщаемость == | |
+ | Обозначим вероятность попасть из состояния <tex> i </tex> в состояние <tex> j </tex> за <tex> n </tex> переходов как <tex> p_{ij}^{(n)} </tex>. | ||
− | {{Определение | definition = | + | {{Определение |
− | Состояние <tex> | + | |definition= |
− | + | Состояние <tex> j </tex> '''достижимо''' (англ. ''accesible'') из состояния <tex> i </tex>, если существует такое <tex> n </tex>, что <tex> p_{ij}^{(n)} > 0 </tex>. Достижимость <tex> j </tex> из <tex> i </tex> обозначается <tex> i \rightarrow j </tex>. <br> | |
}} | }} | ||
− | + | {{Определение | |
+ | |definition= | ||
+ | Состояния <tex> i </tex> и <tex> j </tex> '''сообщаются''' (англ. ''communicate''), если они достижимы друг из друга. Сообщаемость <tex> i </tex> и <tex> j </tex> обозначается <tex> i \leftrightarrow j </tex>. | ||
+ | }} | ||
+ | |||
+ | == Классификация цепей и состояний == | ||
+ | === Неразложимая цепь === | ||
+ | {{Определение | ||
+ | |definition= | ||
+ | '''Неразложимый класс''' (англ. ''communicating class'') — класс эквивалентности множества состояний по отношению сообщаемости. Если представить марковскую цепь как граф, неразложимый класс будет аналогичен [[Отношение связности, компоненты связности#Сильная связность | компоненте сильной связности]]. | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | '''Неразложимая цепь''' (англ. ''irreducible chain'') — цепь Маркова, в которой все состояния образуют один неразложимый класс. | ||
+ | }} | ||
+ | |||
+ | === [[Эргодическая марковская цепь|Эргодическая цепь]] === | ||
+ | {{Определение | ||
+ | |id = sort_def | ||
+ | |definition= | ||
+ | Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются '''эргодическими классами''' (англ. ''ergodic classes''). Состояния в эргодических классах называются '''эргодическими''' (англ. ''ergodic''), '''возвратными''', или '''существенными''' (англ. ''essential''). Все остальные неразложимые классы называются '''невозвратными классами'''. Состояния, входящие в них, называются '''невозвратными''' или '''несущественными''' (англ. ''inessential''). | ||
+ | }} | ||
+ | |||
+ | Если эргодический класс состоит из одного состояния, такое состояние является [[Марковская цепь#Поглощающая цепь|поглощающим]]. Из свойств частичного упорядочения, в любой цепи Маркова найдется хотя бы один эргодический класс. | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | '''Эргодическая''' марковская цепь (англ. ''ergodic Markov chain'') — марковская цепь, целиком состоящая из одного эргодического класса. | ||
+ | }} | ||
+ | |||
+ | Пусть <tex> N_{i, j} </tex> — множество таких <tex> n </tex>, что находясь в состоянии <tex> i </tex>, можно оказаться в состоянии <tex> j </tex> через <tex> n </tex> шагов. <tex> d_i </tex> — наибольший общий делитель чисел из множества <tex> N_{i, i} </tex>. | ||
+ | |||
+ | {{Лемма | ||
+ | |statement= | ||
+ | Для <tex> i </tex> и <tex> j </tex>, принадлежащих одному классу эквивалентности по отношению достижимости, <tex> d_i = d_j = d </tex> и числа из множества <tex> N_{i, j} </tex> сравнимы между собой по модулю <tex> d </tex>. | ||
+ | |proof= | ||
+ | Пусть <tex> a \in N_{i, j}, \ b \in N_{i, j}, \ c \in N_{j, i} </tex>. Из <tex> i </tex> можно попасть в <tex> j </tex> и обратно, значит, <tex> a + c \in N_{i, i} </tex>. Также после попадания в <tex> j </tex> можно сколько угодно раз перейти из него в самого себя, и только потом перейти в <tex> i </tex>, для этого понадобится <tex> a + k \cdot d_j + c </tex> шагов при любом достаточно большом <tex> k </tex>. Значит, <tex> d_j </tex> должно делиться на <tex> d_i </tex>. Но аналогично можно доказать, что <tex> d_i </tex> делится на <tex> d_j </tex>, поэтому <tex> d_i = d_j = d </tex>. Также можно перейти за <tex> b </tex> шагов в <tex> j </tex>, а потом попасть в <tex> i </tex>, поэтому <tex> b + c \in N_{i, i} </tex>. Значит, <tex> a + c </tex> и <tex> b + c </tex> оба делятся на <tex> d </tex>, то есть <tex> a </tex> и <tex> b </tex> сравнимы между собой по модулю <tex> d </tex>. | ||
+ | }} | ||
+ | |||
+ | Введём числа <tex> t_{i, j}, 0 \leqslant t_{i, j} < d </tex>, так, что любой элемент из <tex> N_{i, j} </tex> сравним с <tex> t_{i, j} </tex> по модулю <tex> d </tex>. | ||
+ | |||
+ | === Циклический класс === | ||
+ | {{Определение | ||
+ | |definition= | ||
+ | '''Циклический класс''' (англ. ''cyclic class'') {{---}} класс, для любых элементов <tex> i </tex> и <tex> j </tex> которого верно равенство <tex> t_{i, j} = 0 </tex>. | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | Если цепь состоит целиком из одного циклического класса, её называют '''[[Регулярная марковская цепь|регулярной]]''', иначе — '''циклической'''. | ||
+ | }} | ||
+ | |||
+ | Если цепь циклическая, у неё есть некоторый период <tex> d > 1 </tex>, а её состояния подразделяются на <tex> d </tex> циклических классов. Цепь движется по циклическим классам в определённом порядке, возвращаясь в класс с начальным состоянием через <tex> d </tex> шагов. | ||
+ | |||
+ | Топология циклических цепей разнообразна. Самым тривиальным случаем является элементарный цикл из <tex> n </tex> состояний и, следовательно, содержащий <tex> n </tex> циклический классов. Более сложный случай – простые циклы. Простой цикл состоит из | ||
+ | нескольких циклов, пересекающихся по вершинам, но не пересекающихся по | ||
+ | ребрам. Все эти циклы обязаны не быть взаимно простыми. Иначе НОД длин | ||
+ | этих циклов равен единице, и цепь регулярна. Общий случай циклической цепи – цепь, состоящая из циклов, пересекающихся по вершинам и ребрам в представлении цепи как графа. | ||
+ | |||
+ | ==== Примеры циклических цепей ==== | ||
+ | |||
+ | {| class = "wikitable" | ||
+ | ! Изображение !! Матрица переходов !! Описание | ||
+ | |- | ||
+ | |style="background-color:#FFF" |[[Файл:N steps chain.png|400px|center|Элементарный цикл]] | ||
+ | |<tex>\begin{pmatrix} | ||
+ | 0 & 1 & 0 & \cdots & 0 & 0 & 0 \\ | ||
+ | 0 & 0 & 1 & \cdots & 0 & 0 & 0 \\ | ||
+ | \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ | ||
+ | 0 & 0 & 0 & \cdots & 0 & 0 & 1 \\ | ||
+ | 1 & 0 & 0 & \cdots & 0 & 0 & 0 | ||
+ | \end{pmatrix}_N | ||
+ | </tex> | ||
+ | | Стохастическая матрица элементарного цикла всегда имеет по одной единице в каждом столбце и каждой строке. Таким образом, нужно ровно <tex> n </tex> шагов, проходящих через все вершины, чтобы попасть из вершины <tex> j </tex> в неё же. | ||
+ | |- | ||
+ | |style="background-color:#FFF" |[[Файл:Prime cyclic chain.png|200px|center|Простой цикл]] | ||
+ | |<tex>\begin{pmatrix} | ||
+ | 0 & 0 & 0,5 & 0,5 & 0 & 0 \\ | ||
+ | 1 & 0 & 0 & 0 & 0 & 0 \\ | ||
+ | 0 & 1 & 0 & 0 & 0 & 0 \\ | ||
+ | 0 & 0 & 0 & 0 & 1 & 0 \\ | ||
+ | 0 & 0 & 0 & 0 & 0 & 1 \\ | ||
+ | 1 & 0 & 0 & 0 & 0 & 0 | ||
+ | \end{pmatrix} | ||
+ | </tex> | ||
+ | |Этот простой цикл состоит из двух элементарных, пересекающихся в вершине <tex> 1 </tex>. НОД длин всех путей из вершины <tex> 1 </tex> в вершину <tex> 1 </tex> равен <tex> 1 </tex>, поэтому можно получить предельное распределение. | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | === Поглощающая цепь === | ||
+ | {{Определение | ||
+ | |definition='''Поглощающее состояние''' (англ. ''absorbing state'') — состояние, из которого нельзя попасть ни в какое другое, то есть <tex> i </tex> — поглощающее состояние, если <tex> p_{ii} = 1 </tex>. | ||
+ | }} | ||
+ | {{Определение | ||
+ | |definition='''Поглощающей''' (англ. ''absorbing chain'') называется марковская цепь, в которой есть хотя бы одно поглощающее состояние и из любого состояния достижимо хотя бы одно поглощающее. | ||
+ | }} | ||
+ | |||
+ | В примере на рисунке поглощающими являются состояния <tex>3</tex> и <tex>4</tex>, а непоглощающими — <tex>1</tex> и <tex>2</tex>. | ||
+ | |||
+ | === Пример === | ||
+ | [[File:Markov-chain-example-complete.png|thumb|500px|Пример марковской цепи]] | ||
+ | |||
+ | На рисунке: | ||
+ | * достижимыми состояниями являются: <tex> 2 </tex> из <tex> 1 </tex> (непосредственно), <tex> 3 </tex> из <tex> 1 </tex> (непосредственно), <tex> 6 </tex> из <tex> 3 </tex> (к примеру, через цепочку состояний <tex> 3 \rightarrow 2 \rightarrow 4 \rightarrow 6 </tex>) и т.д. | ||
+ | * сообщаются состояния <tex> 1 </tex> и <tex> 2 </tex> (непосредственно), <tex> 6 </tex> и <tex> 7 </tex> (непосредственно), <tex <tex> 1 </tex> и <tex> 3 </tex> (достижимы друг из друга) и т. д. | ||
+ | * неразложимыми классами являются множества вершин <tex> \left \{ 1, 2, 3 \right \} </tex>, <tex> \left \{ 4 \right \} </tex>, <tex> \left \{ 5 \right \} </tex>, <tex> \left \{ 6, 7 \right \} </tex>; | ||
+ | * эргодическими классами являются множества вершин <tex> \left \{ 5 \right \} </tex>, <tex> \left \{ 6, 7 \right \} </tex>; | ||
+ | * поглощающим состоянием является состояние <tex> 5 </tex>. | ||
+ | * если расматривать <tex> \{6, 7\} </tex> отдельно, можно выделить два циклических класса <tex> \{6\} </tex> и <tex> \{7\} </tex> (на каждом шаге цепь переходит из одного состояния в другое, а через <tex> d = 2 </tex> шага возвращается в одно и то же состояние. | ||
+ | |||
+ | ==Подсчет количества поглощащих состояний== | ||
+ | Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition[i][2]}</tex> — вероятность перехода из состояния <tex>\mathtt{transition[i][0]}</tex> в <tex>\mathtt{transition[i][1]}</tex>. | ||
+ | Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition[j][2] = 1}</tex>. По этому признаку помно определить все поглощающие состояния в цепи. | ||
+ | |||
+ | ===Псевдокод=== | ||
+ | *<tex>\mathtt{absorbing}: boolean:[\mathtt{n}]</tex> — массив состояний. Если <tex>i</tex> — посглощающее состояние, то <tex>\mathtt{absorbing[i]} = true</tex> | ||
+ | *<tex>\mathtt{n}</tex> — количество состояний | ||
+ | *<tex>\mathtt{m}</tex> — количество переходов | ||
+ | |||
+ | '''function''' findAbsorbings(transition: '''int'''[m][2]): | ||
+ | '''boolean''' absorbing[m] | ||
+ | '''for''' i = 0 '''to''' m - 1 | ||
+ | '''if''' transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1 | ||
+ | absorbing[transition[i][0]] = ''true'' | ||
+ | '''return''' absorbing | ||
− | == | + | == См. также == |
+ | *[[Эргодическая марковская цепь]] | ||
+ | *[[Регулярная марковская цепь]] | ||
+ | *[[Отношение связности, компоненты связности]] | ||
− | + | == Источники информации == | |
− | * [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D0%B8_%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D0%B0 Цепь Маркова] | + | * ''Романовский И. В.'' Дискретный анализ. — СПб.: Невский Диалект; БХВ-Петербург, 2003. — С. 270—279. — ISBN 5-7940-0114-3 |
− | * [ | + | * ''Кемени Дж., Снелл Дж.'' Конечные цепи Маркова. — М. : Наука, 1970. — 272 c. |
+ | * [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D0%B8_%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D0%B0 Википедия {{---}} Цепь Маркова] | ||
+ | * [https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia {{---}} Absorbing Markov chain] | ||
− | + | [[Категория:Дискретная математика и алгоритмы]] | |
− | + | [[Категория: Марковские цепи ]] |
Текущая версия на 19:17, 4 сентября 2022
Определение: |
Цепь Маркова (англ. Markov chain) — последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем, что при фиксированном настоящем будущее независимо от прошлого.
Процесс в каждый момент времени находится в одном из состояний.При этом, если он находится в состоянии с номером Матрицу , то он перейдет в состояние с вероятностью . называют матрицей переходов (англ. transition matrix). |
На матрицу переходов накладываются следующие условия:
Такая матрица называется стохастической.
Марковскую цепь можно представить в виде графа, в котором вершины — это состояния процесса, а ребра — переходы между состояниями, и на ребре из в написана вероятность перехода из в , то есть .
Распределение вероятностей
Марковскую цепь в любой момент времени
можно охарактеризовать вектором-строкой — распределением вероятностей по состояниям цепи ( — вероятность цепи в момент времени быть в состоянии ).Если
— текущее распределение вероятностей, то можно узнать распределение на следующем шаге, умножив вектор на матрицу перехода:.
Из ассоциативности произведения матриц следует, что для того, чтобы узнать распределение вероятностей через
шагов, нужно умножить на матрицу перехода, возведённую в степень :.
Для марковской цепи иногда задают начальное распределение
, хотя во многих классах марковских цепей распределение по прошествии большого периода времени от него не зависит (такое распределение называют предельным (англ. limiting distribution)).Достижимость и сообщаемость
Обозначим вероятность попасть из состояния
в состояние за переходов как .
Определение: |
Состояние | достижимо (англ. accesible) из состояния , если существует такое , что . Достижимость из обозначается .
Определение: |
Состояния | и сообщаются (англ. communicate), если они достижимы друг из друга. Сообщаемость и обозначается .
Классификация цепей и состояний
Неразложимая цепь
Определение: |
Неразложимый класс (англ. communicating class) — класс эквивалентности множества состояний по отношению сообщаемости. Если представить марковскую цепь как граф, неразложимый класс будет аналогичен компоненте сильной связности. |
Определение: |
Неразложимая цепь (англ. irreducible chain) — цепь Маркова, в которой все состояния образуют один неразложимый класс. |
Эргодическая цепь
Определение: |
Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются эргодическими классами (англ. ergodic classes). Состояния в эргодических классах называются эргодическими (англ. ergodic), возвратными, или существенными (англ. essential). Все остальные неразложимые классы называются невозвратными классами. Состояния, входящие в них, называются невозвратными или несущественными (англ. inessential). |
Если эргодический класс состоит из одного состояния, такое состояние является поглощающим. Из свойств частичного упорядочения, в любой цепи Маркова найдется хотя бы один эргодический класс.
Определение: |
Эргодическая марковская цепь (англ. ergodic Markov chain) — марковская цепь, целиком состоящая из одного эргодического класса. |
Пусть — множество таких , что находясь в состоянии , можно оказаться в состоянии через шагов. — наибольший общий делитель чисел из множества .
Лемма: |
Для и , принадлежащих одному классу эквивалентности по отношению достижимости, и числа из множества сравнимы между собой по модулю . |
Доказательство: |
Пусть | . Из можно попасть в и обратно, значит, . Также после попадания в можно сколько угодно раз перейти из него в самого себя, и только потом перейти в , для этого понадобится шагов при любом достаточно большом . Значит, должно делиться на . Но аналогично можно доказать, что делится на , поэтому . Также можно перейти за шагов в , а потом попасть в , поэтому . Значит, и оба делятся на , то есть и сравнимы между собой по модулю .
Введём числа
, так, что любой элемент из сравним с по модулю .Циклический класс
Определение: |
Циклический класс (англ. cyclic class) — класс, для любых элементов | и которого верно равенство .
Определение: |
Если цепь состоит целиком из одного циклического класса, её называют регулярной, иначе — циклической. |
Если цепь циклическая, у неё есть некоторый период , а её состояния подразделяются на циклических классов. Цепь движется по циклическим классам в определённом порядке, возвращаясь в класс с начальным состоянием через шагов.
Топология циклических цепей разнообразна. Самым тривиальным случаем является элементарный цикл из
состояний и, следовательно, содержащий циклический классов. Более сложный случай – простые циклы. Простой цикл состоит из нескольких циклов, пересекающихся по вершинам, но не пересекающихся по ребрам. Все эти циклы обязаны не быть взаимно простыми. Иначе НОД длин этих циклов равен единице, и цепь регулярна. Общий случай циклической цепи – цепь, состоящая из циклов, пересекающихся по вершинам и ребрам в представлении цепи как графа.Примеры циклических цепей
Изображение | Матрица переходов | Описание |
---|---|---|
Стохастическая матрица элементарного цикла всегда имеет по одной единице в каждом столбце и каждой строке. Таким образом, нужно ровно | шагов, проходящих через все вершины, чтобы попасть из вершины в неё же.||
Этот простой цикл состоит из двух элементарных, пересекающихся в вершине | . НОД длин всех путей из вершины в вершину равен , поэтому можно получить предельное распределение.
Поглощающая цепь
Определение: |
Поглощающее состояние (англ. absorbing state) — состояние, из которого нельзя попасть ни в какое другое, то есть | — поглощающее состояние, если .
Определение: |
Поглощающей (англ. absorbing chain) называется марковская цепь, в которой есть хотя бы одно поглощающее состояние и из любого состояния достижимо хотя бы одно поглощающее. |
В примере на рисунке поглощающими являются состояния и , а непоглощающими — и .
Пример
На рисунке:
- достижимыми состояниями являются: из (непосредственно), из (непосредственно), из (к примеру, через цепочку состояний ) и т.д.
- сообщаются состояния и (непосредственно), и (непосредственно), и (достижимы друг из друга) и т. д.
- неразложимыми классами являются множества вершин , , , ;
- эргодическими классами являются множества вершин , ;
- поглощающим состоянием является состояние .
- если расматривать отдельно, можно выделить два циклических класса и (на каждом шаге цепь переходит из одного состояния в другое, а через шага возвращается в одно и то же состояние.
Подсчет количества поглощащих состояний
Пусть
— массив переходов марковской цепи, где — вероятность перехода из состояния в . Тогда, по определению поглощающего состояния, если — поглощающее состояние, то . По этому признаку помно определить все поглощающие состояния в цепи.Псевдокод
- — массив состояний. Если — посглощающее состояние, то
- — количество состояний
- — количество переходов
function findAbsorbings(transition: int[m][2]): boolean absorbing[m] for i = 0 to m - 1 if transition[i][0] == transition[i][1] and transition[i][2] == 1 absorbing[transition[i][0]] = true return absorbing
См. также
Источники информации
- Романовский И. В. Дискретный анализ. — СПб.: Невский Диалект; БХВ-Петербург, 2003. — С. 270—279. — ISBN 5-7940-0114-3
- Кемени Дж., Снелл Дж. Конечные цепи Маркова. — М. : Наука, 1970. — 272 c.
- Википедия — Цепь Маркова
- Wikipedia — Absorbing Markov chain